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

Subject: Re: [geometry] Spikes and area
From: Barend Gehrels (barend_at_[hidden])
Date: 2014-04-10 06:39:50

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.

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