Boost logo

Geometry :

From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-05-23 16:36:11


Bluespider Via Geometry wrote:
> Hi I'm not new to boost but am new to boost geometry.
> I have been using the dissolve functionality to process degenerate polygons.
> By degenerate I mean that these polygons usually have some self
> intersections and that the objective of processing here is to create a
> bounding polygon. All self intersections will be internal. Let me explain...
> A poly line is the starting point and in my application this is the route of
> a submarine cable or pipeline. We from that route we want to create a
> polygon which surrounds a section of the route. In other words the polygon
> is first created by running down the left and right sides of the route and
> taking the perpendicular position offset by a fixed amount from each
> waypoint. On close (smaller than half the corridor width) pairs of turns of
> the route the side with the smaller angle can be left with a self
> intersection.

It's hard to imagine what's happening from the description. I don't
fully understand the algorithm but assuming you want to find a bounding
polygon (without holes) enclosing a fragment of polyline or some other
set of points could convex_hull() be useful to you instead of dissolve()?

> Now with the same starting route line (several thousand points) and certain
> distances for the corridor width I can successfully use
> boost:geometry:dissolve and create a perfect result. One that I can then
> reduce down to a polygon with fewer vertices in order to then use it in a
> geospatial query. BUT often I instead end up with an empty output polygon or
> a list of one or more tiny polygons. The main bulk of the area of interest
> is then lost completely. Changing the corridor width by a tiny tiny fraction
> can mean the difference between success and failure and it may have
> something to do with the total number of self intersections but that's the
> only clue I have right now. I did find one case where scaling the values of
> the input coordinates made a difference to the results but it was still a
> degenerate result.

dissolve() is not officially released AFAIU becasue it's not ready yet
so it's not a surprise that it may generate invalid results.
If you found a case when it fails you could report it at GitHub

> I understand from the source that there is a Strategy template argument but
> don't understand its possible use here although it looks like it could
> perhaps determine a winding policy.

Strategies are used to define coordinate-system specific behavior of an
algorithm. If you found a case which fails when it should not in a given
coordinate system the Strategy will probably not help, unless there is
some bug in the default cartesian strategy which is used in your case.
However then this bug should rather be fixed in the strategy itself. But
I doubt passing different strategy would improve the results of
dissolve(). It is in the extensions and it doesn't work flawlessly so my
guess is that this is a bug in the algorithm.

And btw the strategy which is expected is segments intersection
strategy, so one of these:

See accordingly:

The last one allows you to choose geographic formulas (accuracy v.s.
speed) and pass specific spheroid model (in case you wanted to use
something different than WGS84).

> Right now I'm struggling with lack of documentation here and also I'm using
> Microsoft compiler which doesn't help much when debugging template sources.
> Does anyone have an example of using dissolve with strategy or can suggest
> any other docs?
Since it's a part of the extensions it's not documented indeed.
The only places I know where examples of dissolve() can be found is
Berend's blog:
and tests:
But the latter is as simple as you'd expect. The algorithm has the same
interface as any 1-argument mutable operation for polygons. It takes
polygon and returns multi_polygon as output argument.

See also:

> Having already abandoned use of boost::geometry::simplify (ironically due to
> compile errors) and instead rolling my own Douglas-Puecker I find using
> boost::geometry to be rather time consuming and life is too short for that.

AFAIU simplify() is well documented:
What problems have you experienced?

> Also of interest is the CoordinateSystem template arg to
> boost::geometry::model::point and a discussion regarding this could be
> useful. My data is actually geospatial of course so for some algorithms non
> cartesian calculations could be a great benefit but although I can see that
> there could be some support for this I have nothing much to help get
> started.
CoordinateSystem is used in algorithms to automatically instantiate the
default coordinate-system-specific Strategy. So indeed, if your segments
are long or segments may cross antimeridian (meridian of longitude
180deg), cartesian coordinate system could be not accurate enough for
you or not work correctly. If that was the case you could use e.g.
bg::spherical_equatorial<bg::degree>. The results would be more accurate
but the algorithms would be slower.


Geometry list run by mateusz at