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