Enjoy an ad free experience by logging in. Not a member yet? Register.

Results 1 to 5 of 5

06092008, 02:36 AM #1
 Join Date
 Mar 2007
 Posts
 357
 Thanks
 46
 Thanked 22 Times in 21 Posts
Find out if something is inside a given area.
What would be the best way to find out if a certain point, literally just 1 pixel really, is inside a certain space. Like, I'm sure checking if it's equal to a array of possible locations is bad. The best way I thought was to find out if the 'object' position is greater than the left/top side of the area, and less than the right/bottom. Obviously though that won't work for shaped areas. Is there a better way? To be honest, I'm happy with a square area but I want to know what is the best way. No particular programming language but if you're giving your example then something along the same structure as C would be nice.
Thanks upfront.
06092008, 05:29 AM
#2
 Join Date
 Jun 2002
 Location
 USA
 Posts
 9,074
 Thanks
 1
 Thanked 328 Times in 324 Posts
With something that is a circle or a rectangle or some easy shape like that, checking the edges is the best way.
For some unknown blob of a shape, one way you could do it is store the minimum and maximum coordinates for each edge. Then you could check to see if the point was any where in those ranges, and if it was inside all the minimums then you'd be done and know it was inside the shape. However if it was in between the min and max on one side, you'd only need to iterate through that side.
That is just something I thought of off the top of my head, there are probably more formal/better algorithms.
OracleGuy
06092008, 11:44 PM
#3
There are some really interesting algorithms for this out there since this is a common problem in game programming.
One of the more interesting solutions was to create a vector that spanned from the point towards the object or some arbitrary distance.
If the Vector runs into the edge an odd amount of times, then the pixel is inside the object, else it is outside. Proof of concept:
If you go any way from that point, you will hit odd edges.Code:  .  
If you go any way from the object you will hit even edges in intersection.Code: .   
In any case, that was the general idea of the theory. The actual intersection tests and the like were also in the paper, but I can't seem to find it right now. Sorry
"To iterate is human, to recurse divine." L. Peter Deutsch
Users who have thanked Aradon for this post:
flynch01 (06122008)
06102008, 03:04 AM
#4
 Join Date
 Dec 2007
 Posts
 6,682
 Thanks
 436
 Thanked 890 Times in 879 Posts
the border of any surface can be described as a implicit function or set of functions and can be arranged to be positive if a point is inside.
rectangle:
x0  x ; left border
x  x1 ; right border
y0  y ; top border
y  y0 ; bottom border
(x0  x) > 0 && (x  x1) > 0 && (y  y1) > 0 && (y  y0) > 0
=> x, y is inside
polygons:
same as rectangle for each edge.
circle:
f(x,y) = r^2  (x  x0)^2  (y  y0)^2
f(x,y) > 0 => x, y is inside
for other shapes you can use a spline function to aproximate the border.
regards
Users who have thanked oesxyl for this post:
flynch01 (06122008)
06122008, 02:41 PM
#5
 Join Date
 Mar 2007
 Posts
 357
 Thanks
 46
 Thanked 22 Times in 21 Posts
I kindof got confused by those last two posts so I will have to reread later, for now though, I only need a box shape. I managed to get it working somewhat well. Thank you.