<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Thu, Jun 25, 2020 at 3:47 PM Nyall Dawson <<a href="mailto:nyall.dawson@gmail.com">nyall.dawson@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">> Are the line segments in fully general position relative to the polygon? I.e. they range from just touching it to fully crossing it, and may intersect the boundary multiple times?<br>
<br>
They are actually "rays", possibly extending to infinity. But for the<br>
simplicity I've restricted them to fall inside the polygon's bounding<br>
box, since I only care about portion of the line within the polygon.<br>
So they:<br>
1. Will always intersect at least twice with the polygon exterior<br>
2. May possibly coincide exactly with one or more exterior/interior segments<br><br></blockquote><div>I've been thinking about this a bit more, and realized that lines being coincident with polygon segments makes this a bit harder.  What's needed is a simple "graph" structure along the line, which can determine which portions of the line are inside, outside or coincident.  Then the overlay result can be extracted from that.  There probably also needs to be a little bit of snapping done, in case intersections lie very close together (in which case they might reverse position along the line, causing mislabelled topology).</div><div><br></div><div>Also, rather than a linear scan of the polygon edges a spatial index can be used on the polygon (which can be reused).</div><div><br></div><div>All this suggests the possiblity of a new "OverlayPolygonLine" algorithm.  Even given the above, it will be quite a bit simpler than full overlay, and should be a lot faster too.  I am planning to prototype this in JTS to see how it works out.</div><div>  </div></div></div>