Geometry Boost List: Re: [geometry] Spikes and area

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