QGIS API Documentation  2.5.0-Master
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
feature.cpp
Go to the documentation of this file.
1 /*
2  * libpal - Automated Placement of Labels Library
3  *
4  * Copyright (C) 2008 Maxence Laurent, MIS-TIC, HEIG-VD
5  * University of Applied Sciences, Western Switzerland
6  * http://www.hes-so.ch
7  *
8  * Contact:
9  * maxence.laurent <at> heig-vd <dot> ch
10  * or
11  * eric.taillard <at> heig-vd <dot> ch
12  *
13  * This file is part of libpal.
14  *
15  * libpal is free software: you can redistribute it and/or modify
16  * it under the terms of the GNU General Public License as published by
17  * the Free Software Foundation, either version 3 of the License, or
18  * (at your option) any later version.
19  *
20  * libpal is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
23  * GNU General Public License for more details.
24  *
25  * You should have received a copy of the GNU General Public License
26  * along with libpal. If not, see <http://www.gnu.org/licenses/>.
27  *
28  */
29 
30 #ifdef HAVE_CONFIG_H
31 #include <config.h>
32 #endif
33 
34 #define _CRT_SECURE_NO_DEPRECATE
35 
36 
37 #if defined(_VERBOSE_) || (_DEBUG_)
38 #include <iostream>
39 #endif
40 
41 #include <qglobal.h>
42 
43 #include <cmath>
44 #include <cstring>
45 #include <cfloat>
46 
47 #include <pal/pal.h>
48 #include <pal/layer.h>
49 
50 #include "linkedlist.hpp"
51 #include "feature.h"
52 #include "geomfunction.h"
53 #include "labelposition.h"
54 #include "pointset.h"
55 #include "simplemutex.h"
56 #include "util.h"
57 
58 #ifndef M_PI
59 #define M_PI 3.14159265358979323846
60 #endif
61 
62 namespace pal
63 {
64  Feature::Feature( Layer* l, const char* geom_id, PalGeometry* userG, double lx, double ly )
65  : layer( l ), userGeom( userG ), label_x( lx ), label_y( ly ), distlabel( 0 ), labelInfo( NULL ), fixedPos( false ),
66  quadOffset( false ), offsetPos( false ), fixedRotation( false ), alwaysShow( false )
67  {
68  assert( finite( lx ) && finite( ly ) );
69 
70  uid = new char[strlen( geom_id ) +1];
71  strcpy( uid, geom_id );
72  }
73 
75  {
76  delete[] uid;
77  }
78 
80 
81  FeaturePart::FeaturePart( Feature *feat, const GEOSGeometry* geom )
82  : f( feat ), nbHoles( 0 ), holes( NULL )
83  {
84  // we'll remove const, but we won't modify that geometry
85  the_geom = const_cast<GEOSGeometry*>( geom );
86  ownsGeom = false; // geometry is owned by Feature class
87 
88  extractCoords( geom );
89 
90  holeOf = NULL;
91  for ( int i = 0; i < nbHoles; i++ )
92  {
93  holes[i]->holeOf = this;
94  }
95  }
96 
97 
99  {
100  // X and Y are deleted in PointSet
101 
102  if ( holes )
103  {
104  for ( int i = 0; i < nbHoles; i++ )
105  delete holes[i];
106  delete [] holes;
107  holes = NULL;
108  }
109 
110  if ( ownsGeom )
111  {
112  GEOSGeom_destroy( the_geom );
113  the_geom = NULL;
114  }
115  }
116 
117 
118  /*
119  * \brief read coordinates from a GEOS geom
120  */
121  void FeaturePart::extractCoords( const GEOSGeometry* geom )
122  {
123  int i, j;
124 
125  const GEOSCoordSequence *coordSeq;
126 
127  type = GEOSGeomTypeId( geom );
128 
129  if ( type == GEOS_POLYGON )
130  {
131  if ( GEOSGetNumInteriorRings( geom ) > 0 )
132  {
133  // set nbHoles, holes member variables
134  nbHoles = GEOSGetNumInteriorRings( geom );
135  holes = new PointSet*[nbHoles];
136 
137  for ( i = 0; i < nbHoles; i++ )
138  {
139  holes[i] = new PointSet();
140  holes[i]->holeOf = NULL;
141 
142  const GEOSGeometry* interior = GEOSGetInteriorRingN( geom, i );
143  holes[i]->nbPoints = GEOSGetNumCoordinates( interior );
144  holes[i]->x = new double[holes[i]->nbPoints];
145  holes[i]->y = new double[holes[i]->nbPoints];
146 
147  holes[i]->xmin = holes[i]->ymin = DBL_MAX;
148  holes[i]->xmax = holes[i]->ymax = -DBL_MAX;
149 
150  coordSeq = GEOSGeom_getCoordSeq( interior );
151 
152  for ( j = 0; j < holes[i]->nbPoints; j++ )
153  {
154  GEOSCoordSeq_getX( coordSeq, j, &holes[i]->x[j] );
155  GEOSCoordSeq_getY( coordSeq, j, &holes[i]->y[j] );
156 
157  holes[i]->xmax = holes[i]->x[j] > holes[i]->xmax ? holes[i]->x[j] : holes[i]->xmax;
158  holes[i]->xmin = holes[i]->x[j] < holes[i]->xmin ? holes[i]->x[j] : holes[i]->xmin;
159 
160  holes[i]->ymax = holes[i]->y[j] > holes[i]->ymax ? holes[i]->y[j] : holes[i]->ymax;
161  holes[i]->ymin = holes[i]->y[j] < holes[i]->ymin ? holes[i]->y[j] : holes[i]->ymin;
162  }
163 
164  reorderPolygon( holes[i]->nbPoints, holes[i]->x, holes[i]->y );
165  }
166  }
167 
168  // use exterior ring for the extraction of coordinates that follows
169  geom = GEOSGetExteriorRing( geom );
170  }
171  else
172  {
173  nbHoles = 0;
174  holes = NULL;
175  }
176 
177  // find out number of points
178  nbPoints = GEOSGetNumCoordinates( geom );
179  coordSeq = GEOSGeom_getCoordSeq( geom );
180 
181  // initialize bounding box
182  xmin = ymin = DBL_MAX;
183  xmax = ymax = -DBL_MAX;
184 
185  // initialize coordinate arrays
186  x = new double[nbPoints];
187  y = new double[nbPoints];
188 
189  for ( i = 0; i < nbPoints; i++ )
190  {
191  GEOSCoordSeq_getX( coordSeq, i, &x[i] );
192  GEOSCoordSeq_getY( coordSeq, i, &y[i] );
193 
194  xmax = x[i] > xmax ? x[i] : xmax;
195  xmin = x[i] < xmin ? x[i] : xmin;
196 
197  ymax = y[i] > ymax ? y[i] : ymax;
198  ymin = y[i] < ymin ? y[i] : ymin;
199  }
200  }
201 
203  {
204  // TODO add simplify() process
205  int new_nbPoints = nbPoints;
206  bool *ok = new bool[new_nbPoints];
207  int i, j;
208 
209  for ( i = 0; i < nbPoints; i++ )
210  {
211  ok[i] = true;
212  j = ( i + 1 ) % nbPoints;
213  if ( i == j )
214  break;
215  if ( vabs( x[i] - x[j] ) < 0.0000001 && vabs( y[i] - y[j] ) < 0.0000001 )
216  {
217  new_nbPoints--;
218  ok[i] = false;
219  }
220  }
221 
222  if ( new_nbPoints < nbPoints )
223  {
224  double *new_x = new double[new_nbPoints];
225  double *new_y = new double[new_nbPoints];
226  for ( i = 0, j = 0; i < nbPoints; i++ )
227  {
228  if ( ok[i] )
229  {
230  new_x[j] = x[i];
231  new_y[j] = y[i];
232  j++;
233  }
234  }
235  delete[] x;
236  delete[] y;
237  // interchange the point arrays
238  x = new_x;
239  y = new_y;
240  nbPoints = new_nbPoints;
241  }
242 
243  delete[] ok;
244  }
245 
246 
247 
248 
250  {
251  return f->layer;
252  }
253 
254 
255  const char * FeaturePart::getUID()
256  {
257  return f->uid;
258  }
259 
260  int FeaturePart::setPositionOverPoint( double x, double y, double scale, LabelPosition ***lPos, double delta_width, double angle )
261  {
262  Q_UNUSED( scale );
263  Q_UNUSED( delta_width );
264  int nbp = 3;
265  *lPos = new LabelPosition *[nbp];
266 
267  // get from feature
268  double label_x = f->label_x;
269  double label_y = f->label_y;
270  double labelW = f->label_x;
271  double labelH = f->label_y;
272 
273  double xdiff = 0.0;
274  double ydiff = 0.0;
275  double lx = 0.0;
276  double ly = 0.0;
277  double cost = 0.0001;
278  int id = 0;
279 
280  xdiff -= label_x / 2.0;
281  ydiff -= label_y / 2.0;
282 
283  if ( ! f->fixedPosition() )
284  {
285  if ( angle != 0 )
286  {
287  double xd = xdiff * cos( angle ) - ydiff * sin( angle );
288  double yd = xdiff * sin( angle ) + ydiff * cos( angle );
289  xdiff = xd;
290  ydiff = yd;
291  }
292  }
293 
294  if ( angle != 0 )
295  {
296  // use LabelPosition construction to calculate new rotated label dimensions
297  pal::LabelPosition* lp = new LabelPosition( 1, lx, ly, label_x, label_y, angle, 0.0, this );
298 
299  double amin[2], amax[2];
300  lp->getBoundingBox( amin, amax );
301  labelW = amax[0] - amin[0];
302  labelH = amax[1] - amin[1];
303 
304  delete lp;
305  }
306 
307  if ( f->quadOffset )
308  {
309  if ( f->quadOffsetX != 0 )
310  {
311  xdiff += labelW / 2 * f->quadOffsetX;
312  }
313  if ( f->quadOffsetY != 0 )
314  {
315  ydiff += labelH / 2 * f->quadOffsetY;
316  }
317  }
318 
319  if ( f->offsetPos )
320  {
321  if ( f->offsetPosX != 0 )
322  {
323  xdiff += f->offsetPosX;
324  }
325  if ( f->offsetPosY != 0 )
326  {
327  ydiff += f->offsetPosY;
328  }
329  }
330 
331  lx = x + xdiff;
332  ly = y + ydiff;
333 
334 // double offset = label_x / 4;
335  double offset = 0.0; // don't shift what is supposed to be fixed
336 
337  // at the center
338  ( *lPos )[0] = new LabelPosition( id, lx, ly, label_x, label_y, angle, cost, this );
339  // shifted to the sides - with higher cost
340  cost = 0.0021;
341  ( *lPos )[1] = new LabelPosition( id, lx + offset, ly, label_x, label_y, angle, cost, this );
342  ( *lPos )[2] = new LabelPosition( id, lx - offset, ly, label_x, label_y, angle, cost, this );
343  return nbp;
344  }
345 
346  int FeaturePart::setPositionForPoint( double x, double y, double scale, LabelPosition ***lPos, double delta_width, double angle )
347  {
348 
349 #ifdef _DEBUG_
350  std::cout << "SetPosition (point) : " << layer->name << "/" << uid << std::endl;
351 #endif
352 
353  int dpi = f->layer->pal->dpi;
354 
355 
356  double xrm;
357  double yrm;
358  double distlabel = f->distlabel;
359 
360  xrm = unit_convert( f->label_x,
361  f->layer->label_unit,
362  f->layer->pal->map_unit,
363  dpi, scale, delta_width );
364 
365  yrm = unit_convert( f->label_y,
366  f->layer->label_unit,
367  f->layer->pal->map_unit,
368  dpi, scale, delta_width );
369 
370  int nbp = f->layer->pal->point_p;
371 
372  //std::cout << "Nbp : " << nbp << std::endl;
373 
374  int i;
375  int icost = 0;
376  int inc = 2;
377 
378  double alpha;
379  double beta = 2 * M_PI / nbp; /* angle bw 2 pos */
380 
381  // uncomment for Wolff 2 position model test on RailwayStation
382  //if (nbp==2)
383  // beta = M_PI/2;
384 
385 #if 0
386  double distlabel = unit_convert( this->distlabel,
387  pal::PIXEL,
388  layer->pal->map_unit,
389  dpi, scale, delta_width );
390 #endif
391 
392  double lx, ly; /* label pos */
393 
394  /* various alpha */
395  double a90 = M_PI / 2;
396  double a180 = M_PI;
397  double a270 = a180 + a90;
398  double a360 = 2 * M_PI;
399 
400 
401  double gamma1, gamma2;
402 
403  if ( distlabel > 0 )
404  {
405  gamma1 = atan2( yrm / 2, distlabel + xrm / 2 );
406  gamma2 = atan2( xrm / 2, distlabel + yrm / 2 );
407  }
408  else
409  {
410  gamma1 = gamma2 = a90 / 3.0;
411  }
412 
413 
414  if ( gamma1 > a90 / 3.0 )
415  gamma1 = a90 / 3.0;
416 
417  if ( gamma2 > a90 / 3.0 )
418  gamma2 = a90 / 3.0;
419 
420 
421  if ( gamma1 == 0 || gamma2 == 0 )
422  {
423  std::cout << "Oups... label size error..." << std::endl;
424  }
425 
426  *lPos = new LabelPosition *[nbp];
427 
428  for ( i = 0, alpha = M_PI / 4; i < nbp; i++, alpha += beta )
429  {
430  lx = x;
431  ly = y;
432 
433  if ( alpha > a360 )
434  alpha -= a360;
435 
436  if ( alpha < gamma1 || alpha > a360 - gamma1 ) // on the right
437  {
438  lx += distlabel;
439  double iota = ( alpha + gamma1 );
440  if ( iota > a360 - gamma1 )
441  iota -= a360;
442 
443  //ly += -yrm/2.0 + tan(alpha)*(distlabel + xrm/2);
444  ly += -yrm + yrm * iota / ( 2 * gamma1 );
445  }
446  else if ( alpha < a90 - gamma2 ) // top-right
447  {
448  lx += distlabel * cos( alpha );
449  ly += distlabel * sin( alpha );
450  }
451  else if ( alpha < a90 + gamma2 ) // top
452  {
453  //lx += -xrm/2.0 - tan(alpha+a90)*(distlabel + yrm/2);
454  lx += -xrm * ( alpha - a90 + gamma2 ) / ( 2 * gamma2 ) ;
455  ly += distlabel;
456  }
457  else if ( alpha < a180 - gamma1 ) // top left
458  {
459  lx += distlabel * cos( alpha ) - xrm;
460  ly += distlabel * sin( alpha );
461  }
462  else if ( alpha < a180 + gamma1 ) // left
463  {
464  lx += -distlabel - xrm;
465  //ly += -yrm/2.0 - tan(alpha)*(distlabel + xrm/2);
466  ly += - ( alpha - a180 + gamma1 ) * yrm / ( 2 * gamma1 );
467  }
468  else if ( alpha < a270 - gamma2 ) // down - left
469  {
470  lx += distlabel * cos( alpha ) - xrm;
471  ly += distlabel * sin( alpha ) - yrm;
472  }
473  else if ( alpha < a270 + gamma2 ) // down
474  {
475  ly += -distlabel - yrm;
476  //lx += -xrm/2.0 + tan(alpha+a90)*(distlabel + yrm/2);
477  lx += -xrm + ( alpha - a270 + gamma2 ) * xrm / ( 2 * gamma2 );
478  }
479  else if ( alpha < a360 )
480  {
481  lx += distlabel * cos( alpha );
482  ly += distlabel * sin( alpha ) - yrm;
483  }
484 
485  double cost;
486 
487  if ( nbp == 1 )
488  cost = 0.0001;
489  else
490  cost = 0.0001 + 0.0020 * double( icost ) / double( nbp - 1 );
491 
492  ( *lPos )[i] = new LabelPosition( i, lx, ly, xrm, yrm, angle, cost, this );
493 
494  icost += inc;
495 
496  if ( icost == nbp )
497  {
498  icost = nbp - 1;
499  inc = -2;
500  }
501  else if ( icost > nbp )
502  {
503  icost = nbp - 2;
504  inc = -2;
505  }
506 
507  }
508 
509  return nbp;
510  }
511 
512 // TODO work with squared distance by remonving call to sqrt or dist_euc2d
513  int FeaturePart::setPositionForLine( double scale, LabelPosition ***lPos, PointSet *mapShape, double delta_width )
514  {
515 #ifdef _DEBUG_
516  std::cout << "SetPosition (line) : " << layer->name << "/" << uid << std::endl;
517 #endif
518  int i;
519  int dpi = f->layer->pal->dpi;
520  double xrm, yrm;
521  double distlabel = f->distlabel;
522 
523  xrm = unit_convert( f->label_x,
524  f->layer->label_unit,
525  f->layer->pal->map_unit,
526  dpi, scale, delta_width );
527 
528  yrm = unit_convert( f->label_y,
529  f->layer->label_unit,
530  f->layer->pal->map_unit,
531  dpi, scale, delta_width );
532 
533 
534 #if 0
535  double distlabel = unit_convert( this->distlabel,
536  pal::PIXEL,
537  layer->pal->map_unit,
538  dpi, scale, delta_width );
539 #endif
540 
541 
542  double *d; // segments lengths distance bw pt[i] && pt[i+1]
543  double *ad; // absolute distance bw pt[0] and pt[i] along the line
544  double ll; // line length
545  double dist;
546  double bx, by, ex, ey;
547  int nbls;
548  double alpha;
549  double cost;
550 
551  unsigned long flags = f->layer->getArrangementFlags();
552  if ( flags == 0 )
553  flags = FLAG_ON_LINE; // default flag
554 
555  //LinkedList<PointSet*> *shapes_final;
556 
557  //shapes_final = new LinkedList<PointSet*>(ptrPSetCompare);
558 
560 
561  int nbPoints;
562  double *x;
563  double *y;
564 
565  PointSet * line = mapShape;
566 #ifdef _DEBUG_FULL_
567  std::cout << "New line of " << line->nbPoints << " points with label " << xrm << "x" << yrm << std::endl;
568 #endif
569 
570  nbPoints = line->nbPoints;
571  x = line->x;
572  y = line->y;
573 
574  d = new double[nbPoints-1];
575  ad = new double[nbPoints];
576 
577  ll = 0.0; // line length
578  for ( i = 0; i < line->nbPoints - 1; i++ )
579  {
580  if ( i == 0 )
581  ad[i] = 0;
582  else
583  ad[i] = ad[i-1] + d[i-1];
584 
585  d[i] = dist_euc2d( x[i], y[i], x[i+1], y[i+1] );
586  ll += d[i];
587  }
588 
589  ad[line->nbPoints-1] = ll;
590 
591 
592  nbls = ( int )( ll / xrm ); // ratio bw line length and label width
593 
594 #ifdef _DEBUG_FULL_
595  std::cout << "line length :" << ll << std::endl;
596  std::cout << "nblp :" << nbls << std::endl;
597 #endif
598 
599  dist = ( ll - xrm );
600 
601  double l;
602 
603  if ( nbls > 0 )
604  {
605  //dist /= nbls;
606  l = 0;
607  dist = min( yrm, xrm );
608  }
609  else // line length < label with => centering label position
610  {
611  l = - ( xrm - ll ) / 2.0;
612  dist = xrm;
613  ll = xrm;
614  }
615 
616  double birdfly;
617  double beta;
618  i = 0;
619  //for (i=0;i<nbp;i++){
620 #ifdef _DEBUG_FULL_
621  std::cout << l << " / " << ll - xrm << std::endl;
622 #endif
623  while ( l < ll - xrm )
624  {
625  // => bx, by
626  line->getPoint( d, ad, l, &bx, &by );
627  // same but l = l+xrm
628  line->getPoint( d, ad, l + xrm, &ex, &ey );
629 
630  // Label is bigger than line ...
631  if ( l < 0 )
632  birdfly = sqrt(( x[nbPoints-1] - x[0] ) * ( x[nbPoints-1] - x[0] )
633  + ( y[nbPoints-1] - y[0] ) * ( y[nbPoints-1] - y[0] ) );
634  else
635  birdfly = sqrt(( ex - bx ) * ( ex - bx ) + ( ey - by ) * ( ey - by ) );
636 
637  cost = birdfly / xrm;
638  if ( cost > 0.98 )
639  cost = 0.0001;
640  else
641  cost = ( 1 - cost ) / 100; // < 0.0001, 0.01 > (but 0.005 is already pretty much)
642 
643  // penalize positions which are further from the line's midpoint
644  double costCenter = vabs( ll / 2 - ( l + xrm / 2 ) ) / ll; // <0, 0.5>
645  cost += costCenter / 1000; // < 0, 0.0005 >
646 
647  if (( vabs( ey - by ) < EPSILON ) && ( vabs( ex - bx ) < EPSILON ) )
648  {
649  std::cout << "EPSILON " << EPSILON << std::endl;
650  std::cout << "b: " << bx << ";" << by << std::endl;
651  std::cout << "e: " << ex << ";" << ey << std::endl;
652  alpha = 0.0;
653  }
654  else
655  alpha = atan2( ey - by, ex - bx );
656 
657  beta = alpha + M_PI / 2;
658 
659 #ifdef _DEBUG_FULL_
660  std::cout << " Create new label" << std::endl;
661 #endif
662  if ( f->layer->arrangement == P_LINE )
663  {
664  // find out whether the line direction for this candidate is from right to left
665  bool isRightToLeft = ( alpha > M_PI / 2 || alpha <= -M_PI / 2 );
666  // meaning of above/below may be reversed if using line position dependent orientation
667  // and the line has right-to-left direction
668  bool reversed = (( flags & FLAG_MAP_ORIENTATION ) ? isRightToLeft : false );
669  bool aboveLine = ( !reversed && ( flags & FLAG_ABOVE_LINE ) ) || ( reversed && ( flags & FLAG_BELOW_LINE ) );
670  bool belowLine = ( !reversed && ( flags & FLAG_BELOW_LINE ) ) || ( reversed && ( flags & FLAG_ABOVE_LINE ) );
671 
672  if ( aboveLine )
673  positions->push_back( new LabelPosition( i, bx + cos( beta ) *distlabel , by + sin( beta ) *distlabel, xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
674  if ( belowLine )
675  positions->push_back( new LabelPosition( i, bx - cos( beta ) *( distlabel + yrm ) , by - sin( beta ) *( distlabel + yrm ), xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
676  if ( flags & FLAG_ON_LINE )
677  positions->push_back( new LabelPosition( i, bx - yrm*cos( beta ) / 2, by - yrm*sin( beta ) / 2, xrm, yrm, alpha, cost, this, isRightToLeft ) ); // Line
678  }
679  else if ( f->layer->arrangement == P_HORIZ )
680  {
681  positions->push_back( new LabelPosition( i, bx - xrm / 2, by - yrm / 2, xrm, yrm, 0, cost, this ) ); // Line
682  //positions->push_back( new LabelPosition(i, bx -yrm/2, by - yrm*sin(beta)/2, xrm, yrm, alpha, cost, this, line)); // Line
683  }
684  else
685  {
686  // an invalid arrangement?
687  }
688 
689  l += dist;
690 
691  i++;
692 
693  if ( nbls == 0 )
694  break;
695  }
696 
697  //delete line;
698 
699  delete[] d;
700  delete[] ad;
701 
702  int nbp = positions->size();
703  *lPos = new LabelPosition *[nbp];
704  i = 0;
705  while ( positions->size() > 0 )
706  {
707  ( *lPos )[i] = positions->pop_front();
708  i++;
709  }
710 
711  delete positions;
712 
713  return nbp;
714  }
715 
716 
717  LabelPosition* FeaturePart::curvedPlacementAtOffset( PointSet* path_positions, double* path_distances, int orientation, int index, double distance )
718  {
719  // Check that the given distance is on the given index and find the correct index and distance if not
720  while ( distance < 0 && index > 1 )
721  {
722  index--;
723  distance += path_distances[index];
724  }
725 
726  if ( index <= 1 && distance < 0 ) // We've gone off the start, fail out
727  {
728  return NULL;
729  }
730 
731  // Same thing, checking if we go off the end
732  while ( index < path_positions->nbPoints && distance > path_distances[index] )
733  {
734  distance -= path_distances[index];
735  index += 1;
736  }
737  if ( index >= path_positions->nbPoints )
738  {
739  return NULL;
740  }
741 
742  // Keep track of the initial index,distance incase we need to re-call get_placement_offset
743  int initial_index = index;
744  double initial_distance = distance;
745 
746  double string_height = f->labelInfo->label_height;
747  double old_x = path_positions->x[index-1];
748  double old_y = path_positions->y[index-1];
749 
750  double new_x = path_positions->x[index];
751  double new_y = path_positions->y[index];
752 
753  double dx = new_x - old_x;
754  double dy = new_y - old_y;
755 
756  double segment_length = path_distances[index];
757  if ( segment_length == 0 )
758  {
759  // Not allowed to place across on 0 length segments or discontinuities
760  return NULL;
761  }
762 
763  LabelPosition* slp = NULL;
764  LabelPosition* slp_tmp = NULL;
765  // current_placement = placement_result()
766  double angle = atan2( -dy, dx );
767 
768  bool orientation_forced = ( orientation != 0 ); // Whether the orientation was set by the caller
769  if ( !orientation_forced )
770  orientation = ( angle > 0.55 * M_PI || angle < -0.45 * M_PI ? -1 : 1 );
771 
772  int upside_down_char_count = 0; // Count of characters that are placed upside down.
773 
774  for ( int i = 0; i < f->labelInfo->char_num; i++ )
775  {
776  double last_character_angle = angle;
777 
778  // grab the next character according to the orientation
779  LabelInfo::CharacterInfo& ci = ( orientation > 0 ? f->labelInfo->char_info[i] : f->labelInfo->char_info[f->labelInfo->char_num-i-1] );
780 
781  // Coordinates this character will start at
782  if ( segment_length == 0 )
783  {
784  // Not allowed to place across on 0 length segments or discontinuities
785  delete slp;
786  return NULL;
787  }
788 
789  double start_x = old_x + dx * distance / segment_length;
790  double start_y = old_y + dy * distance / segment_length;
791  // Coordinates this character ends at, calculated below
792  double end_x = 0;
793  double end_y = 0;
794 
795  //std::cerr << "segment len " << segment_length << " distance " << distance << std::endl;
796  if ( segment_length - distance >= ci.width )
797  {
798  // if the distance remaining in this segment is enough, we just go further along the segment
799  distance += ci.width;
800  end_x = old_x + dx * distance / segment_length;
801  end_y = old_y + dy * distance / segment_length;
802  }
803  else
804  {
805  // If there isn't enough distance left on this segment
806  // then we need to search until we find the line segment that ends further than ci.width away
807  do
808  {
809  old_x = new_x;
810  old_y = new_y;
811  index++;
812  if ( index >= path_positions->nbPoints ) // Bail out if we run off the end of the shape
813  {
814  delete slp;
815  return NULL;
816  }
817  new_x = path_positions->x[index];
818  new_y = path_positions->y[index];
819  dx = new_x - old_x;
820  dy = new_y - old_y;
821  segment_length = path_distances[index];
822 
823  //std::cerr << "-> " << sqrt(pow(start_x - new_x,2) + pow(start_y - new_y,2)) << " vs " << ci.width << std::endl;
824 
825  }
826  while ( sqrt( pow( start_x - new_x, 2 ) + pow( start_y - new_y, 2 ) ) < ci.width ); // Distance from start_ to new_
827 
828  // Calculate the position to place the end of the character on
829  findLineCircleIntersection( start_x, start_y, ci.width, old_x, old_y, new_x, new_y, end_x, end_y );
830 
831  // Need to calculate distance on the new segment
832  distance = sqrt( pow( old_x - end_x, 2 ) + pow( old_y - end_y, 2 ) );
833  }
834 
835  // Calculate angle from the start of the character to the end based on start_/end_ position
836  angle = atan2( start_y - end_y, end_x - start_x );
837  //angle = atan2(end_y-start_y, end_x-start_x);
838 
839  // Test last_character_angle vs angle
840  // since our rendering angle has changed then check against our
841  // max allowable angle change.
842  double angle_delta = last_character_angle - angle;
843  // normalise between -180 and 180
844  while ( angle_delta > M_PI ) angle_delta -= 2 * M_PI;
845  while ( angle_delta < -M_PI ) angle_delta += 2 * M_PI;
846  if (( f->labelInfo->max_char_angle_inside > 0 && angle_delta > 0
847  && angle_delta > f->labelInfo->max_char_angle_inside*( M_PI / 180 ) )
848  || ( f->labelInfo->max_char_angle_outside < 0 && angle_delta < 0
849  && angle_delta < f->labelInfo->max_char_angle_outside*( M_PI / 180 ) ) )
850  {
851  delete slp;
852  return NULL;
853  }
854 
855  double render_angle = angle;
856 
857  double render_x = start_x;
858  double render_y = start_y;
859 
860  // Center the text on the line
861  //render_x -= ((string_height/2.0) - 1.0)*math.cos(render_angle+math.pi/2)
862  //render_y += ((string_height/2.0) - 1.0)*math.sin(render_angle+math.pi/2)
863 
864  if ( orientation < 0 )
865  {
866  // rotate in place
867  render_x += ci.width * cos( render_angle ); //- (string_height-2)*sin(render_angle);
868  render_y -= ci.width * sin( render_angle ); //+ (string_height-2)*cos(render_angle);
869  render_angle += M_PI;
870  }
871 
872  //std::cerr << "adding part: " << render_x << " " << render_y << std::endl;
873  LabelPosition* tmp = new LabelPosition( 0, render_x /*- xBase*/, render_y /*- yBase*/, ci.width, string_height, -render_angle, 0.0001, this );
874  tmp->setPartId( orientation > 0 ? i : f->labelInfo->char_num - i - 1 );
875  if ( slp == NULL )
876  slp = tmp;
877  else
878  slp_tmp->setNextPart( tmp );
879  slp_tmp = tmp;
880 
881  //current_placement.add_node(ci.character,render_x, -render_y, render_angle);
882  //current_placement.add_node(ci.character,render_x - current_placement.starting_x, render_y - current_placement.starting_y, render_angle)
883 
884  // Normalise to 0 <= angle < 2PI
885  while ( render_angle >= 2*M_PI ) render_angle -= 2 * M_PI;
886  while ( render_angle < 0 ) render_angle += 2 * M_PI;
887 
888  if ( render_angle > M_PI / 2 && render_angle < 1.5*M_PI )
889  upside_down_char_count++;
890  }
891  // END FOR
892 
893  // If we placed too many characters upside down
894  if ( upside_down_char_count >= f->labelInfo->char_num / 2.0 )
895  {
896  // if we auto-detected the orientation then retry with the opposite orientation
897  if ( !orientation_forced )
898  {
899  orientation = -orientation;
900  delete slp;
901  slp = curvedPlacementAtOffset( path_positions, path_distances, orientation, initial_index, initial_distance );
902  }
903  else
904  {
905  // Otherwise we have failed to find a placement
906  delete slp;
907  return NULL;
908  }
909  }
910 
911  return slp;
912  }
913 
914  static LabelPosition* _createCurvedCandidate( LabelPosition* lp, double angle, double dist )
915  {
916  LabelPosition* newLp = new LabelPosition( *lp );
917  newLp->offsetPosition( dist*cos( angle + M_PI / 2 ), dist*sin( angle + M_PI / 2 ) );
918  return newLp;
919  }
920 
922  {
923  // label info must be present
924  if ( f->labelInfo == NULL || f->labelInfo->char_num == 0 )
925  return 0;
926 
927  // distance calculation
928  double* path_distances = new double[mapShape->nbPoints];
929  double total_distance = 0;
930  double old_x = -1.0, old_y = -1.0;
931  for ( int i = 0; i < mapShape->nbPoints; i++ )
932  {
933  if ( i == 0 )
934  path_distances[i] = 0;
935  else
936  path_distances[i] = sqrt( pow( old_x - mapShape->x[i], 2 ) + pow( old_y - mapShape->y[i], 2 ) );
937  old_x = mapShape->x[i];
938  old_y = mapShape->y[i];
939 
940  total_distance += path_distances[i];
941  }
942 
943  if ( total_distance == 0 )
944  {
945  delete[] path_distances;
946  return 0;
947  }
948 
950  double delta = max( f->labelInfo->label_height, total_distance / 10.0 );
951 
952  unsigned long flags = f->layer->getArrangementFlags();
953  if ( flags == 0 )
954  flags = FLAG_ON_LINE; // default flag
955 
956  // generate curved labels
957  for ( int i = 0; i*delta < total_distance; i++ )
958  {
959  LabelPosition* slp = curvedPlacementAtOffset( mapShape, path_distances, 0, 1, i * delta );
960 
961  if ( slp )
962  {
963  // evaluate cost
964  double angle_diff = 0.0, angle_last = 0.0, diff;
965  LabelPosition* tmp = slp;
966  double sin_avg = 0, cos_avg = 0;
967  while ( tmp )
968  {
969  if ( tmp != slp ) // not first?
970  {
971  diff = fabs( tmp->getAlpha() - angle_last );
972  if ( diff > 2*M_PI ) diff -= 2 * M_PI;
973  diff = min( diff, 2 * M_PI - diff ); // difference 350 deg is actually just 10 deg...
974  angle_diff += diff;
975  }
976 
977  sin_avg += sin( tmp->getAlpha() );
978  cos_avg += cos( tmp->getAlpha() );
979  angle_last = tmp->getAlpha();
980  tmp = tmp->getNextPart();
981  }
982 
983  double angle_diff_avg = f->labelInfo->char_num > 1 ? ( angle_diff / ( f->labelInfo->char_num - 1 ) ) : 0; // <0, pi> but pi/8 is much already
984  double cost = angle_diff_avg / 100; // <0, 0.031 > but usually <0, 0.003 >
985  if ( cost < 0.0001 ) cost = 0.0001;
986 
987  // penalize positions which are further from the line's midpoint
988  double labelCenter = ( i * delta ) + f->label_x / 2;
989  double costCenter = vabs( total_distance / 2 - labelCenter ) / total_distance; // <0, 0.5>
990  cost += costCenter / 1000; // < 0, 0.0005 >
991  //std::cerr << "cost " << angle_diff << " vs " << costCenter << std::endl;
992  slp->setCost( cost );
993 
994 
995  // average angle is calculated with respect to periodicity of angles
996  double angle_avg = atan2( sin_avg / f->labelInfo->char_num, cos_avg / f->labelInfo->char_num );
997  // displacement
998  if ( flags & FLAG_ABOVE_LINE )
999  positions->push_back( _createCurvedCandidate( slp, angle_avg, f->distlabel ) );
1000  if ( flags & FLAG_ON_LINE )
1001  positions->push_back( _createCurvedCandidate( slp, angle_avg, -f->labelInfo->label_height / 2 ) );
1002  if ( flags & FLAG_BELOW_LINE )
1003  positions->push_back( _createCurvedCandidate( slp, angle_avg, -f->labelInfo->label_height - f->distlabel ) );
1004 
1005  // delete original candidate
1006  delete slp;
1007  }
1008  }
1009 
1010 
1011  int nbp = positions->size();
1012  ( *lPos ) = new LabelPosition*[nbp];
1013  for ( int i = 0; i < nbp; i++ )
1014  {
1015  ( *lPos )[i] = positions->pop_front();
1016  }
1017  delete positions;
1018  delete[] path_distances;
1019 
1020  return nbp;
1021  }
1022 
1023 
1024 
1025 
1026  /*
1027  * seg 2
1028  * pt3 ____________pt2
1029  * ¦ ¦
1030  * ¦ ¦
1031  * seg 3 ¦ BBOX ¦ seg 1
1032  * ¦ ¦
1033  * ¦____________¦
1034  * pt0 seg 0 pt1
1035  *
1036  */
1037 
1038  int FeaturePart::setPositionForPolygon( double scale, LabelPosition ***lPos, PointSet *mapShape, double delta_width )
1039  {
1040 
1041 #ifdef _DEBUG_
1042  std::cout << "SetPosition (polygon) : " << layer->name << "/" << uid << std::endl;
1043 #endif
1044 
1045  int i;
1046  int j;
1047 
1048  double xrm;
1049  double yrm;
1050 
1051  xrm = unit_convert( f->label_x,
1052  f->layer->label_unit,
1053  f->layer->pal->map_unit,
1054  f->layer->pal->dpi, scale, delta_width );
1055 
1056  yrm = unit_convert( f->label_y,
1057  f->layer->label_unit,
1058  f->layer->pal->map_unit,
1059  f->layer->pal->dpi, scale, delta_width );
1060 
1061  //print();
1062 
1063  //LinkedList<PointSet*> *shapes_toCut;
1064  LinkedList<PointSet*> *shapes_toProcess;
1065  LinkedList<PointSet*> *shapes_final;
1066 
1067  //shapes_toCut = new LinkedList<PointSet*>(ptrPSetCompare);
1068  shapes_toProcess = new LinkedList<PointSet*> ( ptrPSetCompare );
1069  shapes_final = new LinkedList<PointSet*> ( ptrPSetCompare );
1070 
1071  mapShape->parent = NULL;
1072 
1073  shapes_toProcess->push_back( mapShape );
1074 
1075  splitPolygons( shapes_toProcess, shapes_final, xrm, yrm, f->uid );
1076 
1077 
1078  delete shapes_toProcess;
1079 
1080  int nbp;
1081 
1082  if ( shapes_final->size() > 0 )
1083  {
1085 
1086  int id = 0; // ids for candidates
1087  double dlx, dly; // delta from label center and bottom-left corner
1088  double alpha = 0.0; // rotation for the label
1089  double px, py;
1090  double dx;
1091  double dy;
1092  int bbid;
1093  double beta;
1094  double diago = sqrt( xrm * xrm / 4.0 + yrm * yrm / 4 );
1095  double rx, ry;
1096  CHullBox **boxes = new CHullBox*[shapes_final->size()];
1097  j = 0;
1098 
1099  // Compute bounding box foreach finalShape
1100  while ( shapes_final->size() > 0 )
1101  {
1102  PointSet *shape = shapes_final->pop_front();
1103  boxes[j] = shape->compute_chull_bbox();
1104 
1105  if ( shape->parent )
1106  delete shape;
1107 
1108  j++;
1109  }
1110 
1111  //dx = dy = min( yrm, xrm ) / 2;
1112  dx = xrm / 2.0;
1113  dy = yrm / 2.0;
1114 
1115 
1116  int num_try = 0;
1117  int max_try = 10;
1118  do
1119  {
1120  for ( bbid = 0; bbid < j; bbid++ )
1121  {
1122  CHullBox *box = boxes[bbid];
1123 
1124  if (( box->length * box->width ) > ( xmax - xmin ) *( ymax - ymin ) *5 )
1125  {
1126  std::cout << "Very Large BBOX (should never occur : bug-report please)" << std::endl;
1127  std::cout << " Box size: " << box->length << "/" << box->width << std::endl;
1128  std::cout << " Alpha: " << alpha << " " << alpha * 180 / M_PI << std::endl;
1129  std::cout << " Dx;Dy: " << dx << " " << dy << std::endl;
1130  std::cout << " LabelSizerm: " << xrm << " " << yrm << std::endl;
1131  std::cout << " LabelSizeUn: " << f->label_x << " " << f->label_y << std::endl;
1132  continue;
1133  }
1134 
1135 #ifdef _DEBUG_FULL_
1136  std::cout << "New BBox : " << bbid << std::endl;
1137  for ( i = 0; i < 4; i++ )
1138  {
1139  std::cout << box->x[i] << "\t" << box->y[i] << std::endl;
1140  }
1141 #endif
1142 
1143  bool enoughPlace = false;
1144  if ( f->layer->getArrangement() == P_FREE )
1145  {
1146  enoughPlace = true;
1147  px = ( box->x[0] + box->x[2] ) / 2 - xrm;
1148  py = ( box->y[0] + box->y[2] ) / 2 - yrm;
1149  int i, j;
1150 
1151  // Virtual label: center on bbox center, label size = 2x original size
1152  // alpha = 0.
1153  // If all corner are in bbox then place candidates horizontaly
1154  for ( rx = px, i = 0; i < 2; rx = rx + 2 * xrm, i++ )
1155  {
1156  for ( ry = py, j = 0; j < 2; ry = ry + 2 * yrm, j++ )
1157  {
1158  // TODO should test with the polyone insteand of the bbox
1159  if ( !isPointInPolygon( 4, box->x, box->y, rx, ry ) )
1160  {
1161  enoughPlace = false;
1162  break;
1163  }
1164  }
1165  if ( !enoughPlace )
1166  {
1167  break;
1168  }
1169  }
1170 
1171  } // arrangement== FREE ?
1172 
1173  if ( f->layer->getArrangement() == P_HORIZ || enoughPlace )
1174  {
1175  alpha = 0.0; // HORIZ
1176  }
1177  else if ( box->length > 1.5*xrm && box->width > 1.5*xrm )
1178  {
1179  if ( box->alpha <= M_PI / 4 )
1180  {
1181  alpha = box->alpha;
1182  }
1183  else
1184  {
1185  alpha = box->alpha - M_PI / 2;
1186  }
1187  }
1188  else if ( box->length > box->width )
1189  {
1190  alpha = box->alpha - M_PI / 2;
1191  }
1192  else
1193  {
1194  alpha = box->alpha;
1195  }
1196 
1197  beta = atan2( yrm, xrm ) + alpha;
1198 
1199 
1200  //alpha = box->alpha;
1201 
1202  // delta from label center and down-left corner
1203  dlx = cos( beta ) * diago;
1204  dly = sin( beta ) * diago;
1205 
1206 
1207  double px0, py0;
1208 
1209  px0 = box->width / 2.0;
1210  py0 = box->length / 2.0;
1211 
1212  px0 -= ceil( px0 / dx ) * dx;
1213  py0 -= ceil( py0 / dy ) * dy;
1214 
1215  for ( px = px0; px <= box->width; px += dx )
1216  {
1217  for ( py = py0; py <= box->length; py += dy )
1218  {
1219 
1220  rx = cos( box->alpha ) * px + cos( box->alpha - M_PI / 2 ) * py;
1221  ry = sin( box->alpha ) * px + sin( box->alpha - M_PI / 2 ) * py;
1222 
1223  rx += box->x[0];
1224  ry += box->y[0];
1225 
1226  // Only accept candidate that center is in the polygon
1227  if ( isPointInPolygon( mapShape->nbPoints, mapShape->x, mapShape->y, rx, ry ) )
1228  {
1229  // cost is set to minimal value, evaluated later
1230  positions->push_back( new LabelPosition( id++, rx - dlx, ry - dly , xrm, yrm, alpha, 0.0001, this ) ); // Polygon
1231  }
1232  }
1233  }
1234  } // forall box
1235 
1236  nbp = positions->size();
1237  if ( nbp == 0 )
1238  {
1239  dx /= 2;
1240  dy /= 2;
1241  num_try++;
1242  }
1243  }
1244  while ( nbp == 0 && num_try < max_try );
1245 
1246  nbp = positions->size();
1247 
1248  ( *lPos ) = new LabelPosition*[nbp];
1249  for ( i = 0; i < nbp; i++ )
1250  {
1251  ( *lPos )[i] = positions->pop_front();
1252  }
1253 
1254  for ( bbid = 0; bbid < j; bbid++ )
1255  {
1256  delete boxes[bbid];
1257  }
1258 
1259  delete[] boxes;
1260  delete positions;
1261  }
1262  else
1263  {
1264  nbp = 0;
1265  }
1266 
1267  delete shapes_final;
1268 
1269 #ifdef _DEBUG_FULL_
1270  std::cout << "NbLabelPosition: " << nbp << std::endl;
1271 #endif
1272  return nbp;
1273  }
1274 
1276  {
1277  int i, j;
1278  std::cout << "Geometry id : " << f->uid << std::endl;
1279  std::cout << "Type: " << type << std::endl;
1280  if ( x && y )
1281  {
1282  for ( i = 0; i < nbPoints; i++ )
1283  std::cout << x[i] << ", " << y[i] << std::endl;
1284  std::cout << "Obstacle: " << nbHoles << std::endl;
1285  for ( i = 0; i < nbHoles; i++ )
1286  {
1287  std::cout << " obs " << i << std::endl;
1288  for ( j = 0; j < holes[i]->nbPoints; j++ )
1289  {
1290  std::cout << holes[i]->x[j] << ";" << holes[i]->y[j] << std::endl;
1291  }
1292  }
1293  }
1294 
1295  std::cout << std::endl;
1296  }
1297 
1298  int FeaturePart::setPosition( double scale, LabelPosition ***lPos,
1299  double bbox_min[2], double bbox_max[2],
1300  PointSet *mapShape, RTree<LabelPosition*, double, 2, double> *candidates
1301 #ifdef _EXPORT_MAP_
1302  , std::ofstream &svgmap
1303 #endif
1304  )
1305  {
1306  int nbp = 0;
1307  int i;
1308  double bbox[4];
1309 
1310 #ifdef _EXPORT_MAP_
1311  int dpi = layer->pal->getDpi();
1312 #endif
1313 
1314  bbox[0] = bbox_min[0];
1315  bbox[1] = bbox_min[1];
1316  bbox[2] = bbox_max[0];
1317  bbox[3] = bbox_max[1];
1318 
1319  double delta = bbox_max[0] - bbox_min[0];
1320  double angle = f->fixedRotation ? f->fixedAngle : 0.0;
1321 
1322  if ( f->fixedPosition() )
1323  {
1324  nbp = 1;
1325  *lPos = new LabelPosition *[nbp];
1326  ( *lPos )[0] = new LabelPosition( 0, f->fixedPosX, f->fixedPosY, f->label_x, f->label_y, angle, 0.0, this );
1327  }
1328  else
1329  {
1330  switch ( type )
1331  {
1332  case GEOS_POINT:
1333  if ( f->layer->getArrangement() == P_POINT_OVER )
1334  nbp = setPositionOverPoint( x[0], y[0], scale, lPos, delta, angle );
1335  else
1336  nbp = setPositionForPoint( x[0], y[0], scale, lPos, delta, angle );
1337  break;
1338  case GEOS_LINESTRING:
1339  if ( f->layer->getArrangement() == P_CURVED )
1340  nbp = setPositionForLineCurved( lPos, mapShape );
1341  else
1342  nbp = setPositionForLine( scale, lPos, mapShape, delta );
1343  break;
1344 
1345  case GEOS_POLYGON:
1346  switch ( f->layer->getArrangement() )
1347  {
1348  case P_POINT:
1349  case P_POINT_OVER:
1350  double cx, cy;
1351  mapShape->getCentroid( cx, cy, f->layer->getCentroidInside() );
1352  if ( f->layer->getArrangement() == P_POINT_OVER )
1353  nbp = setPositionOverPoint( cx, cy, scale, lPos, delta, angle );
1354  else
1355  nbp = setPositionForPoint( cx, cy, scale, lPos, delta, angle );
1356  break;
1357  case P_LINE:
1358  nbp = setPositionForLine( scale, lPos, mapShape, delta );
1359  break;
1360  default:
1361  nbp = setPositionForPolygon( scale, lPos, mapShape, delta );
1362  break;
1363  }
1364  }
1365  }
1366 
1367  int rnbp = nbp;
1368 
1369  // purge candidates that are outside the bbox
1370  for ( i = 0; i < nbp; i++ )
1371  {
1372  bool outside = false;
1373  if ( f->layer->pal->getShowPartial() )
1374  outside = !( *lPos )[i]->isIntersect( bbox );
1375  else
1376  outside = !( *lPos )[i]->isInside( bbox );
1377  if ( outside )
1378  {
1379  rnbp--;
1380  ( *lPos )[i]->setCost( DBL_MAX ); // infinite cost => do not use
1381  }
1382  else // this one is OK
1383  {
1384  ( *lPos )[i]->insertIntoIndex( candidates );
1385  }
1386  }
1387 
1388  sort(( void** )( *lPos ), nbp, LabelPosition::costGrow );
1389 
1390  for ( i = rnbp; i < nbp; i++ )
1391  {
1392  delete( *lPos )[i];
1393  }
1394 
1395  return rnbp;
1396  }
1397 
1398  void FeaturePart::addSizePenalty( int nbp, LabelPosition** lPos, double bbx[4], double bby[4] )
1399  {
1400  int geomType = GEOSGeomTypeId( the_geom );
1401 
1402  double sizeCost = 0;
1403  if ( geomType == GEOS_LINESTRING )
1404  {
1405  double length;
1406  if ( GEOSLength( the_geom, &length ) != 1 )
1407  return; // failed to calculate length
1408  double bbox_length = max( bbx[2] - bbx[0], bby[2] - bby[0] );
1409  if ( length >= bbox_length / 4 )
1410  return; // the line is longer than quarter of height or width - don't penalize it
1411 
1412  sizeCost = 1 - ( length / ( bbox_length / 4 ) ); // < 0,1 >
1413  }
1414  else if ( geomType == GEOS_POLYGON )
1415  {
1416  double area;
1417  if ( GEOSArea( the_geom, &area ) != 1 )
1418  return;
1419  double bbox_area = ( bbx[2] - bbx[0] ) * ( bby[2] - bby[0] );
1420  if ( area >= bbox_area / 16 )
1421  return; // covers more than 1/16 of our view - don't penalize it
1422 
1423  sizeCost = 1 - ( area / ( bbox_area / 16 ) ); // < 0, 1 >
1424  }
1425  else
1426  return; // no size penalty for points
1427 
1428  //std::cout << "size cost " << sizeCost << std::endl;
1429 
1430  // apply the penalty
1431  for ( int i = 0; i < nbp; i++ )
1432  {
1433  lPos[i]->setCost( lPos[i]->getCost() + sizeCost / 100 );
1434  }
1435  }
1436 
1438  {
1439  return ( GEOSTouches( the_geom, p2->the_geom ) == 1 );
1440  }
1441 
1443  {
1444  GEOSGeometry* g1 = GEOSGeom_clone( the_geom );
1445  GEOSGeometry* g2 = GEOSGeom_clone( other->the_geom );
1446  GEOSGeometry* geoms[2] = { g1, g2 };
1447  GEOSGeometry* g = GEOSGeom_createCollection( GEOS_MULTILINESTRING, geoms, 2 );
1448  GEOSGeometry* gTmp = GEOSLineMerge( g );
1449  GEOSGeom_destroy( g );
1450 
1451  if ( GEOSGeomTypeId( gTmp ) != GEOS_LINESTRING )
1452  {
1453  // sometimes it's not possible to merge lines (e.g. they don't touch at endpoints)
1454  GEOSGeom_destroy( gTmp );
1455  return false;
1456  }
1457 
1458  if ( ownsGeom ) // delete old geometry if we own it
1459  GEOSGeom_destroy( the_geom );
1460  // set up new geometry
1461  the_geom = gTmp;
1462  ownsGeom = true;
1463 
1464  deleteCoords();
1466  return true;
1467  }
1468 
1469 } // end namespace pal
Arrangement arrangement
optional flags used for some placement methods
Definition: layer.h:112
void getCentroid(double &px, double &py, bool forceInside=false)
Definition: pointset.cpp:959
int reorderPolygon(int nbPoints, double *x, double *y)
double fixedAngle
Definition: feature.h:124
double length
Definition: pointset.h:76
static unsigned index
Units map_unit
Definition: pal.h:136
double fixedPosY
Definition: feature.h:115
bool fixedRotation
Definition: feature.h:123
double max_char_angle_outside
Definition: feature.h:73
static void splitPolygons(LinkedList< PointSet * > *shapes_toProcess, LinkedList< PointSet * > *shapes_final, double xrm, double yrm, char *uid)
Definition: pointset.cpp:196
void setCost(double newCost)
Modify candidate's cost.
A layer of spacial entites.
Definition: layer.h:65
double offsetPosX
Definition: feature.h:120
bool ptrPSetCompare(PointSet *a, PointSet *b)
Definition: util.h:240
void offsetPosition(double xOffset, double yOffset)
shift the label by specified offset
friend class LabelPosition
Definition: pointset.h:95
static LabelPosition * _createCurvedCandidate(LabelPosition *lp, double angle, double dist)
Definition: feature.cpp:914
double quadOffsetY
Definition: feature.h:118
static bool costGrow(void *l, void *r)
CHullBox * compute_chull_bbox()
Definition: pointset.cpp:598
void removeDuplicatePoints()
find duplicate (or nearly duplicate points) and remove them.
Definition: feature.cpp:202
Layer * getLayer()
return the layer that feature belongs to
Definition: feature.cpp:249
bool offsetPos
Definition: feature.h:119
int setPositionOverPoint(double x, double y, double scale, LabelPosition ***lPos, double delta_width, double angle)
generate one candidate over specified point
Definition: feature.cpp:260
double distlabel
Definition: feature.h:108
void addSizePenalty(int nbp, LabelPosition **lPos, double bbx[4], double bby[4])
Definition: feature.cpp:1398
bool getCentroidInside() const
Definition: layer.h:300
arranges candidates around a point (centroid for polygon)
Definition: pal.h:95
bool isPointInPolygon(int npol, double *xp, double *yp, double x, double y)
CharacterInfo * char_info
Definition: feature.h:76
int dpi
Definition: pal.h:163
int setPositionForLine(double scale, LabelPosition ***lPos, PointSet *mapShape, double delta_width)
generate candidates for line feature Generate candidates for line features
Definition: feature.cpp:513
double unit_convert(double x, Units from, Units to, int dpi, double scale, double delta_canvas_width)
Definition: util.h:120
void deleteCoords()
Definition: pointset.cpp:137
Layer * layer
Definition: feature.h:104
double width
Definition: pointset.h:75
Feature * f
Definition: feature.h:142
void getBoundingBox(double amin[2], double amax[2]) const
return bounding box - amin: xmin,ymin - amax: xmax,ymax
FeaturePart(Feature *feat, const GEOSGeometry *geom)
create a new generic feature
Definition: feature.cpp:81
Units label_unit
Definition: layer.h:106
PointSet ** holes
Definition: feature.h:145
virtual ~FeaturePart()
Delete the feature.
Definition: feature.cpp:98
bool mergeWithFeaturePart(FeaturePart *other)
merge other (connected) part with this one and save the result in this part (other is unchanged)...
Definition: feature.cpp:1442
double getAlpha() const
get alpha
PointSet * parent
Definition: pointset.h:111
double * x
Definition: pointset.h:102
double ymax
Definition: pointset.h:122
double xmin
Definition: pointset.h:119
PointSet * holeOf
Definition: pointset.h:110
double ymin
Definition: pointset.h:121
int setPosition(double scale, LabelPosition ***lPos, double bbox_min[2], double bbox_max[2], PointSet *mapShape, RTree< LabelPosition *, double, 2, double > *candidates)
generic method to generate candidates This method will call either setPositionFromPoint(), setPositionFromLine or setPositionFromPolygon
Definition: feature.cpp:1298
void print()
Print feature information Print feature unique id, geometry type, points, and holes on screen...
Definition: feature.cpp:1275
double quadOffsetX
Definition: feature.h:117
int setPositionForLineCurved(LabelPosition ***lPos, PointSet *mapShape)
Generate curved candidates for line features.
Definition: feature.cpp:921
double dist_euc2d(double x1, double y1, double x2, double y2)
Definition: geomfunction.h:56
bool isConnected(FeaturePart *p2)
check whether this part is connected with some other part
Definition: feature.cpp:1437
arranges candidates over a point (centroid for polygon)
Definition: pal.h:97
double label_height
Definition: feature.h:74
Only for lines, labels along the line.
Definition: pal.h:99
double offsetPosY
Definition: feature.h:121
LabelPosition * getNextPart() const
bool quadOffset
Definition: feature.h:116
const char * getUID()
get the unique id of the feature
Definition: feature.cpp:255
Main class to handle feature.
Definition: feature.h:138
pixel [px]
Definition: pal.h:67
int setPositionForPoint(double x, double y, double scale, LabelPosition ***lPos, double delta_width, double angle)
generate candidates for point feature Generate candidates for point features
Definition: feature.cpp:346
void setPartId(int id)
Arrangement getArrangement()
get arrangement policy
Definition: layer.cpp:151
double ANALYSIS_EXPORT angle(Point3D *p1, Point3D *p2, Point3D *p3, Point3D *p4)
Calculates the angle between two segments (in 2 dimension, z-values are ignored)
void extractCoords(const GEOSGeometry *geom)
read coordinates from a GEOS geom
Definition: feature.cpp:121
int setPositionForPolygon(double scale, LabelPosition ***lPos, PointSet *mapShape, double delta_width)
generate candidates for point feature Generate candidates for point features
Definition: feature.cpp:1038
int min(int a, int b)
Definition: util.h:93
double * y
Definition: pointset.h:103
LabelPosition * curvedPlacementAtOffset(PointSet *path_positions, double *path_distances, int orientation, int index, double distance)
Definition: feature.cpp:717
bool getShowPartial()
Get flag show partial label.
Definition: pal.cpp:970
void sort(double *heap, int *x, int *y, int N)
Definition: util.cpp:72
GEOSGeometry * the_geom
Definition: feature.h:147
Pal * pal
Definition: layer.h:96
void setNextPart(LabelPosition *next)
LabelInfo * labelInfo
Definition: feature.h:109
double x[4]
Definition: pointset.h:70
bool ptrLPosCompare(LabelPosition *a, LabelPosition *b)
Definition: util.h:235
double label_y
Definition: feature.h:107
double y[4]
Definition: pointset.h:71
double max_char_angle_inside
Definition: feature.h:72
char * uid
Definition: feature.h:111
double label_x
Definition: feature.h:106
#define EPSILON
Definition: util.h:84
void getPoint(double *d, double *ad, double dl, double *px, double *py)
Definition: pointset.h:190
Only for polygon, arranges candidates with respect of polygon orientation.
Definition: pal.h:100
void findLineCircleIntersection(double cx, double cy, double radius, double x1, double y1, double x2, double y2, double &xRes, double &yRes)
LabelPositon is a candidate feature label position.
Definition: labelposition.h:53
Feature(Layer *l, const char *id, PalGeometry *userG, double lx, double ly)
Definition: feature.cpp:64
Interface that allows Pal to access user's geometries.
Definition: palgeometry.h:42
int point_p
maximum # candidates for a point
Definition: pal.h:141
double alpha
Definition: pointset.h:73
#define M_PI
Definition: feature.cpp:59
double xmax
Definition: pointset.h:120
int max(int a, int b)
Definition: util.h:87
double fixedPosX
Definition: feature.h:114
int char_num
Definition: feature.h:75
bool fixedPosition() const
Definition: feature.h:96
double vabs(double x)
Definition: util.h:99
unsigned long getArrangementFlags() const
Definition: layer.h:185