OpenEuphoria

RE: finding if point is inside irregular rectangle

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

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
> > > > > oxymoron.  A rectangle is a four-sided polygon having all right
> > angles.
> > > > >
> > > > > Perhaps you mean "irregular quadrilateral"...
> > > > >
> > > > > -- BB
> > > > >
> > > > >
> > > > > tone.skoda at siol.net wrote:
> > > > > > Here's another problem: I need to find out if point lies inside
> > > > > > an irregular rectangle. Irregular rectangle has
> > > > > > 4 corners but they don't need to be 90 degree, although they can
> > still
> > > > > > be.
> > > > > >
> > > > > > Example of irregular rectangle:
> > > > >
> > > > >