Boost logo

Geometry :

Subject: Re: [geometry] Spikes and area
From: Barend Gehrels (barend_at_[hidden])
Date: 2014-04-10 07:02:54

Hi Volker again,

Barend Gehrels wrote On 10-4-2014 12:39:
> Hi Volker,
> Volker Schöch wrote On 9-4-2014 16:25:
>> Hi,
>> Please correct me if I'm wrong:
>> -Any (multi-)polygon that only consists of spikes has area 0 (zero).
> That is correct.
>> -Any (multi-)polygon that has area 0 (zero) and does not have any
>> inside-out or self-intersecting polygons, is either empty or consists
>> of only spikes.
> That is possible but not always the case.
>> As far as I understand, the algorithms in boost::geometry require
>> that input polygons do not contain spikes, and the results of these
>> algorithms can be assumed to not contain spikes either. What's the
>> definition of a spike? This seems to imply that as long as I only
>> deal with positive-area multi-polygons, zero area should be
>> equivalent to a completely empty multi-polygon.
>> Interestingly, boost::geometry::remove_spikes( "MULTIPOLYGON(((4287
>> 2160,5984 2160)))" ) does not modify the input at all, and this is an
>> example of a non-empty, zero-area multi-polygon that does not seem to
>> contain spikes (b/c remove_spikes does not change a thing). What am I
>> missing?
> This is not a spike, even though it has zero area. This is just a
> segment and therefore forming an invalid polygon. A spike goes forward
> and then backward over the same path, so it covers the same
> linesegment twice. So (1 1,3 1,1 1) for example, covering (1,1)..(3,1)
> twice. Or partly backwards, such as (1 1,3 1,2 1) covering
> (1,1)..(2,1) twice. Or backwards and beyond (1 1,3 1,0 1), etc. Spikes
> can of course also make angles, so go forward over several segments
> and backward over the same segments.

Of course, if your polygon is open (and it is, you noted that
explicitly, as always ;-) ) it goes implicitly back to the starting
point and it is a spike indeed, I realized that just after sending the mail.
So yes, this spike is not detected. Because at the start of the
detection the minimum size of a polygon is considered, and 2 is lower
than that. Also for closed polygons it will not be detected. That can
both be fixed. Can you create a ticket?

> There are cases where paths go forward and backward over the same
> path, but which are not spikes:
> ---------- ----------
> | | | |
> | |----| |
> | |f/b | |
> --------- ----------
> (use courier font to see it correctly)
> The segment "f/b" in the middle goes forward and after creating a
> correct ring goes backward over the same path, this one is not
> detected as a spike, though it makes the polygon invalid.
> But just one segment is not a spike. Therefore your input is unaltered.
> Another sample of an invalid polygon with area 0, not being a spike,
> is just MULTIPOLYGON(((4287 2160))), one point.
> But thanks for your questions, it is indeed good to get the definition
> clear.
> B.T.W. I did not react on your last bug report, but it is noted and
> will be worked on, there are still some tickets open.

Regards, Barend

Geometry list run by mateusz at