Allegro.cc Forums » Programming Questions » A point inside a rectangle

Credits go to Felipe Maia for helping out!
 This thread is locked; no one can reply to it.
 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. ---It's Ridge Racer! RIIIIIDGE RAAAAACER!
 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).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"}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. --sig used to be here
 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. --- Bob [ -- All my signature links are 404 -- ]
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.

 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.

 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. -- Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散！悪霊退散！怨霊、物の怪、困った時は　ドーマン！セーマン！ドーマン！セーマン！　直ぐに呼びましょう陰陽師レッツゴー！
 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. --- Bob [ -- All my signature links are 404 -- ]
 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 ``` -- Since 2008-Jun-18, democracy in Sweden is dead. | 悪霊退散！悪霊退散！怨霊、物の怪、困った時は　ドーマン！セーマン！ドーマン！セーマン！　直ぐに呼びましょう陰陽師レッツゴー！
 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! ---It's Ridge Racer! RIIIIIDGE RAAAAACER!
 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]
 Go to: Allegro Development Installation, Setup & Configuration Allegro.cc Comments Off-Topic Ordeals The Depot Game Design & Concepts Programming Questions Recent Threads