Skip to content

Commit 268feb5

Browse files
nyalldawsonnyalldawson
committedJul 21, 2015
[pal] Use GEOS methods for label position conflict tests
·
ltr-3_40archive/master_2
1 parent eaddba6 commit 268feb5

File tree

6 files changed

+67
-118
lines changed

6 files changed

+67
-118
lines changed
 

‎src/core/pal/costcalculator.cpp

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -42,6 +42,8 @@ namespace pal
4242
if ( dist < 0 )
4343
n = 2;
4444
else if ( dist < distlabel )
45+
//note this never happens at the moment - points are not obstacles if they don't fall
46+
//within the label
4547
n = 1;
4648
else
4749
n = 0;

‎src/core/pal/feature.cpp

Lines changed: 2 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1381,13 +1381,11 @@ namespace pal
13811381
return false;
13821382
}
13831383

1384-
if ( mOwnsGeom ) // delete old geometry if we own it
1385-
GEOSGeom_destroy_r( ctxt, mGeos );
1386-
GEOSPreparedGeom_destroy_r( ctxt, mPreparedGeom );
1384+
invalidateGeos();
1385+
13871386
// set up new geometry
13881387
mGeos = gTmp;
13891388
mOwnsGeom = true;
1390-
mPreparedGeom = 0;
13911389

13921390
deleteCoords();
13931391
qDeleteAll( mHoles );

‎src/core/pal/labelposition.cpp

Lines changed: 43 additions & 105 deletions
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,8 @@
4848
namespace pal
4949
{
5050
LabelPosition::LabelPosition( int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed, Quadrant quadrant )
51-
: id( id )
51+
: PointSet()
52+
, id( id )
5253
, cost( cost )
5354
, feature( feature )
5455
, probFeat( 0 )
@@ -62,6 +63,10 @@ namespace pal
6263
, upsideDown( false )
6364
, quadrant( quadrant )
6465
{
66+
type = GEOS_POLYGON;
67+
nbPoints = 4;
68+
x = new double[nbPoints];
69+
y = new double[nbPoints];
6570

6671
// alpha take his value bw 0 and 2*pi rad
6772
while ( this->alpha > 2*M_PI )
@@ -148,9 +153,18 @@ namespace pal
148153
upsideDown = true;
149154
}
150155
}
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+
}
151164
}
152165

153166
LabelPosition::LabelPosition( const LabelPosition& other )
167+
: PointSet( other )
154168
{
155169
id = other.id;
156170
cost = other.cost;
@@ -250,39 +264,15 @@ namespace pal
250264

251265
bool LabelPosition::isInConflictSinglePart( LabelPosition* lp )
252266
{
253-
// TODO: add bounding box test to possibly avoid cross product calculation
267+
if ( !mGeos )
268+
createGeosGeom();
254269

255-
int i, i2, j;
256-
int d1, d2;
257-
double cp1, cp2;
258-
259-
for ( i = 0; i < 4; i++ )
260-
{
261-
i2 = ( i + 1 ) % 4;
262-
d1 = -1;
263-
d2 = -1;
270+
if ( !lp->mGeos )
271+
lp->createGeosGeom();
264272

265-
for ( j = 0; j < 4; j++ )
266-
{
267-
cp1 = cross_product( x[i], y[i], x[i2], y[i2], lp->x[j], lp->y[j] );
268-
if ( cp1 > 0 )
269-
{
270-
d1 = 1;
271-
}
272-
cp2 = cross_product( lp->x[i], lp->y[i],
273-
lp->x[i2], lp->y[i2],
274-
x[j], y[j] );
275-
276-
if ( cp2 > 0 )
277-
{
278-
d2 = 1;
279-
}
280-
}
281-
282-
if ( d1 == -1 || d2 == -1 ) // disjoint
283-
return false;
284-
}
285-
return true;
273+
GEOSContextHandle_t geosctxt = geosContext();
274+
bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
275+
return result;
286276
}
287277

288278
bool LabelPosition::isInConflictMultiPart( LabelPosition* lp )
@@ -315,8 +305,9 @@ namespace pal
315305

316306
if ( nextPart )
317307
nextPart->offsetPosition( xOffset, yOffset );
318-
}
319308

309+
invalidateGeos();
310+
}
320311

