flynch01

06-09-2008, 02:36 AM

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.

oracleguy

06-09-2008, 05:29 AM

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.

Aradon

06-09-2008, 11:44 PM

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.

|-------|

. | |

|-------|

If you go any way from the object you will hit even edges in intersection.

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

oesxyl

06-10-2008, 03:04 AM

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

flynch01

06-12-2008, 02:41 PM

I kindof got confused by those last two posts so I will have to re-read later, for now though, I only need a box shape. I managed to get it working somewhat well. Thank you.