Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
[pal] Use GEOS methods for label position conflict tests
  • Loading branch information
nyalldawson committed Jul 21, 2015
1 parent eaddba6 commit 268feb5
Show file tree
Hide file tree
Showing 6 changed files with 67 additions and 118 deletions.
2 changes: 2 additions & 0 deletions src/core/pal/costcalculator.cpp
Expand Up @@ -42,6 +42,8 @@ namespace pal
if ( dist < 0 )
n = 2;
else if ( dist < distlabel )
//note this never happens at the moment - points are not obstacles if they don't fall
//within the label
n = 1;
else
n = 0;
Expand Down
6 changes: 2 additions & 4 deletions src/core/pal/feature.cpp
Expand Up @@ -1381,13 +1381,11 @@ namespace pal
return false;
}

if ( mOwnsGeom ) // delete old geometry if we own it
GEOSGeom_destroy_r( ctxt, mGeos );
GEOSPreparedGeom_destroy_r( ctxt, mPreparedGeom );
invalidateGeos();

// set up new geometry
mGeos = gTmp;
mOwnsGeom = true;
mPreparedGeom = 0;

deleteCoords();
qDeleteAll( mHoles );
Expand Down
148 changes: 43 additions & 105 deletions src/core/pal/labelposition.cpp
Expand Up @@ -48,7 +48,8 @@
namespace pal
{
LabelPosition::LabelPosition( int id, double x1, double y1, double w, double h, double alpha, double cost, FeaturePart *feature, bool isReversed, Quadrant quadrant )
: id( id )
: PointSet()
, id( id )
, cost( cost )
, feature( feature )
, probFeat( 0 )
Expand All @@ -62,6 +63,10 @@ namespace pal
, upsideDown( false )
, quadrant( quadrant )
{
type = GEOS_POLYGON;
nbPoints = 4;
x = new double[nbPoints];
y = new double[nbPoints];

// alpha take his value bw 0 and 2*pi rad
while ( this->alpha > 2*M_PI )
Expand Down Expand Up @@ -148,9 +153,18 @@ namespace pal
upsideDown = true;
}
}

for ( int i = 0; i < nbPoints; ++i )
{
xmin = qMin( xmin, x[i] );
xmax = qMax( xmax, x[i] );
ymin = qMin( ymin, y[i] );
ymax = qMax( ymax, y[i] );
}
}

LabelPosition::LabelPosition( const LabelPosition& other )
: PointSet( other )
{
id = other.id;
cost = other.cost;
Expand Down Expand Up @@ -250,39 +264,15 @@ namespace pal

bool LabelPosition::isInConflictSinglePart( LabelPosition* lp )
{
// TODO: add bounding box test to possibly avoid cross product calculation
if ( !mGeos )
createGeosGeom();

int i, i2, j;
int d1, d2;
double cp1, cp2;

for ( i = 0; i < 4; i++ )
{
i2 = ( i + 1 ) % 4;
d1 = -1;
d2 = -1;
if ( !lp->mGeos )
lp->createGeosGeom();

for ( j = 0; j < 4; j++ )
{
cp1 = cross_product( x[i], y[i], x[i2], y[i2], lp->x[j], lp->y[j] );
if ( cp1 > 0 )
{
d1 = 1;
}
cp2 = cross_product( lp->x[i], lp->y[i],
lp->x[i2], lp->y[i2],
x[j], y[j] );

if ( cp2 > 0 )
{
d2 = 1;
}
}

if ( d1 == -1 || d2 == -1 ) // disjoint
return false;
}
return true;
GEOSContextHandle_t geosctxt = geosContext();
bool result = ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), lp->mGeos ) == 1 );
return result;
}

bool LabelPosition::isInConflictMultiPart( LabelPosition* lp )
Expand Down Expand Up @@ -315,8 +305,9 @@ namespace pal

if ( nextPart )
nextPart->offsetPosition( xOffset, yOffset );
}

invalidateGeos();
}

int LabelPosition::getId() const
{
Expand Down Expand Up @@ -500,89 +491,36 @@ namespace pal
return true;
}



double LabelPosition::getDistanceToPoint( double xp, double yp )
double LabelPosition::getDistanceToPoint( double xp, double yp ) const
{
int i;
int j;

double mx[4];
double my[4];

double dist_min = DBL_MAX;
double dist;

for ( i = 0; i < 4; i++ )
{
j = ( i + 1 ) % 4;
mx[i] = ( x[i] + x[j] ) / 2.0;
my[i] = ( y[i] + y[j] ) / 2.0;
}
//first check if inside, if so then distance is -1
double distance = ( containsPoint( xp, yp ) ? -1
: sqrt( minDistanceToPoint( xp, yp ) ) );

if ( qAbs( cross_product( mx[0], my[0], mx[2], my[2], xp, yp ) / h ) < w / 2 )
{
dist = cross_product( x[1], y[1], x[0], y[0], xp, yp ) / w;
if ( qAbs( dist ) < qAbs( dist_min ) )
dist_min = dist;
if ( nextPart && distance > 0 )
return qMin( distance, nextPart->getDistanceToPoint( xp, yp ) );

dist = cross_product( x[3], y[3], x[2], y[2], xp, yp ) / w;
if ( qAbs( dist ) < qAbs( dist_min ) )
dist_min = dist;
}
return distance;
}

