Boost logo

Geometry :

Subject: Re: [geometry] Equivalence between (multi-)polygons with spikes (1)
From: Volker Schöch (vschoech_at_[hidden])
Date: 2014-11-20 06:43:55

vs> Corollary: If for some multi-polygon P, is_valid(remove_spikes(P)) holds, then for all purposes of boost::geometry, remove_spikes(P) is equivalent to P.

bg> Seeing also your ticket - no, this does not hold. remove_spikes removes the spikes in polygons. That does not necessarily result in a valid (multi)polygon. The geometry may still be invalid, but due to other invalidities.

I think this is understood, see the highlighted precondition in my text above. If after removing the spikes the polygon is still invalid: Tough luck, separate discussion. But *if* after removing the spikes we end up with a valid polygon, *then* for all purposes of boost::geometry there is no difference between the original polygon and the result from remove_spikes().

This seems to be a necessary consequence of treating polygons with spikes as invalid: Excluding the set of (otherwise valid) polygons with spikes from the domain of definition for your algorithms is to say that you consider polygons with spikes irrelevant. You are basically saying, the algorithms do not need to take these cases into account, because these cases would add complexity requirements (time, space, code) without solving any actual problem. Which is to say that all problems involving spikes can be mapped to simpler problems that do not contain spikes and have an equivalent solution. Which is to say, that an (otherwise valid) polygon with spikes is equivalent to itself with the spikes removed.

If you do not agree with the above, that would mean that polygons with spikes do not have equivalent counterparts without spikes, and that the algorithms (union, difference, etc.) should yield substantially different results for polygons with spikes, and that you are by way of definition simply excluding the whole problem from boost::geometry. I don't believe that this is what you're up to.



Volker Schöch | vschoech_at_[hidden]<mailto:vschoech_at_[hidden]>
Senior Software Engineer
We are looking for C++ Developers:
think-cell Software GmbH>
Chausseestr. 8/E        phone / fax     +49 30 666473-10 / -19
10115 Berlin, Germany   US phone / fax  +1 800 891 8091 / +1 212 504 3039
Amtsgericht Berlin-Charlottenburg, HRB 85229 | European Union VAT Id DE813474306
Directors: Dr. Markus Hannebauer, Dr. Arno Schödl

Geometry list run by mateusz at