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