<div dir="ltr"><br><div class="gmail_quote"><div dir="ltr">On Fri, Oct 26, 2018 at 6:09 AM Darafei "Komяpa" Praliaskouski <<a href="mailto:me@komzpa.net">me@komzpa.net</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">It looks like for polygon / box intersection area can be calculated in O(n), by just clamping the ordinates (<a href="https://github.com/postgis/postgis/commit/3233ccd19cdb6958b53164262cd812d3f6d70fb2" target="_blank">https://github.com/postgis/postgis/commit/3233ccd19cdb6958b53164262cd812d3f6d70fb2</a>). </div><div dir="ltr"><br><div>It also may be adapted for any convex polygons, with O(n*m) though. Convex check also seems to be O(n). Building dataset tends to be mostly convex (and mostly 4-corner), so this may be a specialized fast path.</div><div><br></div><div>Is there a chance we may want BOX() as new geometry primitive to save a is_convex / is_box check? :)</div><div><br></div><div>Any other thoughts?</div><div><div class="gmail_quote"><div dir="ltr"><br></div></div></div></div></div></blockquote><div>Isn't BOX axis-aligned (ortholinear)?  Is this really a common occurrence in building footprints?   </div><div><br></div><div>There's probably more optimal intersection code that could be developed for quadrilaterals.  I'm still optimistic that the Franklin Fast Overlay Area approach holds some promise as well.</div><div><br></div><div>It's pretty fast to check for rectangular or quadrilateral geometry where an optimization for those exists.  So that doesn't seem like a reason to incur the overhead of developing and maintaining a new Geometry type.</div></div></div>