Geometry Boost List: Re: [geometry] duplicate points in polygon

Subject: Re: [geometry] duplicate points in polygon
From: Barend Gehrels (barend_at_[hidden])
Date: 2013-07-04 18:29:19

Hi Volker,

Sorry for the late reply on this.

On 28-6-2013 11:13, Volker Schöch wrote:
>
>
> I presume that there is consensus that the following polygons must be 
> treated as equivalent, i.e., they should yield the "same" results 
> (modulo duplicate points) when used as input to geometric operations:
>
> P1( 1/1, 1/2, 2/2, 2/1 )
>
> P2( 1/1, 1/1, 1/2, 2/2, 2/2, 2/2, 2/1, 1/1 )
>

They are indeed spatially equal. So boost::geometry::equals(P1, P2) 
should return true (did not check explicitly now).

> Polygons like P2 frequently occur in our application, e.g, when a 
> pentagon degenerates to a triangle or a point. In that case, the 
> pentagon's outline is still constructed from 5 points, but some of 
> those points may represent the same values.
>
> -What is your design rationale in the polygon algorithms? Is there any 
> special treatment for duplicate points or do algorithms just deal with 
> these points as with any others?
>

There is a special treatment.  For many basic operations (area, 
centroid, etc) the points are dealt with as any other points. But for 
(e.g.) the overlay operations, the polygons are first "sectionalized" 
and in that process duplicate points are recognized, and skipped later 
on, because they disturb the process. Disturb can mean: if you want to 
know if a polygon goes left, right or straight ahead, and you encounter 
a duplicate point, you still don't know that.

> -Are there any invariants or assumptions made regarding duplicate 
> points, e.g., if the input to an algorithm does not have duplicate 
> points, the output does not have them either?
>

In the output duplicate points are skipped too. Even if the input does 
not contain duplicate points, the raw  output might in some 
configurations contain duplicate points, and they are explicitly skipped 
(however, this is not checked). This is done in a later phase of the 
library, at first they were just included.

> -Can you give me any advice how to deal with duplicate points? Should 
> they simply be ignored, or should duplicate points be removed at the 
> earliest possible, thus "normalizing" the polygon representation? 
> Either way -- why? It is probably impossible to get rid of duplicate 
> points entirely, at least in a floating point situation, where it is 
> not trivial to determine if two values are equal.
>

You can use boost::geometry::unique(polygon). But this is not required, 
the algorithms we provide should handle them correctly. However it is 
always possible that you at one time need to get rid of them yourself.

> -What does this say about (explicitly) closed vs. open (implicitly 
> closed) polygon representation? After all, the closing point is just a 
> special case of a duplicate point. What if in an "open" 
> representation, the last point is equal to the first point? Should 
> this case be avoided? All above considerations apply.
>

Good point - I have to check if this is the case indeed. If not, it 
might be a source for errors (see disturb above).

> Thank you for any insights, practical or philosophical.
>

:-) You are welcome

Regards, Barend