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