<div dir="ltr"><div class="gmail_default" style="font-family:monospace,monospace">Thank you everybody for your quick responses! </div><div class="gmail_default" style="font-family:monospace,monospace">I know first hand how making a geometric algorithm robust to precision is challenging,</div><div class="gmail_default" style="font-family:monospace,monospace">I appreciate your efforts :-)<br></div><div class="gmail_default" style="font-family:monospace,monospace"><br></div><div class="gmail_default" style="font-family:monospace,monospace">Remi<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Le jeu. 20 avr. 2023 à 21:18, Regina Obe <<a href="mailto:lr@pcorp.us">lr@pcorp.us</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div class="msg-4449303469474218318"><div lang="EN-US"><div class="m_-4449303469474218318WordSection1"><p class="MsoNormal"><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)">I have ticketed - <a href="https://github.com/libgeos/geos/issues/875" target="_blank">https://github.com/libgeos/geos/issues/875</a><u></u><u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p><p class="MsoNormal"><span style="font-size:11pt;font-family:"Calibri",sans-serif;color:rgb(31,73,125)"><u></u> <u></u></span></p><div style="border-color:currentcolor currentcolor currentcolor blue;border-style:none none none solid;border-width:medium medium medium 1.5pt;padding:0in 0in 0in 4pt"><div><div style="border-color:rgb(225,225,225) currentcolor currentcolor;border-style:solid none none;border-width:1pt medium medium;padding:3pt 0in 0in"><p class="MsoNormal"><b><span style="font-size:11pt;font-family:"Calibri",sans-serif">From:</span></b><span style="font-size:11pt;font-family:"Calibri",sans-serif"> postgis-devel [mailto:<a href="mailto:postgis-devel-bounces@lists.osgeo.org" target="_blank">postgis-devel-bounces@lists.osgeo.org</a>] <b>On Behalf Of </b>Martin Davis<br><b>Sent:</b> Thursday, April 20, 2023 8:45 PM<br><b>To:</b> PostGIS Development Discussion <<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a>><br><b>Subject:</b> Re: [postgis-devel] ST_MaximumInscribedCircle madness<u></u><u></u></span></p></div></div><p class="MsoNormal"><u></u> <u></u></p><div><p class="MsoNormal">There's only one main loop, so an interrupt check can go there:<u></u><u></u></p><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal"><a href="https://github.com/libgeos/geos/blob/main/src/algorithm/construct/MaximumInscribedCircle.cpp#L187" target="_blank">https://github.com/libgeos/geos/blob/main/src/algorithm/construct/MaximumInscribedCircle.cpp#L187</a><u></u><u></u></p></div></div><p class="MsoNormal"><u></u> <u></u></p><div><div><p class="MsoNormal">On Thu, Apr 20, 2023 at 5:33 PM Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>> wrote:<u></u><u></u></p></div><blockquote style="border-color:currentcolor currentcolor currentcolor rgb(204,204,204);border-style:none none none solid;border-width:medium medium medium 1pt;padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in"><div><p class="MsoNormal">One thing we can do is find a reasonable place in the loop to put an interrupt check. Where does it spend its time when it’s in this state?<u></u><u></u></p><div><p class="MsoNormal"><br><br><u></u><u></u></p><blockquote style="margin-top:5pt;margin-bottom:5pt"><div><p class="MsoNormal">On Apr 20, 2023, at 5:31 PM, Martin Davis <<a href="mailto:mtnclimb@gmail.com" target="_blank">mtnclimb@gmail.com</a>> wrote:<u></u><u></u></p></div><p class="MsoNormal"><u></u> <u></u></p><div><div><p class="MsoNormal">That geometry is indeed a simple rectangle, but it's very, very, very narrow.   This is causing the interative algorithm used in MaximmumInscribedCircle to essentially hunt forever trying to find a point which lies inside the polygon.<u></u><u></u></p><div><p class="MsoNormal"><u></u> <u></u></p></div><div><p class="MsoNormal">Of course it would be nice to detect this situation and terminate faster, either with a point which lies actually lies outside the rectangle, or some other return value.  This will require some thought.<u></u><u></u></p></div></div><p class="MsoNormal"><u></u> <u></u></p><div><div><p class="MsoNormal">On Thu, Apr 20, 2023 at 2:38 PM Rémi Cura <<a href="mailto:remi.cura@gmail.com" target="_blank">remi.cura@gmail.com</a>> wrote:<u></u><u></u></p></div><blockquote style="border-color:currentcolor currentcolor currentcolor rgb(204,204,204);border-style:none none none solid;border-width:medium medium medium 1pt;padding:0in 0in 0in 6pt;margin-left:4.8pt;margin-right:0in"><div><div><p class="MsoNormal" style="margin-bottom:12pt"><span style="font-family:"Courier New"">Hello dear Postgis devs!<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">I have a strange case to submit to you.<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">In a nutshell, trying to compute <u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">```SQL<br>SELECT ST_MaximumInscribedCircle( 'POLYGON ((59.3 100.00000000000001, 99.7 100.00000000000001, 99.7 100, 59.3 100, 59.3 100.00000000000001))') ;<br>```<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">causes it to run for many minutes until it eventually errors.<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">Worst, running this kind of computing on 12M geoms in parallel x6 created a postgres **segfault** and crashed my server (16 cores, 64GB).<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">(many more geoms are making this function unhappy).<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New""><br>/!\ Once this query starts, it can't be stopped by `pg_cancel_backend(pid)` or even `pg_terminate_backend(pid)`<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">--> This is pretty dangerous in my opinion.<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New""><u></u> <u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New""><u></u> <u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">The geometry is simple, it is a rectangle.<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">I obtained it through other geometry operations<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">It must be some kind of precision issue, I'm wondering if there is some kind of infinite loop going on or something.<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New""><u></u> <u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">My full code is something like that:<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">```SQL<br>SELECT env, diff, ST_MaximumInscribedCircle(diff)<br>FROM CAST ('some_polygon'as text ) as g<br>    , ST_Envelope(g) as env<br>    , ST_MakeEnvelope(0,0,100,100) as bound<br>    , ST_Difference(env, bound) as diff;<br>```<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New""><u></u> <u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">Not creating a bug ticket as I don't know if I'm simply abusing the function / using it in a way it should not.<u></u><u></u></span></p></div><p class="MsoNormal"> <u></u><u></u></p><div><p class="MsoNormal"><span style="font-family:"Courier New""><u></u> <u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">POSTGIS="3.1.7 aafe1ff" [EXTENSION] PGSQL="140" GEOS="3.9.1-CAPI-1.14.2" PROJ="8.0.1" GDAL="GDAL 3.4.3, released 2022/04/22" LIBXML="2.9.1" LIBJSON="0.15" LIBPROTOBUF="1.3.2" WAGYU="0.5.0 (Internal)" RASTER<u></u><u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New""><u></u> <u></u></span></p></div><div><p class="MsoNormal"><span style="font-family:"Courier New"">PostgreSQL 14.7 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 7.3.1 20180712 (Red Hat 7.3.1-12), 64-bit<u></u><u></u></span></p></div></div><p class="MsoNormal">_______________________________________________<br>postgis-devel mailing list<br><a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br><a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><u></u><u></u></p></blockquote></div><p class="MsoNormal">_______________________________________________<br>postgis-devel mailing list<br><a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br><a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><u></u><u></u></p></div></blockquote></div><p class="MsoNormal"><u></u> <u></u></p></div><p class="MsoNormal">_______________________________________________<br>postgis-devel mailing list<br><a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br><a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><u></u><u></u></p></blockquote></div></div></div></div>_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@lists.osgeo.org" target="_blank">postgis-devel@lists.osgeo.org</a><br>
<a href="https://lists.osgeo.org/mailman/listinfo/postgis-devel" rel="noreferrer" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a><br>
</div></blockquote></div>