if ( qAbs( cross_product( mx[1], my[1], mx[3], my[3], xp, yp ) / w ) < h / 2 )
{
dist = cross_product( x[2], y[2], x[1], y[1], xp, yp ) / h;
if ( qAbs( dist ) < qAbs( dist_min ) )
dist_min = dist;
bool LabelPosition::isBorderCrossingLine( PointSet* line ) const
{
if ( !mGeos )
createGeosGeom();

dist = cross_product( x[0], y[0], x[3], y[3], xp, yp ) / h;
if ( qAbs( dist ) < qAbs( dist_min ) )
dist_min = dist;
}
if ( !line->mGeos )
line->createGeosGeom();

for ( i = 0; i < 4; i++ )
GEOSContextHandle_t geosctxt = geosContext();
if ( GEOSPreparedIntersects_r( geosctxt, preparedGeom(), line->mGeos ) == 1 )
{
dist = dist_euc2d( x[i], y[i], xp, yp );
if ( qAbs( dist ) < qAbs( dist_min ) )
dist_min = dist;
return true;
}

if ( nextPart && dist_min > 0 )
return qMin( dist_min, nextPart->getDistanceToPoint( xp, yp ) );

return dist_min;
}


bool LabelPosition::isBorderCrossingLine( PointSet* feat )
{
double ca, cb;
for ( int i = 0; i < 4; i++ )
else if ( nextPart )
{
for ( int j = 0; j < feat->getNumPoints() - 1; j++ )
{
ca = cross_product( x[i], y[i], x[( i+1 ) %4], y[( i+1 ) %4],
feat->x[j], feat->y[j] );
cb = cross_product( x[i], y[i], x[( i+1 ) %4], y[( i+1 ) %4],
feat->x[j+1], feat->y[j+1] );

if (( ca < 0 && cb > 0 ) || ( ca > 0 && cb < 0 ) )
{
ca = cross_product( feat->x[j], feat->y[j], feat->x[j+1], feat->y[j+1],
x[i], y[i] );
cb = cross_product( feat->x[j], feat->y[j], feat->x[j+1], feat->y[j+1],
x[( i+1 ) %4], y[( i+1 ) %4] );
if (( ca < 0 && cb > 0 ) || ( ca > 0 && cb < 0 ) )
return true;
}
}
return nextPart->isBorderCrossingLine( line );
}

if ( nextPart )
return nextPart->isBorderCrossingLine( feat );

return false;
}

Expand Down
7 changes: 3 additions & 4 deletions src/core/pal/labelposition.h
Expand Up @@ -45,7 +45,7 @@ namespace pal
/**
* \brief LabelPosition is a candidate feature label position
*/
class CORE_EXPORT LabelPosition
class CORE_EXPORT LabelPosition : public PointSet
{
friend class CostCalculator;
friend class PolygonCostCalculator;
Expand Down Expand Up @@ -126,10 +126,10 @@ namespace pal
void getBoundingBox( double amin[2], double amax[2] ) const;

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

/** Returns true if this label crosses the specified line */
bool isBorderCrossingLine( PointSet* feat );
bool isBorderCrossingLine( PointSet* line ) const;

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

int nbOverlap;

double x[4], y[4];
double alpha;
double w;
double h;
Expand Down
15 changes: 13 additions & 2 deletions src/core/pal/pointset.cpp
Expand Up @@ -109,7 +109,7 @@ namespace pal
type = GEOS_POINT;
}

PointSet::PointSet( PointSet &ps )
PointSet::PointSet( const PointSet &ps )
: mGeos( 0 )
, mOwnsGeom( false )
, parent( 0 )
Expand Down Expand Up @@ -211,6 +211,17 @@ namespace pal
return mPreparedGeom;
}

void PointSet::invalidateGeos()
{
GEOSContextHandle_t geosctxt = geosContext();
if ( mOwnsGeom ) // delete old geometry if we own it
GEOSGeom_destroy_r( geosctxt, mGeos );
GEOSPreparedGeom_destroy_r( geosctxt, mPreparedGeom );
mOwnsGeom = false;
mGeos = 0;
mPreparedGeom = 0;
}

PointSet::~PointSet()
{
GEOSContextHandle_t geosctxt = geosContext();
Expand Down Expand Up @@ -867,7 +878,7 @@ namespace pal
return finalBb;
}

double PointSet::minDistanceToPoint( double px, double py, double *rx, double *ry )
double PointSet::minDistanceToPoint( double px, double py, double *rx, double *ry ) const
{
if ( !mGeos )
createGeosGeom();
Expand Down
7 changes: 4 additions & 3 deletions src/core/pal/pointset.h
Expand Up @@ -98,15 +98,15 @@ namespace pal
QLinkedList<PointSet *> &shapes_final,
double xrm, double yrm, const QString &uid );

/** Returns the minimum distance between the point set geometry and the point (px,py)
/** Returns the squared minimum distance between the point set geometry and the point (px,py)
* Optionally, the nearest point is stored in (rx,ry).
* @param px x coordinate of the point
* @param py y coordinate of the points
* @param rx pointer to x coorinates of the nearest point (can be NULL)
* @param ry pointer to y coorinates of the nearest point (can be NULL)
* @returns minimum distance
*/
double minDistanceToPoint( double px, double py, double *rx = 0, double *ry = 0 );
double minDistanceToPoint( double px, double py, double *rx = 0, double *ry = 0 ) const;

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

Expand Down Expand Up @@ -156,11 +156,12 @@ namespace pal

PointSet( double x, double y );

PointSet( PointSet &ps );
PointSet( const PointSet &ps );

void deleteCoords();
void createGeosGeom() const;
const GEOSPreparedGeometry* preparedGeom() const;
void invalidateGeos();

double xmin;
double xmax;
Expand Down

0 comments on commit 268feb5

Please sign in to comment.