Geometry Boost List: Re: [geometry] single-point polygons

Subject: Re: [geometry] single-point polygons
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2014-10-13 11:34:30

Adam Wulkiewicz wrote:
> Hi,
>
> Volker Schöch wrote:
>>
>> It is now my understanding that WKT demands closing points for 
>> polygons. The following should be a well-formed polygon:
>>
>> POLYGON((2079 1968,2301 1968,2079 1968))
>>
>
> No, it should be invalid. A valid Polygon should have a non-0 area. 
> This means that it should at least be a triangle - contain 3 points 
> for open, 4 points for closed.
> You may now call bg::is_valid() to check it however it is as 
> computionally expensive as set or relation operation, e.g. intersects().
>
>> Calling remove_spikes on the resulting polygon, and outputting it as 
>> WKT, results in the following (boost 1.56.0):
>>
>> POLYGON((2079 1968))
>>
>> My questions:
>>
>> -Is this expected (no closing point)?
>>
>> -I presume that for some algorithms (which?) the position of the 
>> single point makes a difference while for others, like difference, 
>> any empty polygon should create the same result. Is this correct?
>>
>> -A year ago I made a note in my code that some algorithms cannot deal 
>> with input polygons that contain spikes (Boost.Geometry Overlay 
>> invalid input exception results). Therefore I established an 
>> invariant for my own polygons, that requires all polygons to be free 
>> of spikes. Is this still necessary?
>>
>> -How is a single-point polygon different from a spike?
>>
>> -If spikes are not allowed, how should single-point polygons be dealt 
>> with? Should they be considered empty, and have their last remaining 
>> point removed before passing them to, e.g., the difference algorithm? 
>> Or is some wrapper code required that avoids calling certain 
>> algorithms with single-point polygons?
>>
>> My internal representation is oriented counter-clockwise and not 
>> closed, my point type is based on int.
>>
>
> I'd say that remove_spikes() assume that the Polygon is valid and 
> since an invalid one is passed it treats it as a one spike which is 
> removed.
>

This is not precise enough, sorry. A Polygon containing spikes is of 
course invalid so remove_spikes() can't assume that it is. It just 
naiively remove spikes which in some cases may result in a Polygon 
containing to small number of Points.

> I guess at the end we could check the number of Points and throw an 
> exception if the result contained too small number of Points.
> In some cases numbers of Points are checked at the beginning of a 
> function, maybe for "mutable" functions we should also check this at 
> the end?

Another possible solution would be to generate invalid Polygon but, 
containing the "correct" number of Points, e.g.:
POLYGON((2079 1968,2079 1968,2079 1968,2079 1968)) for closed

Btw, this is related to convex_hull() for a 1- or 2-Point geometry 
(https://github.com/boostorg/geometry/pull/152).

Regards,
Adam