StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here is one way. By rotating one polygon to the XY plane, you reduce the 3D problem to a 2D problem (mostly), and it is normally not too much of a performance issue.</p> <ol> <li>Rotate the points of first polygon so that it lies on the X-Y plane.</li> <li>Rotate the points of the second polygon the same direction and amount as the first.</li> <li>Check each line in the second polygon and see whether and where it intercepts the X-Y plane. With a convex polygon, this should happen twice, at points A and B.</li> <li>Find all the intersections of line AB with the edges of the first polygon. There should be 0, 1, or 2 intersections if the first polygon is convex.</li> <li>Case: Zero Intersections: the line AB is either completely inside or out the first polygon. If inside, AB is the intersecting line of the planes. If outside, there is no intersection.</li> <li>Case: One intersection, point C: Either A or B is inside the first plane. That intersecting line of the planes is that inside point (A or B) to C.</li> <li>Case: Two intersections: The intersecting line of the planes is AB</li> <li>Rotate the intersecting line back to its original position, the reverse of the rotation done in step 1.</li> </ol> <p>It is left as an exercise to the reader to extend this method to non-convex polygons. :) (It's actually pretty easy.)</p> <p>One way to check to see if a point is inside a 2D polygon is to get the intersections of a line from that point upward with all the edges of the polygon. 0 or 2: outside. 1: inside. (This also works for a non-convex polygon using even and odd for outside and inside.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload