Boost logo

Geometry :

Subject: [geometry] "invalid" box geometry
From: Volker Schöch (vschoech_at_[hidden])
Date: 2014-11-17 05:10:24


let's have another look at the domain of definition of boost::geometry algorithms. As far as I understand, most algorithms have well-defined behavior for input that satisfies the is_valid(...) predicate. Exceptions include, obviously, the is_valid(...) predicate itself, which should be well-defined for all technically possible input values.

For the time being, let's focus on the difference(...) algorithm. I assume the following, please correct me if I'm wrong:

· For input geometries that satisfy the is_valid(...) predicate, the output geometry represents the mathematically correct difference, and the output geometry satisfies the is_valid(...) predicate.

· For other input geometries, the algorithm should not crash (no infinite loops, no access to uninitialized memory, etc.) but the output geometry is not necessarily useful in any way.

Now let's return to my example from the "access violation" issue. Note that _intPolygon is a model for boost::geometry::multi_polygon, and _intRect is a model for boost::geometry::box. _intPolygon is oriented couter-clockwise and not closed, points are based on int.

_intPolygon polygonA;
GEOMETRYERR( boost::geometry::read_wkt("MULTIPOLYGON(((488 2035,527 2035,527 2093,488 2093)))", polygonA), "polygonA" );
_ASSERT( boost::geometry::is_valid(polygonA) ); // holds

_intRect rectB;
GEOMETRYERR( boost::geometry::read_wkt("BOX(417 2064,597 2064)", rectB), "rectB" );
_ASSERT( boost::geometry::is_valid(rectB) ); // does NOT hold

_intPolygon polygonC;
GEOMETRYERR( boost::geometry::difference(polygonA, rectB, polygonC), "boost::geometry::difference" );

Given this example, what is your advice how to deal with the invalid rectangle rectB?

· There is no equivalent rectangle ("box") that satisfies the is_valid(...) predicate.

· Is an empty multi-polygon an adequate representation for rectB?

· Is there any way that I can invoke the difference algorithm with this input, and get a reasonable result (i.e., unchanged polygonA)?

· Do I have to wrap all calls to the difference algorithm by

o A conversion of boxes to (potentially empty) multi-polygons,

o or a separate code path that in this case would return polygonA without invoking the difference algorithm?

o What are the criteria for a conversion to an empty multi-polygon, or a separate code path that does not invoke the difference algorithm? Is it boost::geometry::area(rectB) <= 0? Sounds good for int-based rectangles; does the same criterion apply to float-based rectangles?

As you can see, I'm just throwing some random thoughts at the wall to see if something sticks. I would appreciate your advice for a sound best practice, whether or not that's among my suggestions.

Thanks in advance

Volker Schöch | vschoech_at_[hidden]<mailto:vschoech_at_[hidden]>
Senior Software Engineer
We are looking for C++ Developers:
think-cell Software GmbH>
Chausseestr. 8/E        phone / fax     +49 30 666473-10 / -19
10115 Berlin, Germany   US phone / fax  +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

Geometry list run by mateusz at