321312
int LabelPosition::getId() const
322313
{
@@ -500,89 +491,36 @@ namespace pal
500491
return true;
501492
}
502493

503-
504-
505-
double LabelPosition::getDistanceToPoint( double xp, double yp )
494+
double LabelPosition::getDistanceToPoint( double xp, double yp ) const
506495
{
507-
int i;
508-
int j;
509-
510-
double mx[4];
511-
double my[4];
512-
513-
double dist_min = DBL_MAX;
514-
double dist;
515-
516-
for ( i = 0; i < 4; i++ )
517-
{
518-
j = ( i + 1 ) % 4;
519-
mx[i] = ( x[i] + x[j] ) / 2.0;
520-
my[i] = ( y[i] + y[j] ) / 2.0;
521-
}
496+
//first check if inside, if so then distance is -1
497+
double distance = ( containsPoint( xp, yp ) ? -1
498+
: sqrt( minDistanceToPoint( xp, yp ) ) );
522499

523-
if ( qAbs( cross_product( mx[0], my[0], mx[2], my[2], xp, yp ) / h ) < w / 2 )
524-
{
525-
dist = cross_product( x[1], y[1], x[0], y[0], xp, yp ) / w;
526-
if ( qAbs( dist ) < qAbs( dist_min ) )
527-
dist_min = dist;
500+
if ( nextPart && distance > 0 )
501+
return qMin( distance, nextPart->getDistanceToPoint( xp, yp ) );
528502

529-
dist = cross_product( x[3], y[3], x[2], y[2], xp, yp ) / w;
530-
if ( qAbs( dist ) < qAbs( dist_min ) )
531-
dist_min = dist;
532-
}
503+
return distance;
504+
}
533505

534-
if ( qAbs( cross_product( mx[1], my[1], mx[3], my[3], xp, yp ) / w ) < h / 2 )
535-
{
536-
dist = cross_product( x[2], y[2], x[1], y[1], xp, yp ) / h;
537-
if ( qAbs( dist ) < qAbs( dist_min ) )
538-
dist_min = dist;
506+
bool LabelPosition::isBorderCrossingLine( PointSet* line ) const
507+
{
508+
if ( !mGeos )
509+
createGeosGeom();
539510

540-
dist = cross_product( x[0], y[0], x[3], y[3], xp, yp ) / h;
541-
if ( qAbs( dist ) < qAbs( dist_min ) )
542-
dist_min = dist;
543-
}
511+
if ( !line->mGeos )
512+
line->createGeosGeom();
544513

545-
for ( i = 0; i < 4; i++ )
514+
GEOSContextHandle_t geosctxt = geosContext();
515+
if ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), line->mGeos ) == 1 )
546516
{
547-
dist = dist_euc2d( x[i], y[i], xp, yp );
548-
if ( qAbs( dist ) < qAbs( dist_min ) )
549-
dist_min = dist;
517+
return true;
550518
}
551-
552-
if ( nextPart && dist_min > 0 )
553-
return qMin( dist_min, nextPart->getDistanceToPoint( xp, yp ) );
554-
555-
return dist_min;
556-
}
557-
558-
559-
bool LabelPosition::isBorderCrossingLine( PointSet* feat )
560-
{
561-
double ca, cb;
562-
for ( int i = 0; i < 4; i++ )
519+
else if ( nextPart )
563520
{
564-
for ( int j = 0; j < feat->getNumPoints() - 1; j++ )
565-
{
566-
ca = cross_product( x[i], y[i], x[( i+1 ) %4], y[( i+1 ) %4],
567-
feat->x[j], feat->y[j] );
568-
cb = cross_product( x[i], y[i], x[( i+1 ) %4], y[( i+1 ) %4],
569-
feat->x[j+1], feat->y[j+1] );
570-
571-
if (( ca < 0 && cb > 0 ) || ( ca > 0 && cb < 0 ) )
572-
{
573-
ca = cross_product( feat->x[j], feat->y[j], feat->x[j+1], feat->y[j+1],
574-
x[i], y[i] );
575-
cb = cross_product( feat->x[j], feat->y[j], feat->x[j+1], feat->y[j+1],
576-
x[( i+1 ) %4], y[( i+1 ) %4] );
577-
if (( ca < 0 && cb > 0 ) || ( ca > 0 && cb < 0 ) )
578-
return true;
579-
}
580-
}
521+
return nextPart->isBorderCrossingLine( line );
581522
}
582523

583-
if ( nextPart )
584-
return nextPart->isBorderCrossingLine( feat );
585-
586524
return false;
587525
}
588526

