QGIS API Documentation  2.11.0-Master
labelposition.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 #define _CRT_SECURE_NO_DEPRECATE
31 
32 #include <iostream>
33 #include <fstream>
34 #include <cmath>
35 #include <cstring>
36 #include <cfloat>
37 
38 #include "layer.h"
39 #include "pal.h"
40 #include "costcalculator.h"
41 #include "feature.h"
42 #include "geomfunction.h"
43 #include "labelposition.h"
44 
45 #ifndef M_PI
46 #define M_PI 3.1415926535897931159979634685
47 #endif
48 
49 
50 namespace pal
51 {
52  LabelPosition::LabelPosition( int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed, Quadrant quadrant )
53  : id( id )
54  , cost( cost )
55  , feature( feature )
56  , probFeat( 0 )
57  , nbOverlap( 0 )
58  , alpha( alpha )
59  , w( w )
60  , h( h )
61  , nextPart( NULL )
62  , partId( -1 )
63  , reversed( isReversed )
64  , upsideDown( false )
65  , quadrant( quadrant )
66  {
67 
68  // alpha take his value bw 0 and 2*pi rad
69  while ( this->alpha > 2*M_PI )
70  this->alpha -= 2 * M_PI;
71 
72  while ( this->alpha < 0 )
73  this->alpha += 2 * M_PI;
74 
75  double beta = this->alpha + ( M_PI / 2 );
76 
77  double dx1, dx2, dy1, dy2;
78 
79  double tx, ty;
80 
81  dx1 = cos( this->alpha ) * w;
82  dy1 = sin( this->alpha ) * w;
83 
84  dx2 = cos( beta ) * h;
85  dy2 = sin( beta ) * h;
86 
87  x[0] = x1;
88  y[0] = y1;
89 
90  x[1] = x1 + dx1;
91  y[1] = y1 + dy1;
92 
93  x[2] = x1 + dx1 + dx2;
94  y[2] = y1 + dy1 + dy2;
95 
96  x[3] = x1 + dx2;
97  y[3] = y1 + dy2;
98 
99  // upside down ? (curved labels are always correct)
100  if ( feature->getLayer()->getArrangement() != P_CURVED &&
101  this->alpha > M_PI / 2 && this->alpha <= 3*M_PI / 2 )
102  {
103  bool uprightLabel = false;
104 
105  switch ( feature->getLayer()->getUpsidedownLabels() )
106  {
107  case Layer::Upright:
108  uprightLabel = true;
109  break;
110  case Layer::ShowDefined:
111  // upright only dynamic labels
112  if ( !feature->getFixedRotation() || ( !feature->getFixedPosition() && feature->getLabelAngle() == 0.0 ) )
113  {
114  uprightLabel = true;
115  }
116  break;
117  case Layer::ShowAll:
118  break;
119  default:
120  uprightLabel = true;
121  }
122 
123  if ( uprightLabel )
124  {
125  tx = x[0];
126  ty = y[0];
127 
128  x[0] = x[2];
129  y[0] = y[2];
130 
131  x[2] = tx;
132  y[2] = ty;
133 
134  tx = x[1];
135  ty = y[1];
136 
137  x[1] = x[3];
138  y[1] = y[3];
139 
140  x[3] = tx;
141  y[3] = ty;
142 
143  if ( this->alpha < M_PI )
144  this->alpha += M_PI;
145  else
146  this->alpha -= M_PI;
147 
148  // labels with text shown upside down are not classified as upsideDown,
149  // only those whose boundary points have been inverted
150  upsideDown = true;
151  }
152  }
153  }
154 
156  {
157  id = other.id;
158  cost = other.cost;
159  feature = other.feature;
160  probFeat = other.probFeat;
161  nbOverlap = other.nbOverlap;
162 
163  memcpy( x, other.x, sizeof( double )*4 );
164  memcpy( y, other.y, sizeof( double )*4 );
165  alpha = other.alpha;
166  w = other.w;
167  h = other.h;
168 
169  if ( other.nextPart )
170  nextPart = new LabelPosition( *other.nextPart );
171  else
172  nextPart = NULL;
173  partId = other.partId;
174  upsideDown = other.upsideDown;
175  reversed = other.reversed;
176  quadrant = other.quadrant;
177  }
178 
179  bool LabelPosition::isIn( double *bbox )
180  {
181  int i;
182 
183  for ( i = 0; i < 4; i++ )
184  {
185  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
186  y[i] >= bbox[1] && y[i] <= bbox[3] )
187  return true;
188  }
189 
190  if ( nextPart )
191  return nextPart->isIn( bbox );
192  else
193  return false;
194 
195  }
196 
197  bool LabelPosition::isIntersect( double *bbox )
198  {
199  int i;
200 
201  for ( i = 0; i < 4; i++ )
202  {
203  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
204  y[i] >= bbox[1] && y[i] <= bbox[3] )
205  return true;
206  }
207 
208  if ( nextPart )
209  return nextPart->isIntersect( bbox );
210  else
211  return false;
212  }
213 
214  bool LabelPosition::isInside( double *bbox )
215  {
216  for ( int i = 0; i < 4; i++ )
217  {
218  if ( !( x[i] >= bbox[0] && x[i] <= bbox[2] &&
219  y[i] >= bbox[1] && y[i] <= bbox[3] ) )
220  return false;
221  }
222 
223  if ( nextPart )
224  return nextPart->isInside( bbox );
225  else
226  return true;
227 
228  }
229 
231  {
232  std::cout << feature->getLayer()->getName() << "/" << feature->getUID() << "/" << id;
233  std::cout << " cost: " << cost;
234  std::cout << " alpha" << alpha << std::endl;
235  std::cout << x[0] << ", " << y[0] << std::endl;
236  std::cout << x[1] << ", " << y[1] << std::endl;
237  std::cout << x[2] << ", " << y[2] << std::endl;
238  std::cout << x[3] << ", " << y[3] << std::endl;
239  std::cout << std::endl;
240  }
241 
243  {
244  if ( this->probFeat == lp->probFeat ) // bugfix #1
245  return false; // always overlaping itself !
246 
247  if ( nextPart == NULL && lp->nextPart == NULL )
248  return isInConflictSinglePart( lp );
249  else
250  return isInConflictMultiPart( lp );
251  }
252 
254  {
255  // TODO: add bounding box test to possibly avoid cross product calculation
256 
257  int i, i2, j;
258  int d1, d2;
259  double cp1, cp2;
260 
261  for ( i = 0; i < 4; i++ )
262  {
263  i2 = ( i + 1 ) % 4;
264  d1 = -1;
265  d2 = -1;
266 
267  for ( j = 0; j < 4; j++ )
268  {
269  cp1 = cross_product( x[i], y[i], x[i2], y[i2], lp->x[j], lp->y[j] );
270  if ( cp1 > 0 )
271  {
272  d1 = 1;
273  }
274  cp2 = cross_product( lp->x[i], lp->y[i],
275  lp->x[i2], lp->y[i2],
276  x[j], y[j] );
277 
278  if ( cp2 > 0 )
279  {
280  d2 = 1;
281  }
282  }
283 
284  if ( d1 == -1 || d2 == -1 ) // disjoint
285  return false;
286  }
287  return true;
288  }
289 
291  {
292  // check all parts against all parts of other one
293  LabelPosition* tmp1 = this;
294  while ( tmp1 )
295  {
296  // check tmp1 against parts of other label
297  LabelPosition* tmp2 = lp;
298  while ( tmp2 )
299  {
300  if ( tmp1->isInConflictSinglePart( tmp2 ) )
301  return true;
302  tmp2 = tmp2->nextPart;
303  }
304 
305  tmp1 = tmp1->nextPart;
306  }
307  return false; // no conflict found
308  }
309 
310  void LabelPosition::offsetPosition( double xOffset, double yOffset )
311  {
312  for ( int i = 0; i < 4; i++ )
313  {
314  x[i] += xOffset;
315  y[i] += yOffset;
316  }
317 
318  if ( nextPart )
319  nextPart->offsetPosition( xOffset, yOffset );
320  }
321 
322 
324  {
325  return id;
326  }
327 
328  double LabelPosition::getX( int i ) const
329  {
330  return ( i >= 0 && i < 4 ? x[i] : -1 );
331  }
332 
333  double LabelPosition::getY( int i ) const
334  {
335  return ( i >= 0 && i < 4 ? y[i] : -1 );
336  }
337 
338  double LabelPosition::getAlpha() const
339  {
340  return alpha;
341  }
342 
343  double LabelPosition::getCost() const
344  {
345  return cost;
346  }
347 
349  {
350  if ( cost >= 1 )
351  {
352  std::cout << " Warning: lp->cost == " << cost << " (from feat: " << feature->getUID() << "/" << getLayerName() << ")" << std::endl;
353  cost -= int ( cost ); // label cost up to 1
354  }
355  }
356 
358  {
359  return feature;
360  }
361 
362  void LabelPosition::getBoundingBox( double amin[2], double amax[2] ) const
363  {
364  if ( nextPart )
365  {
366  //std::cout << "using next part" <<
367  nextPart->getBoundingBox( amin, amax );
368  }
369  else
370  {
371  amin[0] = DBL_MAX;
372  amax[0] = -DBL_MAX;
373  amin[1] = DBL_MAX;
374  amax[1] = -DBL_MAX;
375  }
376  for ( int c = 0; c < 4; c++ )
377  {
378  if ( x[c] < amin[0] )
379  amin[0] = x[c];
380  if ( x[c] > amax[0] )
381  amax[0] = x[c];
382  if ( y[c] < amin[1] )
383  amin[1] = y[c];
384  if ( y[c] > amax[1] )
385  amax[1] = y[c];
386  }
387  }
388 
390  {
391  return feature->getLayer()->name;
392  }
393 
394  bool LabelPosition::costShrink( void *l, void *r )
395  {
396  return (( LabelPosition* ) l )->cost < (( LabelPosition* ) r )->cost;
397  }
398 
399  bool LabelPosition::costGrow( void *l, void *r )
400  {
401  return (( LabelPosition* ) l )->cost > (( LabelPosition* ) r )->cost;
402  }
403 
404 
406  {
408 
409  LabelPosition *lp = pCost->getLabel();
410  if (( feat == lp->feature ) || ( feat->getHoleOf() && feat->getHoleOf() != lp->feature ) )
411  {
412  return true;
413  }
414 
415  pCost->update( feat );
416 
417  return true;
418  }
419 
420 
422  {
423  double amin[2];
424  double amax[2];
425  getBoundingBox( amin, amax );
426  index->Remove( amin, amax, this );
427  }
428 
429 
431  {
432  double amin[2];
433  double amax[2];
434  getBoundingBox( amin, amax );
435  index->Insert( amin, amax, this );
436  }
437 
438 
440 
442  {
443  PointSet *feat = (( PruneCtx* ) ctx )->obstacle;
444 
445  if (( feat == lp->feature ) || ( feat->getHoleOf() && feat->getHoleOf() != lp->feature ) )
446  {
447  return true;
448  }
449 
451 
452  return true;
453  }
454 
455 
457  {
458  LabelPosition *lp2 = ( LabelPosition* ) ctx;
459 
460  //std::cerr << "checking " << lp2->getFeature()->getUID() << " x " << lp->getFeature()->getUID() << std::endl;
461  if ( lp2->isInConflict( lp ) )
462  {
463  //std::cerr << "conflict!" << std::endl;
464  lp2->nbOverlap++;
465  }
466 
467  return true;
468  }
469 
471  {
472  LabelPosition *lp2 = (( CountContext* ) ctx )->lp;
473  double *cost = (( CountContext* ) ctx )->cost;
474  //int *feat = ((CountContext*)ctx)->feat;
475  int *nbOv = (( CountContext* ) ctx )->nbOv;
476  double *inactiveCost = (( CountContext* ) ctx )->inactiveCost;
477  if ( lp2->isInConflict( lp ) )
478  {
479 #ifdef _DEBUG_FULL_
480  std::cout << "count overlap : " << lp->id << "<->" << lp2->id << std::endl;
481 #endif
482  ( *nbOv ) ++;
483  *cost += inactiveCost[lp->probFeat] + lp->getCost();
484 
485  }
486 
487  return true;
488  }
489 
490 
492  {
493  LabelPosition *lp2 = ( LabelPosition * ) ctx;
494 
495  if ( lp2->isInConflict( lp ) )
496  {
497  //std::cout << " hit !" << std::endl;
498  lp->nbOverlap--;
499  lp2->nbOverlap--;
500  }
501 
502  return true;
503  }
504 
505 
506 
507  double LabelPosition::getDistanceToPoint( double xp, double yp )
508  {
509  int i;
510  int j;
511 
512  double mx[4];
513  double my[4];
514 
515  double dist_min = DBL_MAX;
516  double dist;
517 
518  for ( i = 0; i < 4; i++ )
519  {
520  j = ( i + 1 ) % 4;
521  mx[i] = ( x[i] + x[j] ) / 2.0;
522  my[i] = ( y[i] + y[j] ) / 2.0;
523  }
524 
525  if ( vabs( cross_product( mx[0], my[0], mx[2], my[2], xp, yp ) / h ) < w / 2 )
526  {
527  dist = cross_product( x[1], y[1], x[0], y[0], xp, yp ) / w;
528  if ( vabs( dist ) < vabs( dist_min ) )
529  dist_min = dist;
530 
531  dist = cross_product( x[3], y[3], x[2], y[2], xp, yp ) / w;
532  if ( vabs( dist ) < vabs( dist_min ) )
533  dist_min = dist;
534  }
535 
536  if ( vabs( cross_product( mx[1], my[1], mx[3], my[3], xp, yp ) / w ) < h / 2 )
537  {
538  dist = cross_product( x[2], y[2], x[1], y[1], xp, yp ) / h;
539  if ( vabs( dist ) < vabs( dist_min ) )
540  dist_min = dist;
541 
542  dist = cross_product( x[0], y[0], x[3], y[3], xp, yp ) / h;
543  if ( vabs( dist ) < vabs( dist_min ) )
544  dist_min = dist;
545  }
546 
547  for ( i = 0; i < 4; i++ )
548  {
549  dist = dist_euc2d( x[i], y[i], xp, yp );
550  if ( vabs( dist ) < vabs( dist_min ) )
551  dist_min = dist;
552  }
553 
554  if ( nextPart && dist_min > 0 )
555  return min( dist_min, nextPart->getDistanceToPoint( xp, yp ) );
556 
557  return dist_min;
558  }
559 
560 
562  {
563  double ca, cb;
564  for ( int i = 0; i < 4; i++ )
565  {
566  for ( int j = 0; j < feat->getNumPoints() - 1; j++ )
567  {
568  ca = cross_product( x[i], y[i], x[( i+1 ) %4], y[( i+1 ) %4],
569  feat->x[j], feat->y[j] );
570  cb = cross_product( x[i], y[i], x[( i+1 ) %4], y[( i+1 ) %4],
571  feat->x[j+1], feat->y[j+1] );
572 
573  if (( ca < 0 && cb > 0 ) || ( ca > 0 && cb < 0 ) )
574  {
575  ca = cross_product( feat->x[j], feat->y[j], feat->x[j+1], feat->y[j+1],
576  x[i], y[i] );
577  cb = cross_product( feat->x[j], feat->y[j], feat->x[j+1], feat->y[j+1],
578  x[( i+1 ) %4], y[( i+1 ) %4] );
579  if (( ca < 0 && cb > 0 ) || ( ca > 0 && cb < 0 ) )
580  return true;
581  }
582  }
583  }
584 
585  if ( nextPart )
586  return nextPart->isBorderCrossingLine( feat );
587 
588  return false;
589  }
590 
591  int LabelPosition::getNumPointsInPolygon( int npol, double *xp, double *yp )
592  {
593  int a, k, count = 0;
594  double px, py;
595 
596  // cheack each corner
597  for ( k = 0; k < 4; k++ )
598  {
599  px = x[k];
600  py = y[k];
601 
602  for ( a = 0; a < 2; a++ ) // and each middle of segment
603  {
604  if ( isPointInPolygon( npol, xp, yp, px, py ) )
605  count++;
606  px = ( x[k] + x[( k+1 ) %4] ) / 2.0;
607  py = ( y[k] + y[( k+1 ) %4] ) / 2.0;
608  }
609  }
610 
611  px = ( x[0] + x[2] ) / 2.0;
612  py = ( y[0] + y[2] ) / 2.0;
613 
614  // and the label center
615  if ( isPointInPolygon( npol, xp, yp, px, py ) )
616  count += 4; // virtually 4 points
617 
618  // TODO: count with nextFeature
619 
620  return count;
621  }
622 
623 } // end namespace
624 
FeaturePart * feature
static unsigned index
FeaturePart * getFeaturePart()
return the feature corresponding to this labelposition
bool isBorderCrossingLine(PointSet *feat)
Returns true if this label crosses the specified line.
PointSet * getHoleOf()
Returns NULL if this isn't a hole.
Definition: pointset.h:147
double getCost() const
get the position geographical cost
bool getFixedRotation()
Definition: feature.h:253
void validateCost()
Make sure the cost is less than 1.
static bool removeOverlapCallback(LabelPosition *lp, void *ctx)
static bool countOverlapCallback(LabelPosition *lp, void *ctx)
void offsetPosition(double xOffset, double yOffset)
Shift the label by specified offset.
static bool costGrow(void *l, void *r)
bool isInConflictMultiPart(LabelPosition *lp)
Layer * getLayer()
return the layer that feature belongs to
Definition: feature.cpp:257
char * name
Definition: layer.h:262
static void addObstacleCostPenalty(LabelPosition *lp, PointSet *feat)
Increase candidate's cost according to its collision with passed feature.
bool isIn(double *bbox)
Is the labelposition in the bounding-box ? (intersect or inside????)
bool isPointInPolygon(int npol, double *xp, double *yp, double x, double y)
bool isInConflict(LabelPosition *ls)
Check whether or not this overlap with another labelPosition.
int getId() const
return id
char * getLayerName() const
Return pointer to layer's name.
UpsideDownLabels getUpsidedownLabels() const
Definition: layer.h:217
void getBoundingBox(double amin[2], double amax[2]) const
Return bounding box - amin: xmin,ymin - amax: xmax,ymax.
bool isIntersect(double *bbox)
Is the labelposition intersect the bounding-box ?
static bool polygonObstacleCallback(PointSet *feat, void *ctx)
double getY(int i=0) const
get the down-left y coordinate
double getAlpha() const
get alpha
LabelPosition * nextPart
double * x
Definition: pointset.h:204
bool getFixedPosition()
Definition: feature.h:255
double getDistanceToPoint(double xp, double yp)
Get distance from this label to a point.
bool isInConflictSinglePart(LabelPosition *lp)
double dist_euc2d(double x1, double y1, double x2, double y2)
Definition: geomfunction.h:52
void update(PointSet *pset)
void removeFromIndex(RTree< LabelPosition *, double, 2, double > *index)
static bool countFullOverlapCallback(LabelPosition *lp, void *ctx)
void insertIntoIndex(RTree< LabelPosition *, double, 2, double > *index)
double cross_product(double x1, double y1, double x2, double y2, double x3, double y3)
Definition: geomfunction.h:47
const char * getUID()
get the unique id of the feature
Definition: feature.cpp:263
Main class to handle feature.
Definition: feature.h:133
int getNumPoints() const
Definition: pointset.h:149
double getLabelAngle()
Definition: feature.h:254
Arrangement getArrangement()
get arrangement policy
Definition: layer.cpp:151
static bool pruneCallback(LabelPosition *lp, void *ctx)
Check whether the candidate in ctx overlap with obstacle feat.
int min(int a, int b)
Definition: util.h:88
double * y
Definition: pointset.h:205
const char * getName()
get layer's name
Definition: layer.cpp:146
LabelPosition(int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed=false, Quadrant quadrant=QuadrantOver)
create a new LabelPosition
#define M_PI
LabelPosition is a candidate feature label position.
Definition: labelposition.h:50
Quadrant
Position of label candidate relative to feature.
Definition: labelposition.h:60
double getX(int i=0) const
get the down-left x coordinate
Data structure to compute polygon's candidates costs.
bool isInside(double *bbox)
Is the labelposition inside the bounding-box ?
int getNumPointsInPolygon(int npol, double *xp, double *yp)
Returns number of intersections with polygon (testing border and center)
static bool costShrink(void *l, void *r)
LabelPosition::Quadrant quadrant
double vabs(double x)
Definition: util.h:94