|
|
Geometry : |
Subject: Re: [geometry] difference algorithm produces invalid polygon?
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2012-03-01 13:09:05
From: Volker Schöch
> > Strictly speaking, this means that your algorithms are not closed (domain of definition of f is not a superset of the image of f) which leaves me scratching my head with regard to the >>definition of "valid" polygons (I understand it's a given by OGC and hardly debatable).
> Yes, I understand this though I did not see it until now. But admitted, did not heavily test with all kinds of integer input.
One thing to add, it is not just spikes and zero area polygons that will be a problem here. When the intersection of two line segments is snapped to the integer grid it moves those line segments over slightly. This can be enough to cross some other vertex of the output polygon creating a self intersecting polygon. This could happen even when snapping to the floating point grid (it would be trival to construct an example) but is much more likely to happen in integer domain. No polygon clipping algorithm that snaps intersection to a coordinate grid is closed unless it looks also for "near intersections" and handles them. This is relatively easy with integer, and is possible with floating point also, though I didn't read that paper very closely because I had already chosen to use integer. The reason Polygon is relatively slow is because it goes to a lot of work to make sure to handle such things as best as possible. Since any possible input is acceptable to Polygon, Polygon is trivially closed, but Polygon guarantees the strongest possible post conditions while requiring the weakest possible preconditions. The idea is that Polygon is trying to satisfy the pre-conditions of whatever else might consume its output without imposing any post-conditions on whatever else might produce its input. This allows it to be plugged in to pretty much any application and be expected to work.
Regards,
Luke
Geometry list run by mateusz at loskot.net