<div dir="ltr"><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">Hello everyone,</span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> I am working with a group of researchers on developing an algorithm to decompose 2D polygons into meaningful parts, without using triangulations.</span></span><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> </span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> Our algorithm relies on spatial set operations</span></span></span><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">.</span></span> <span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> Due to finite-precision floating point arithmetic, as clarified in the Robustness section of the GEOS FAQs, as well as in section D.7 of the JTS FAQs, some predicates do not necessarily agree in theory and practice.</span></span><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> However, I am interested in finding out if there is any proof for the following predicate, for which I do not find in practice that differ from the theory:</span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">Given two polygons P and Q, which overlaps:</span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> - <b>((P difference Q) touches (P difference(P difference Q)))</b> seems to be always True and the intersection between their boundaries has dimension 1 (their interiors do not intersect and their boundaries have at least one segment in common).<br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> </span></span></span><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"> If you know of any academic article in which this case has been investigated, applied to </span></span></span><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">finite-precision floating point computations, </span></span></span><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">even if you knew a counterexample, it would be of great help in our research.</span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb"><br></span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">Regards, and thank you very much for your great work,</span></span></span></div><div><span class="gmail-HwtZe" lang="en"><span class="gmail-jCAhz gmail-ChMk0b"><span class="gmail-ryNqvb">Gabriel<br></span></span></span></div></div>