compact abyss
Hi all! I have two simple polygons represented by arrays of 2D vertices:
polygon1 = [[0,0],[1,0],[1,1],[0,1]]
polygon2 = [[0.5,-0.5],[1.5,0.5],[0.5,1.5]].
I would like to know if the two polygons intersect. How can I achieve this?
I am attaching a picture as an example.
Thanks in advance
queen harbor
This is traditionally a tricky question. The simplest thing is to test whether any of the verts of one polygon are inside the other, but as you show that's not always sufficient. You can test each line segment against each other line segment (along with a single point-in-poly test each way to cover the test where one polygon entirely contains the other), but that's expensive (though fine unless your polygons have dozens and dozens of vertices). A scanline approach is probably most general-purpose: https://en.wikipedia.org/wiki/Bentley–Ottmann_algorithm
Basically unless your polygons have a LOT of vertices I'd go segment-to-segment.
compact abyss
Thanks for the answer. I wanted to at least be sure there is no THREE function for this, so now I can move on to other solutions. I think your rationale excludes some edge cases unfortunately, look at the picture I send attached. I found this function on github which seems to work wonderfully (you can test it interactively: https://github.com/vrd/js-intersect), but for some reason I found it gets stuck on an infinite loop for some polygons. I think I would rather give the problem a go myself than to debug the function. I'm thinking about, for the case where no points are inside one another and some edges are coincident, to check if the cross product between the z-axis and each coincident edge point to the same side: if so, then the polygons intersect, if not they do not. This assumes the coordinates of the vertices are oriented clockwise, which is my case. If you have any further idea it would be greatly appreciated!
