StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My first observation about this problem is that the a rectangle (aligned with the axes) is a simple degenerate case. If two corners of that rectangle are: (x1,y1) and (x2,y2) then you simply test, given a point (x3,y3), that min(x1,x2) < x3 < max(x1,x2) and min(y1,y2) < y3 < max(y1, y3).</p> <p>This might also be a useful optimization. If we find axis-aligned bounding rectangle of our parallelogram then we can start with a quick test of any given point against that.</p> <p>If our parallels have non-zero slope then we compute the axis intersections of our bounding lines and the intersection of the lines that would pass through the point in question at those slopes. If both of our point's intersections (defined by both slopes) lies between our the intersections of our bounding lines then we're in. If either of this is out of those ranges then we're not.</p> <p>I don't have time to code up an example but computing these slopes and intersections are first year algebra.</p> <p>[Addenda]</p> <p>I see now that the first post (regarding ray from the point to be tested and extending along any arbitrary slope) is a reference to the general solution to this problem for any closed planar polygon ... or, in fact, for any closed planar curve. It can also be extended to three dimensions for closed surfaces.</p> <p>There is, however, one caveat that would apply to parallelograms nor to rhomboids. In the case of a concave polygon (or some other curves) if the ray hits any apex (corner) then it's possible that the test return an even number of "line" crossings. In other words any part of the "curve" which is simultaneously included in multiple "sides" of the polygon could return a false positive.</p> <p>Two solutions of this would be: explicitly test for intersections at line segment limits (corner/apexes) or treat each line segment as bounded on one end by (point + epsilon) (so that our computations won't find any point in common between any two sides).</p> <p>My idea of finding a bounding rectangle is still a useful quick test and does extend generally to all polygons. We find the min() and max() x to find the left and right bounding sides and the min() and and max() y to find the bottom and top bounds. This also can be extended to three dimensions ... and a friend tells me that standard graphics libraries use this extensively for collision detection in most virtual reality and MMORPGs, etc. When the find collisions in bounding boxes then they do more fine-grained computations on the polygons that are contained therein.</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