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 "qgsgeos.h"
39 #include "qgsmessagelog.h"
40 #include <iostream>
41 #include <fstream>
42 #include <cmath>
43 #include <cfloat>
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  : PointSet()
54  , id( id )
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  , mCost( cost )
67  , mHasObstacleConflict( false )
68  {
69  type = GEOS_POLYGON;
70  nbPoints = 4;
71  x = new double[nbPoints];
72  y = new double[nbPoints];
73 
74  // alpha take his value bw 0 and 2*pi rad
75  while ( this->alpha > 2*M_PI )
76  this->alpha -= 2 * M_PI;
77 
78  while ( this->alpha < 0 )
79  this->alpha += 2 * M_PI;
80 
81  double beta = this->alpha + ( M_PI / 2 );
82 
83  double dx1, dx2, dy1, dy2;
84 
85  double tx, ty;
86 
87  dx1 = cos( this->alpha ) * w;
88  dy1 = sin( this->alpha ) * w;
89 
90  dx2 = cos( beta ) * h;
91  dy2 = sin( beta ) * h;
92 
93  x[0] = x1;
94  y[0] = y1;
95 
96  x[1] = x1 + dx1;
97  y[1] = y1 + dy1;
98 
99  x[2] = x1 + dx1 + dx2;
100  y[2] = y1 + dy1 + dy2;
101 
102  x[3] = x1 + dx2;
103  y[3] = y1 + dy2;
104 
105  // upside down ? (curved labels are always correct)
106  if ( feature->layer()->arrangement() != P_CURVED &&
107  this->alpha > M_PI / 2 && this->alpha <= 3*M_PI / 2 )
108  {
109  bool uprightLabel = false;
110 
111  switch ( feature->layer()->upsidedownLabels() )
112  {
113  case Layer::Upright:
114  uprightLabel = true;
115  break;
116  case Layer::ShowDefined:
117  // upright only dynamic labels
118  if ( !feature->getFixedRotation() || ( !feature->getFixedPosition() && feature->getLabelAngle() == 0.0 ) )
119  {
120  uprightLabel = true;
121  }
122  break;
123  case Layer::ShowAll:
124  break;
125  default:
126  uprightLabel = true;
127  }
128 
129  if ( uprightLabel )
130  {
131  tx = x[0];
132  ty = y[0];
133 
134  x[0] = x[2];
135  y[0] = y[2];
136 
137  x[2] = tx;
138  y[2] = ty;
139 
140  tx = x[1];
141  ty = y[1];
142 
143  x[1] = x[3];
144  y[1] = y[3];
145 
146  x[3] = tx;
147  y[3] = ty;
148 
149  if ( this->alpha < M_PI )
150  this->alpha += M_PI;
151  else
152  this->alpha -= M_PI;
153 
154  // labels with text shown upside down are not classified as upsideDown,
155  // only those whose boundary points have been inverted
156  upsideDown = true;
157  }
158  }
159 
160  for ( int i = 0; i < nbPoints; ++i )
161  {
162  xmin = qMin( xmin, x[i] );
163  xmax = qMax( xmax, x[i] );
164  ymin = qMin( ymin, y[i] );
165  ymax = qMax( ymax, y[i] );
166  }
167  }
168 
170  : PointSet( other )
171  {
172  id = other.id;
173  mCost = other.mCost;
174  feature = other.feature;
175  probFeat = other.probFeat;
176  nbOverlap = other.nbOverlap;
177 
178  alpha = other.alpha;
179  w = other.w;
180  h = other.h;
181 
182  if ( other.nextPart )
183  nextPart = new LabelPosition( *other.nextPart );
184  else
185  nextPart = NULL;
186  partId = other.partId;
187  upsideDown = other.upsideDown;
188  reversed = other.reversed;
189  quadrant = other.quadrant;
190  mHasObstacleConflict = other.mHasObstacleConflict;
191  }
192 
193  bool LabelPosition::isIn( double *bbox )
194  {
195  int i;
196 
197  for ( i = 0; i < 4; i++ )
198  {
199  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
200  y[i] >= bbox[1] && y[i] <= bbox[3] )
201  return true;
202  }
203 
204  if ( nextPart )
205  return nextPart->isIn( bbox );
206  else
207  return false;
208 
209  }
210 
211  bool LabelPosition::isIntersect( double *bbox )
212  {
213  int i;
214 
215  for ( i = 0; i < 4; i++ )
216  {
217  if ( x[i] >= bbox[0] && x[i] <= bbox[2] &&
218  y[i] >= bbox[1] && y[i] <= bbox[3] )
219  return true;
220  }
221 
222  if ( nextPart )
223  return nextPart->isIntersect( bbox );
224  else
225  return false;
226  }
227 
228  bool LabelPosition::isInside( double *bbox )
229  {
230  for ( int i = 0; i < 4; i++ )
231  {
232  if ( !( x[i] >= bbox[0] && x[i] <= bbox[2] &&
233  y[i] >= bbox[1] && y[i] <= bbox[3] ) )
234  return false;
235  }
236 
237  if ( nextPart )
238  return nextPart->isInside( bbox );
239  else
240  return true;
241 
242  }
243 
245  {
246  // std::cout << feature->getLayer()->getName() << "/" << feature->getUID() << "/" << id;
247  std::cout << " cost: " << mCost;
248  std::cout << " alpha" << alpha << std::endl;
249  std::cout << x[0] << ", " << y[0] << std::endl;
250  std::cout << x[1] << ", " << y[1] << std::endl;
251  std::cout << x[2] << ", " << y[2] << std::endl;
252  std::cout << x[3] << ", " << y[3] << std::endl;
253  std::cout << std::endl;
254  }
255 
257  {
258  if ( this->probFeat == lp->probFeat ) // bugfix #1
259  return false; // always overlaping itself !
260 
261  if ( nextPart == NULL && lp->nextPart == NULL )
262  return isInConflictSinglePart( lp );
263  else
264  return isInConflictMultiPart( lp );
265  }
266 
268  {
269  if ( !mGeos )
270  createGeosGeom();
271 
272  if ( !lp->mGeos )
273  lp->createGeosGeom();
274 
275  GEOSContextHandle_t geosctxt = geosContext();
276  try
277  {
278  bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
279  return result;
280  }
281  catch ( GEOSException &e )
282  {
283  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
284  return false;
285  }
286  }
287 
289  {
290  // check all parts against all parts of other one
291  LabelPosition* tmp1 = this;
292  while ( tmp1 )
293  {
294  // check tmp1 against parts of other label
295  LabelPosition* tmp2 = lp;
296  while ( tmp2 )
297  {
298  if ( tmp1->isInConflictSinglePart( tmp2 ) )
299  return true;
300  tmp2 = tmp2->nextPart;
301  }
302 
303  tmp1 = tmp1->nextPart;
304  }
305  return false; // no conflict found
306  }
307 
308  void LabelPosition::offsetPosition( double xOffset, double yOffset )
309  {
310  for ( int i = 0; i < 4; i++ )
311  {
312  x[i] += xOffset;
313  y[i] += yOffset;
314  }
315 
316  if ( nextPart )
317  nextPart->offsetPosition( xOffset, yOffset );
318 
319  invalidateGeos();
320  }
321 
323  {
324  return id;
325  }
326 
327  double LabelPosition::getX( int i ) const
328  {
329  return ( i >= 0 && i < 4 ? x[i] : -1 );
330  }
331 
332  double LabelPosition::getY( int i ) const
333  {
334  return ( i >= 0 && i < 4 ? y[i] : -1 );
335  }
336 
337  double LabelPosition::getAlpha() const
338  {
339  return alpha;
340  }
341 
343  {
344  if ( mCost >= 1 )
345  {
346  // std::cout << " Warning: lp->cost == " << cost << " (from feat: " << feature->getUID() << "/" << getLayerName() << ")" << std::endl;
347  mCost -= int ( mCost ); // label cost up to 1
348  }
349  }
350 
352  {
353  return feature;
354  }
355 
356  void LabelPosition::getBoundingBox( double amin[2], double amax[2] ) const
357  {
358  if ( nextPart )
359  {
360  //std::cout << "using next part" <<
361  nextPart->getBoundingBox( amin, amax );
362  }
363  else
364  {
365  amin[0] = DBL_MAX;
366  amax[0] = -DBL_MAX;
367  amin[1] = DBL_MAX;
368  amax[1] = -DBL_MAX;
369  }
370  for ( int c = 0; c < 4; c++ )
371  {
372  if ( x[c] < amin[0] )
373  amin[0] = x[c];
374  if ( x[c] > amax[0] )
375  amax[0] = x[c];
376  if ( y[c] < amin[1] )
377  amin[1] = y[c];
378  if ( y[c] > amax[1] )
379  amax[1] = y[c];
380  }
381  }
382 
384  {
385  return feature->layer()->name();
386  }
387 
389  {
390  mHasObstacleConflict = conflicts;
391  if ( nextPart )
392  nextPart->setConflictsWithObstacle( conflicts );
393  }
394 
395  bool LabelPosition::costShrink( void *l, void *r )
396  {
397  return (( LabelPosition* ) l )->mCost < (( LabelPosition* ) r )->mCost;
398  }
399 
400  bool LabelPosition::costGrow( void *l, void *r )
401  {
402  return (( LabelPosition* ) l )->mCost > (( LabelPosition* ) r )->mCost;
403  }
404 
405 
407  {
409 
410  LabelPosition *lp = pCost->getLabel();
411  if (( obstacle == lp->feature ) || ( obstacle->getHoleOf() && obstacle->getHoleOf() != lp->feature ) )
412  {
413  return true;
414  }
415 
416  pCost->update( obstacle );
417 
418  return true;
419  }
420 
421 
423  {
424  double amin[2];
425  double amax[2];
426  getBoundingBox( amin, amax );
427  index->Remove( amin, amax, this );
428  }
429 
430 
432  {
433  double amin[2];
434  double amax[2];
435  getBoundingBox( amin, amax );
436  index->Insert( amin, amax, this );
437  }
438 
439 
441 
443  {
444  FeaturePart *feat = (( PruneCtx* ) ctx )->obstacle;
445 
446  if (( feat == lp->feature ) || ( feat->getHoleOf() && feat->getHoleOf() != lp->feature ) )
447  {
448  return true;
449  }
450 
452 
453  return true;
454  }
455 
456 
458  {
459  LabelPosition *lp2 = ( LabelPosition* ) ctx;
460 
461  //std::cerr << "checking " << lp2->getFeature()->getUID() << " x " << lp->getFeature()->getUID() << std::endl;
462  if ( lp2->isInConflict( lp ) )
463  {
464  //std::cerr << "conflict!" << std::endl;
465  lp2->nbOverlap++;
466  }
467 
468  return true;
469  }
470 
472  {
473  LabelPosition *lp2 = (( CountContext* ) ctx )->lp;
474  double *cost = (( CountContext* ) ctx )->cost;
475  //int *feat = ((CountContext*)ctx)->feat;
476  int *nbOv = (( CountContext* ) ctx )->nbOv;
477  double *inactiveCost = (( CountContext* ) ctx )->inactiveCost;
478  if ( lp2->isInConflict( lp ) )
479  {
480 #ifdef _DEBUG_FULL_
481  std::cout << "count overlap : " << lp->id << "<->" << lp2->id << std::endl;
482 #endif
483  ( *nbOv ) ++;
484  *cost += inactiveCost[lp->probFeat] + lp->cost();
485 
486  }
487 
488  return true;
489  }
490 
491 
493  {
494  LabelPosition *lp2 = ( LabelPosition * ) ctx;
495 
496  if ( lp2->isInConflict( lp ) )
497  {
498  //std::cout << " hit !" << std::endl;
499  lp->nbOverlap--;
500  lp2->nbOverlap--;
501  }
502 
503  return true;
504  }
505 
506  double LabelPosition::getDistanceToPoint( double xp, double yp ) const
507  {
508  //first check if inside, if so then distance is -1
509  double distance = ( containsPoint( xp, yp ) ? -1
510  : sqrt( minDistanceToPoint( xp, yp ) ) );
511 
512  if ( nextPart && distance > 0 )
513  return qMin( distance, nextPart->getDistanceToPoint( xp, yp ) );
514 
515  return distance;
516  }
517 
519  {
520  if ( !mGeos )
521  createGeosGeom();
522 
523  if ( !line->mGeos )
524  line->createGeosGeom();
525 
526  GEOSContextHandle_t geosctxt = geosContext();
527  try
528  {
529  if ( GEOSPreparedIntersects_r( geosctxt, line->preparedGeom(), mGeos ) == 1 )
530  {
531  return true;
532  }
533  else if ( nextPart )
534  {
535  return nextPart->crossesLine( line );
536  }
537  }
538  catch ( GEOSException &e )
539  {
540  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
541  return false;
542  }
543 
544  return false;
545  }
546 
548  {
549  if ( !mGeos )
550  createGeosGeom();
551 
552  if ( !polygon->mGeos )
553  polygon->createGeosGeom();
554 
555  GEOSContextHandle_t geosctxt = geosContext();
556  try
557  {
558  if ( GEOSPreparedOverlaps_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1
559  || GEOSPreparedTouches_r( geosctxt, polygon->preparedGeom(), mGeos ) == 1 )
560  {
561  return true;
562  }
563  else if ( nextPart )
564  {
565  return nextPart->crossesBoundary( polygon );
566  }
567  }
568  catch ( GEOSException &e )
569  {
570  QgsMessageLog::logMessage( QObject::tr( "Exception: %1" ).arg( e.what() ), QObject::tr( "GEOS" ) );
571  return false;
572  }
573 
574  return false;
575  }
576 
578  {
579  int a, k, count = 0;
580  double px, py;
581 
582  // check each corner
583  for ( k = 0; k < 4; k++ )
584  {
585  px = x[k];
586  py = y[k];
587 
588  for ( a = 0; a < 2; a++ ) // and each middle of segment
589  {
590  if ( polygon->containsPoint( px, py ) )
591  count++;
592  px = ( x[k] + x[( k+1 ) %4] ) / 2.0;
593  py = ( y[k] + y[( k+1 ) %4] ) / 2.0;
594  }
595  }
596 
597  px = ( x[0] + x[2] ) / 2.0;
598  py = ( y[0] + y[2] ) / 2.0;
599 
600  // and the label center
601  if ( polygon->containsPoint( px, py ) )
602  count += 4; // virtually 4 points
603 
604  // TODO: count with nextFeature
605 
606  return count;
607  }
608 
609 } // end namespace
610 
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
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.
double cost() const
Returns the candidate label position's geographical cost.
static bool costGrow(void *l, void *r)
bool crossesLine(PointSet *line) const
Returns true if this label crosses the specified line.
bool isInConflictMultiPart(LabelPosition *lp)
QString tr(const char *sourceText, const char *disambiguation, int n)
void createGeosGeom() const
Definition: pointset.cpp:158
bool isIn(double *bbox)
Is the labelposition in the bounding-box ? (intersect or inside????)
static void logMessage(QString message, QString tag=QString::null, MessageLevel level=WARNING)
add a message to the instance (and create it if necessary)
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:148
bool getFixedPosition()
Definition: feature.h:305
double ymax
Definition: pointset.h:171
double xmin
Definition: pointset.h:168
Layer * layer()
Returns the layer that feature belongs to.
Definition: feature.cpp:186
double ymin
Definition: pointset.h:170
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:56
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:295
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:149
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)
void setConflictsWithObstacle(bool conflicts)
Sets whether the position is marked as conflicting with an obstacle feature.
GEOSGeometry * mGeos
Definition: pointset.h:144
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:212
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:896
bool crossesBoundary(PointSet *polygon) const
Returns true if this label crosses the boundary of the specified polygon.
const GEOSPreparedGeometry * preparedGeom() const
Definition: pointset.cpp:200
double xmax
Definition: pointset.h:169
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