Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 5 of 5
  1. #1
    Regular Coder
    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.

  • #2
    Rockstar Coder
    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

  • #3
    Regular Coder Aradon's Avatar
    Join Date
    Jun 2005
    Location
    USA
    Posts
    734
    Thanks
    0
    Thanked 20 Times in 19 Posts
    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:

    Code:
    |-------|
    |   .   |
    |-------|
    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.

    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 (06-12-2008)

  • #4
    Master Coder
    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 (06-12-2008)

  • #5
    Regular Coder
    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 re-read later, for now though, I only need a box shape. I managed to get it working somewhat well. Thank you.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •