|
A point inside a rectangle |
Kauhiz
Member #4,798
July 2004
|
Ok, my problem is fairly simple: I need to determine if a point is inside a specific rectangle. The problem is, that the rectangle might not (and, infact, will not) be aligned along the x and y axes, but it will look sort of like a diamond-shape. So I can't just check if the point is between the x and y coordinates, I need something else. I've already come up with some possible solutions, but I thought I might as well ask you guys, and get the best (most effective) solution. --- |
miran
Member #2,407
June 2002
|
1. Write a function that checks on which side of a straight line a given point lies (left or right). This is a simple algorithm. There are others that may be more eficient, but this one is a simple as it gets... EDIT: -- |
Bob
Free Market Evangelist
September 2000
|
That's easy: Just generalize the point-in-triangle intersection test. For all ordered edges in your rectangle, compute an edge equation. You can compute the edge equation if you know two points on the edge. Let's say that P and Q form one of the rectangle's edges. Then, you can plug the coordinates of P and Q into the equation and get the factors A, B and C for that edge. After all, it's just a linear system of equations. Once you've obtained A, B and C for each of your edges, you can now determine if some point is on the edge, on one side of the edge or on the other. Then evaluate the sign of all the equations by plugging in your point's coordinates. If all the signs are the same, then your point is in the rectangle. Otherwise, it's outside. If you get a value of 0 anywhere, then it's on one of the edges. You can decide how you want to interpret that. Typically, you'd pick half the non-colinear edges and make them inclusive, then let the other edges be exclusive. That said, this algorithm will only work for convex polygons. If your "rectangle" happens to be concave, you'll need a much more complicated algorithm to determine inclusion. -- |
Felipe Maia
Member #6,190
September 2005
|
The best way to do this is by barycentric coordinates. It can be done in 3d aswell. Divide the rectangle in 2 triangles and do this for each of them.
There's the code. [edit] |
X-G
Member #856
December 2000
|
Or you can just use the classic thing where you extend a line infinitely in one direction from your point (it doesn't matter what direction) and count the number of times that line intersects your polygon. If that number of times is odd, the point is inside your polygon. Works for convex as well as concave polygons, of arbitrary layout. -- |
Bob
Free Market Evangelist
September 2000
|
Quote: Or you can just use the classic thing where you extend a line infinitely in one direction from your point (it doesn't matter what direction) and count the number of times that line intersects your polygon. If that number of times is odd, the point is inside your polygon. Works for convex as well as concave polygons, of arbitrary layout. There are some precision issues with this approach. But if all your numbers have sane range values, then that works too. You'll still need to compute the edge equations for line-line intersection testing, though. -- |
X-G
Member #856
December 2000
|
Sounds like you could make it a little simpler by extending your line horizontally and just doing linear interpolation... Untested pseudofluff: for each edge as E do f = (P.y - E.y1) / (E.y2 - E.y1) if (f >= 0 and f <= 1) if (E.x1 + (E.x2 - E.x1) * f) < P.x then countEdges++ end end end if odd(countEdges) then return true
-- |
Kauhiz
Member #4,798
July 2004
|
Right, some very different methods there. What I had in mind was pretty much what miran posted. I'm doing what Felipe suggested, since it works and is easy to implement. Thanks guys! --- |
Thomas Harte
Member #33
April 2000
|
I appreciate that I am late to the party and really just suggesting another way of reaching the same code as miran (albeit with a tiny optimisation), but why not project the point onto the axes of the rectangle then do an ordinary 2d style test? It's really the same as taking miran's approach and adding the oberservation that opposite sides have the same normal but inverted. [My site] [Tetrominoes] |
|