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