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