A point inside a rectangle
Kauhiz

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

1. Write a function that checks on which side of a straight line a given point lies (left or right).
2. Call the above function 4 times, once for each edge of the rectangle (works for all convex polygons actually). If the point is on the same side for all 4 edges (assuming you turn all the edges in the same direction), then the point is inside.

This is a simple algorithm. There are others that may be more eficient, but this one is a simple as it gets...

EDIT:
Here's a picture:
{"name":"589732","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/1\/01aeae11fd4a36b265a9fb37a1c861b5.png","w":478,"h":437,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/1\/01aeae11fd4a36b265a9fb37a1c861b5"}589732
The red point is on the right side of the lines AB, BC, CD and DA (notice how all the lines are oriented in the same direction, I mean they go uniformly from A to D), but the blue point is on the left side of one of the lines DA.

Bob

That's easy: Just generalize the point-in-triangle intersection test. For all ordered edges in your rectangle, compute an edge equation.

<math>EdgeEq: Ax + By + C = 0</math>

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.

<math>A * P.x + B * P.y + C = 0</math>
<math>A * Q.x + B * Q.y + C = 0</math>

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.

<math>Ax + By + C > 0?</math>
<math>Ax + By + C < 0?</math>
<math>Ax + By + C = 0?</math>

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

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.

1 t1 = (((x2 - x3)*(y3 - y)) - ((x3 - x)*(y2 - y3)));
2 t2 = (((x1 - x3)*(y2 - y3)) - ((x2 - x3)*(y1 - y3)));
3 t3 = (((x1 - x3)*(y3 - y)) - ((x3 - x)*(y1 - y3)));
4 t4 = (((x2 - x3)*(y1 - y3)) - ((x1 - x3)*(y2 - y3)));
5 if(t2 != 0) {
6 a1 = t1/t2;
7 } else {
8 a1 = 0;
9 }
10 if(t4 != 0) {
11 a2 = t3/t4;
12 } else {
13 a2 = 0;
14 }
15 a3 = 1.0f-a1-a2;
16 
17//If (a1 < 0), or (a2 < 0), or (a3 < 0), then the point is not inside the triangle

There's the code.

[edit]
http://en.wikipedia.org/wiki/Barycentric_coordinates_(mathematics)
link

X-G

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
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

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

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

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.

Thread #586395. Printed from Allegro.cc