|
|
Geometry : |
Subject: [geometry] duplicate points in polygon
From: Volker Schöch (vschoech_at_[hidden])
Date: 2013-06-28 05:13:01
Hi all,
I have a couple of questions regarding duplicate points in polygons. What are your best practices?
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 )
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?
- 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?
- 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.
- 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.
Thank you for any insights, practical or philosophical.
Regards
Volker