OpenEuphoria

RE: finding if point is inside irregular rectangle

• Posted by bensler at mail.com Feb 25, 2002
• 418 views

This is the concept of raycasting. And yes it does work for concave 
polygons. Even a polygon with a hole in the middle.

To find out if point intersects with shape:
    Choose a direction to shoot the ray from the point. Horizontal is 
best, either left or right, not both.
    Step along the ray for every x value, if x intersects with any edge 
of shape, add 1 to crossing_count
    When you reach the boundary (assuming pixel coordinates, that would 
be the edge of the screen), if crossing_count is odd, then point is 
within shape.


I have another idea that is even simpler, but I need to test it first.
I don't think you even need to cast a ray.

Just determine the y value of point.
Then for every edge of shape, determine if y is between edge_start[y], 
and edge_end[y]. Increment crossing_count if it is.
When finished, if crossing count is EVEN, the point is within shape.

This seems too easy of a solution to work. But I can't see any reason it 
shouldn't. I'll try and let you know.

Chris

rforno at tutopia.com wrote:
> Well, if we mean exactly "find if a *point* is inside an irregular 
> shape", I
> think the following method should work:
> Imagine a line starting at the point and going to infinity at only one 
> side.
> This can any line; to simplify things, it can be a horizontal line.
> Assuming the irregular polygon (even a concave one) is defined by a 
> sequence
> of point pairs, determine the intersection of the line with every side 
> of
> the polygon: this involves only solving some simple equations. Then,
> determine if the intersection is between the defining points of the
> polygon's side, and on the correct side of the horizontal line (this
> involves some simple tests), so that it is real. If the number of real
> intersections is even, the point is outside the polygon; otherwise, it 
> is
> inside.
> Please correct me if my reasoning has any flaw, or if you feel this is
> difficult to program.
> ----- Original Message -----
> From: <bensler at mail.com>
> To: "EUforum" <EUforum at topica.com>
> Sent: Monday, February 25, 2002 7:30 PM
> Subject: RE: finding if point is inside irregular rectangle
> 
> 
> > It's hard to wrap the brain around, but it really isn't that difficult.
> >
> > Here's a bit of theory..
> >
> > I haven't done it in a while, but I had to do edge finding in order to
> > do hidden surface removal in a 3D engine project I was working on a long
> > while ago.
> >
> > This only works for convex polygons, not concave polygons (THAT is NOT
> > trivial at ALL). An 'O' or is a convex shape, a 'C' is a concave shape,
> > although, they aren't polygons..
> >
> > Like I said, it's been a while, so I don't doubt I'm a bit off on some
> > of this theory, but it should be fairly close.
> >
> > 1. Get the bounds of shape A and B. (making them rectangles)
> > 2. Determine if shape B COULD be partly inside shape A using the
> > bounding edges.
> > 3. Find out if 2 or more points of shape A cross 2 or more points of
> > shape B, if so, shape B overlaps shape A.
> > 4. Determine which of the TRUE points of shape B might fall inside the
> > TRUE shape A. And vice versa
> > 5. Get the edge points for the edge of shape A that divides the
> > determined points of shape A and shape B (see #4).
> > 6. For each edge point, figure out if the 'B' point is on the 'A' side
> > of the dividing edge.
> >
> > Wphew! I still have a hard time understanding that stuff.
> >
> > I'll see if I can make up an example.
> >
> > Chris
> >
> > Al Gonzalez wrote:
> > > "far from trivial" maybe an understatement unless you are up on all of
> > > your geometry.
> > >
> > > Have a look here:
> > > http://www.acm.org/tog/resources/RTNews/html/rtnv5n3.html#art3
> > >
> > > There is some discussion and sample code in C
> > >
> > > gwalters at sc.rr.com wrote:
> > > > then it's a polygon...and it's far from trivial to find if a point is
> > > > inside.
> > > >
> > > > george
> > > > ----- Original Message -----
> > > > From: <tone.skoda at siol.net>
> > > > To: "EUforum" <EUforum at topica.com>
> > > > Sent: Monday, February 25, 2002 4:05 PM
> > > > Subject: Re: finding if point is inside irregular rectangle
> > > >
> > > >
> > > > > No I don't mean that. It can have angles which are not 90 degree.
> > > > >
> > > > > ----- Original Message -----
> > > > > From: <bensler at mail.com>
> > > > > To: "EUforum" <EUforum at topica.com>
> > > > > Sent: Monday, February 25, 2002 9:57 PM
> > > > > Subject: RE: finding if point is inside irregular rectangle
> > > > >
> > > > >
> > > > > > He means a rectangle that is not exactly horizontal and vertical.
> It's
> > > > > > still a rectangle, but on an angle, like a diamond with 90 degree
> > > > > > corners.
> > > > > >
> > > > > > Chris
> > > > > >
> > > > > > Brian Broker wrote:
> > > > > > > Hate to be a stickler here but "irregular rectangle" sounds like
> an
<snip>