‎src/core/pal/labelposition.h

Lines changed: 3 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ namespace pal
4545
/**
4646
* \brief LabelPosition is a candidate feature label position
4747
*/
48-
class CORE_EXPORT LabelPosition
48+
class CORE_EXPORT LabelPosition : public PointSet
4949
{
5050
friend class CostCalculator;
5151
friend class PolygonCostCalculator;
@@ -126,10 +126,10 @@ namespace pal
126126
void getBoundingBox( double amin[2], double amax[2] ) const;
127127

128128
/** Get distance from this label to a point. If point lies inside, returns negative number. */
129-
double getDistanceToPoint( double xp, double yp );
129+
double getDistanceToPoint( double xp, double yp ) const;
130130

131131
/** Returns true if this label crosses the specified line */
132-
bool isBorderCrossingLine( PointSet* feat );
132+
bool isBorderCrossingLine( PointSet* line ) const;
133133

134134
/** Returns number of intersections with polygon (testing border and center) */
135135
int getNumPointsInPolygon( PointSet* polygon ) const;
@@ -258,7 +258,6 @@ namespace pal
258258

259259
int nbOverlap;
260260

261-
double x[4], y[4];
262261
double alpha;
263262
double w;
264263
double h;

‎src/core/pal/pointset.cpp

Lines changed: 13 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -109,7 +109,7 @@ namespace pal
109109
type = GEOS_POINT;
110110
}
111111

112-
PointSet::PointSet( PointSet &ps )
112+
PointSet::PointSet( const PointSet &ps )
113113
: mGeos( 0 )
114114
, mOwnsGeom( false )
115115
, parent( 0 )
@@ -211,6 +211,17 @@ namespace pal
211211
return mPreparedGeom;
212212
}
213213

214+
void PointSet::invalidateGeos()
215+
{
216+
GEOSContextHandle_t geosctxt = geosContext();
217+
if ( mOwnsGeom ) // delete old geometry if we own it
218+
GEOSGeom_destroy_r( geosctxt, mGeos );
219+
GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
220+
mOwnsGeom = false;
221+
mGeos = 0;
222+
mPreparedGeom = 0;
223+
}
224+
214225
PointSet::~PointSet()
215226
{
216227
GEOSContextHandle_t geosctxt = geosContext();
@@ -867,7 +878,7 @@ namespace pal
867878
return finalBb;
868879
}
869880

870-
double PointSet::minDistanceToPoint( double px, double py, double *rx, double *ry )
881+
double PointSet::minDistanceToPoint( double px, double py, double *rx, double *ry ) const
871882
{
872883
if ( !mGeos )
873884
createGeosGeom();

‎src/core/pal/pointset.h

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -98,15 +98,15 @@ namespace pal
9898
QLinkedList<PointSet *> &shapes_final,
9999
double xrm, double yrm, const QString &uid );
100100

101-
/** Returns the minimum distance between the point set geometry and the point (px,py)
101+
/** Returns the squared minimum distance between the point set geometry and the point (px,py)
102102
* Optionally, the nearest point is stored in (rx,ry).
103103
* @param px x coordinate of the point
104104
* @param py y coordinate of the points
105105
* @param rx pointer to x coorinates of the nearest point (can be NULL)
106106
* @param ry pointer to y coorinates of the nearest point (can be NULL)
107107
* @returns minimum distance
108108
*/
109-
double minDistanceToPoint( double px, double py, double *rx = 0, double *ry = 0 );
109+
double minDistanceToPoint( double px, double py, double *rx = 0, double *ry = 0 ) const;
110110

111111
void getCentroid( double &px, double &py, bool forceInside = false ) const;
112112

@@ -156,11 +156,12 @@ namespace pal
156156

157157
PointSet( double x, double y );
158158

159-
PointSet( PointSet &ps );
159+
PointSet( const PointSet &ps );
160160

161161
void deleteCoords();
162162
void createGeosGeom() const;
163163
const GEOSPreparedGeometry* preparedGeom() const;
164+
void invalidateGeos();
164165

165166
double xmin;
166167
double xmax;

0 commit comments

Comments
 (0)
Please sign in to comment.