<div dir="ltr"><div class="gmail_quote"><div dir="ltr">On Fri, Oct 26, 2018 at 8:20 PM Martin Davis <<a href="mailto:mtnclimb@gmail.com" target="_blank">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"><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" target="_blank">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></div></blockquote><div><br></div></div><div dir="ltr"><div class="gmail_quote"><div>Usages I see for BOX are storing raster's pixels and things like parts clipped off by ST_Subdivide. This can also fix things like BoundingDiagonal having to exist in this form, as there's no easy option to store a multi-dimensional axis-aligned BOX in geometry.</div></div></div><div dir="ltr"><div class="gmail_quote"><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><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></div></blockquote><div><br></div><div>I've tried replacing box clipping with clip_to_ordinate range: <a href="https://github.com/Komzpa/postgis/pull/6">https://github.com/Komzpa/postgis/pull/6</a> <br></div><div><br></div><div>First observation: ST_Buffer can't reliably fix all the topological incorrectness after this clipping, and ST_MakeValid can't either. Any ideas of ready made functions that can help fix it?</div><div><br></div><div>Second observation: ST_Subdivide is a lot faster when it doesn't try to get valid geometry out, and only needs to check one axis. Point-in-polygon and ST_Area should work well for this case of invalidity, so it may be of some use there either.</div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><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></blockquote></div></div><div dir="ltr"><div><br></div>-- <br><div dir="ltr" class="m_1667619506772815388gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div>Darafei Praliaskouski</div><div>Support me: <a href="http://patreon.com/komzpa" target="_blank">http://patreon.com/komzpa</a></div></div></div></div></div></div>-- <br><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr">Darafei Praliaskouski<br>Support me: <a href="http://patreon.com/komzpa">http://patreon.com/komzpa</a></div></div>