Boost logo

Geometry :

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


Geometry list run by mateusz at