<div dir="ltr">A bit more information on the Franklin Area-Of-Intersection algorithm, after an initial pass at implementing it:<div><br></div><div>1. It does seem to work! (which wasn't really in doubt, but still it seems a bit magical...)</div><div>2. I am no longer optimistic that it will provide a faster algorithm.  The reasons are that it still has to determine all segment intersections, which is the main cost of overlay.  And, it has to do a lot of point-in-polygon tests, which might actually make it slower. This is the downside of using a structure which contains only the vertices, with no topological information.</div><div>3. It should be fully robust, up to numerical approximation.  Not sure if this makes it appealing to use - this depends on how often topology issues are encountered in actual use.</div></div><br><div class="gmail_quote"><div dir="ltr">On Tue, Oct 23, 2018 at 10:35 AM Martin Davis <<a href="mailto:mtnclimb@gmail.com">mtnclimb@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div dir="ltr">W. R. Franklin was one of the early researchers into polygon overlay, and he published a paper "Calculating the Area of Overlaid Polygons Without Constructing the Overlay" back in 1994 [1]. Unfortunately behind a paywall, but maybe further sleuthing will uncover it in a dusty corner of the net.</div><div dir="ltr"><br></div><div dir="ltr">It's not obvious to me that his algorithm could have a lower computational complexity, but the constant factor might be lower.  And possibly there's a robustness advantage too.<br><div><br></div><div>[1] <a href="https://www.researchgate.net/publication/2804714_Calculating_the_Area_of_Overlaid_Polygons_Without_Constructing_the_Overlay" target="_blank">https://www.researchgate.net/publication/2804714_Calculating_the_Area_of_Overlaid_Polygons_Without_Constructing_the_Overlay</a></div></div></div><br><div class="gmail_quote"><div dir="ltr">On Tue, Oct 23, 2018 at 10:04 AM Paul Ramsey <<a href="mailto:pramsey@cleverelephant.ca" target="_blank">pramsey@cleverelephant.ca</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div style="word-wrap:break-word;line-break:after-white-space">The first GIS system I ever used had an “intersection area” function that was distinct from, and faster than, the full-on “intersection” function that output a new geometry. I wonder if there is some possibility there…<div><br></div><div>P<br><div><br><blockquote type="cite"><div>On Oct 23, 2018, at 6:01 PM, Darafei Komяpa Praliaskouski <<a href="mailto:me@komzpa.net" target="_blank">me@komzpa.net</a>> wrote:</div><br class="m_8471497547510433023m_8521531483276131651Apple-interchange-newline"><div><div dir="ltr">Hi,<div><br></div><div>I have two polygonal layers to intersect and need to measure area of intersections.</div><div><br></div><div>ST_Area(ST_Intersection(a.geom, b.geom)) works fine, but is rather slow. Typical polygon on first side has <10 edges, on second 200..1000 edges.</div><div><br></div><div>What are my options to make it faster? Any ideas, links, experiences to share are welcome.</div><div><br></div><div>For starters, this seems to work faster than vanilla ST_Intersection in my case:</div><div><pre style="font-family:"Courier New""><span style="color:rgb(0,0,128);font-weight:bold">create or replace function </span><span style="font-style:italic">clipped_st_intersection</span>(geom1 <span style="color:rgb(0,0,128);font-weight:bold">geometry</span>, geom2 <span style="color:rgb(0,0,128);font-weight:bold">geometry</span>)<br>  <span style="color:rgb(0,0,128);font-weight:bold">returns geometry<br></span><span style="color:rgb(0,0,128);font-weight:bold">as </span><span style="color:rgb(0,128,0);font-weight:bold">$$</span><span style="color:rgb(0,0,128);font-weight:bold">select </span><span style="font-style:italic">ST_Intersection</span>(<br>              <span style="color:rgb(0,0,128);font-weight:bold">case<br></span><span style="color:rgb(0,0,128);font-weight:bold">                when </span><span style="font-style:italic">ST_MemSize</span>(geom1) > <span style="color:rgb(0,0,255)">160 </span><span style="color:rgb(0,0,128);font-weight:bold">then </span><span style="font-style:italic">ST_ClipByBox2D</span>(geom1, geom2)<br>                <span style="color:rgb(0,0,128);font-weight:bold">else </span>geom1 <span style="color:rgb(0,0,128);font-weight:bold">end</span>, <span style="color:rgb(0,0,128);font-weight:bold">case<br></span><span style="color:rgb(0,0,128);font-weight:bold">                when </span><span style="font-style:italic">ST_MemSize</span>(geom2) > <span style="color:rgb(0,0,255)">160 </span><span style="color:rgb(0,0,128);font-weight:bold">then </span><span style="font-style:italic">ST_ClipByBox2D</span>(geom2, geom1)<br>                <span style="color:rgb(0,0,128);font-weight:bold">else </span>geom2 <span style="color:rgb(0,0,128);font-weight:bold">end</span>)<span style="color:rgb(0,128,0);font-weight:bold">$$<br></span><span style="color:rgb(0,0,128);font-weight:bold">language sql<br></span><span style="color:rgb(0,0,128);font-weight:bold">immutable<br></span><span style="color:rgb(0,0,128);font-weight:bold">strict<br></span><span style="color:rgb(0,0,128);font-weight:bold">parallel safe</span>;</pre></div></div>-- <br><div dir="ltr" class="m_8471497547510433023m_8521531483276131651gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Darafei Praliaskouski<br>Support me: <a href="http://patreon.com/komzpa" target="_blank">http://patreon.com/komzpa</a></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" target="_blank">https://lists.osgeo.org/mailman/listinfo/postgis-devel</a></div></blockquote></div><br></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></blockquote></div>
</blockquote></div>