Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
[pal] Fix crash in labeling polygons in some rare circumstance which …
…I can

only reproduce on a single project

But this code is so totally unreadable that it's not suprising that
there's all kinds of nasty here. In this case the crash is caused
when the polygon part calculated by "splitPolygons" (which does...
something... to a polygon) results in a zero area polygon (because...
reasons). So add a safeguard in to avoid this situation.

Also rename class to something saner
  • Loading branch information
nyalldawson authored and github-actions[bot] committed Mar 11, 2021
1 parent 3719d93 commit 6a77947
Show file tree
Hide file tree
Showing 3 changed files with 32 additions and 34 deletions.
9 changes: 6 additions & 3 deletions src/core/pal/feature.cpp
Expand Up @@ -1654,14 +1654,17 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt
double beta;
double diago = std::sqrt( labelWidth * labelWidth / 4.0 + labelHeight * labelHeight / 4 );
double rx, ry;
std::vector< CHullBox > boxes;
std::vector< OrientedConvexHullBoundingBox > boxes;
boxes.reserve( shapes_final.size() );

// Compute bounding box foreach finalShape
while ( !shapes_final.isEmpty() )
{
PointSet *shape = shapes_final.takeFirst();
boxes.emplace_back( shape->compute_chull_bbox() );
bool ok = false;
OrientedConvexHullBoundingBox box = shape->computeConvexHullOrientedBoundingBox( ok );
if ( ok )
boxes.emplace_back( box );

if ( shape->parent )
delete shape;
Expand All @@ -1682,7 +1685,7 @@ std::size_t FeaturePart::createCandidatesForPolygon( std::vector< std::unique_pt

do
{
for ( CHullBox &box : boxes )
for ( OrientedConvexHullBoundingBox &box : boxes )
{
// there is two possibilities here:
// 1. no maximum candidates for polygon setting is in effect (i.e. maxPolygonCandidates == 0). In that case,
Expand Down
47 changes: 20 additions & 27 deletions src/core/pal/pointset.cpp
Expand Up @@ -638,31 +638,20 @@ void PointSet::extendLineByDistance( double startDistance, double endDistance, d
invalidateGeos();
}

CHullBox PointSet::compute_chull_bbox()
OrientedConvexHullBoundingBox PointSet::computeConvexHullOrientedBoundingBox( bool &ok )
{
int i;
int j;

ok = false;
double bbox[4]; // xmin, ymin, xmax, ymax

double alpha;
int alpha_d;

double alpha_seg;

double dref;
double d1, d2;

double bb[16]; // {ax, ay, bx, by, cx, cy, dx, dy, ex, ey, fx, fy, gx, gy, hx, hy}}

double cp;
double best_cp;
double distNearestPoint;

double area;
double width;
double length;

double best_area = std::numeric_limits<double>::max();
double best_alpha = -1;
double best_bb[16];
Expand All @@ -675,7 +664,7 @@ CHullBox PointSet::compute_chull_bbox()
bbox[2] = std::numeric_limits<double>::lowest();
bbox[3] = std::numeric_limits<double>::lowest();

for ( i = 0; i < cHullSize; i++ )
for ( int i = 0; i < cHullSize; i++ )
{
if ( x[cHull[i]] < bbox[0] )
bbox[0] = x[cHull[i]];
Expand All @@ -690,8 +679,14 @@ CHullBox PointSet::compute_chull_bbox()
bbox[3] = y[cHull[i]];
}

OrientedConvexHullBoundingBox finalBb;

dref = bbox[2] - bbox[0];
const double dref = bbox[2] - bbox[0];
if ( qgsDoubleNear( dref, 0 ) )
{
ok = false;
return finalBb;
}

for ( alpha_d = 0; alpha_d < 90; alpha_d++ )
{
Expand Down Expand Up @@ -722,22 +717,22 @@ CHullBox PointSet::compute_chull_bbox()
bb[15] = bb[13] - d1; // hx, hy

// adjust all points
for ( i = 0; i < 16; i += 4 )
for ( int i = 0; i < 16; i += 4 )
{

alpha_seg = ( ( i / 4 > 0 ? ( i / 4 ) - 1 : 3 ) ) * M_PI_2 + alpha;

best_cp = std::numeric_limits<double>::max();
for ( j = 0; j < nbPoints; j++ )
double best_cp = std::numeric_limits<double>::max();
for ( int j = 0; j < nbPoints; j++ )
{
cp = GeomFunction::cross_product( bb[i + 2], bb[i + 3], bb[i], bb[i + 1], x[cHull[j]], y[cHull[j]] );
const double cp = GeomFunction::cross_product( bb[i + 2], bb[i + 3], bb[i], bb[i + 1], x[cHull[j]], y[cHull[j]] );
if ( cp < best_cp )
{
best_cp = cp;
}
}

distNearestPoint = best_cp / dref;
const double distNearestPoint = best_cp / dref;

d1 = std::cos( alpha_seg ) * distNearestPoint;
d2 = std::sin( alpha_seg ) * distNearestPoint;
Expand All @@ -749,10 +744,10 @@ CHullBox PointSet::compute_chull_bbox()
}

// compute and compare AREA
width = GeomFunction::cross_product( bb[6], bb[7], bb[4], bb[5], bb[12], bb[13] ) / dref;
length = GeomFunction::cross_product( bb[2], bb[3], bb[0], bb[1], bb[8], bb[9] ) / dref;
const double width = GeomFunction::cross_product( bb[6], bb[7], bb[4], bb[5], bb[12], bb[13] ) / dref;
const double length = GeomFunction::cross_product( bb[2], bb[3], bb[0], bb[1], bb[8], bb[9] ) / dref;

area = width * length;
double area = width * length;

if ( area < 0 )
area *= -1;
Expand All @@ -769,10 +764,7 @@ CHullBox PointSet::compute_chull_bbox()
}

// best bbox is defined

CHullBox finalBb;

for ( i = 0; i < 16; i = i + 4 )
for ( int i = 0; i < 16; i = i + 4 )
{
GeomFunction::computeLineIntersection( best_bb[i], best_bb[i + 1], best_bb[i + 2], best_bb[i + 3],
best_bb[( i + 4 ) % 16], best_bb[( i + 5 ) % 16], best_bb[( i + 6 ) % 16], best_bb[( i + 7 ) % 16],
Expand All @@ -783,6 +775,7 @@ CHullBox PointSet::compute_chull_bbox()
finalBb.width = best_width;
finalBb.length = best_length;

ok = true;
return finalBb;
}

Expand Down
10 changes: 6 additions & 4 deletions src/core/pal/pointset.h
Expand Up @@ -52,7 +52,10 @@ namespace pal

class PointSet;

struct CHullBox
/**
* Represents the minimum area, oriented bounding box surrounding a convex hull.
*/
struct OrientedConvexHullBoundingBox
{
double x[4];
double y[4];
Expand Down Expand Up @@ -112,10 +115,9 @@ namespace pal
bool containsLabelCandidate( double x, double y, double width, double height, double alpha = 0 ) const;

/**
* Computes a con???? hull. Maybe convex, maybe concave. The person who wrote this
* had no care for anyone else ever reading their code.
* Computes an oriented bounding box for the shape's convex hull.
*/
CHullBox compute_chull_bbox();
OrientedConvexHullBoundingBox computeConvexHullOrientedBoundingBox( bool &ok );

/**
* Split a concave shape into several convex shapes.
Expand Down

0 comments on commit 6a77947

Please sign in to comment.