1. RE: finding if point is inside irregular rectangle
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:
2. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 25, 2002
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:
>
>
3. RE: finding if point is inside irregular rectangle
"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:
> > > >
> > > >
4. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 25, 2002
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:
> > > > >
> > > > >
5. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 25, 2002
I've never thought of using ray casting to find edge crossings.
I'd expect that to be MUCH faster than the way I just described.
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:
> > > > >
> > > > >
6. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 25, 2002
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>
7. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 25, 2002
What happens if both l[1][2] and l[2][2] < p[2]? It's still gonna check
if p[1] is in bounds.
Chris
David Cuny wrote:
> Derek Parnell wrote:
>
> > Not sure if this works for concave polygons.
>
> It should. Odd/Even edge crossing is pretty much the classic method.
> Plus,
> it's easy to optimize. You don't have to actually cast a ray, you just
> count
> the number lines that "cover" the point that lie above the point (ie:
> the x
> of the point lies between (x1, x2) and the one of (y1,y2) lies above the
> y of
> the point. Something like:
>
> -- p = {x,y}
> -- l = { {x1,y1}, {x2,y2}}
> function crosses( sequence p, sequence l )
> if l[1][2] >= p[1] or l[2][2] >= p[2] then
> if l[1][1] < l[2][1] then
> return l[1][1] <= p[1] and l[2][1] >= p[1]
> else
> return l[2][1] <= p[1] and l[1][1] >= p[1]
> end if
> end if
> return 0
> end function
>
> Untested code, of course. 
>
> -- David Cuny
>
>
8. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 25, 2002
I've been playing with intersectring polygons code, and my solution for
the double counted vertices was to make my formula like this:
if (edge[x1] < point[x]) and (edge[x2] >= point[x]) then ...
if (edge[x2] <= point[x]) and (edge[x1] > point[x]) then ...
only vertex 2 is counted for each edge
Chris
BTW: I've tried implementing David's code using two shapes to check for
instersections, and I can get it to work when shape1 is upper/leftmost.
When shape2 is upper/leftmost, it fails. Can someone verify that code?
David? I'm pretty sure I understand the algorithm.
Chris
Derek Parnell wrote:
> You're right David. I misunderstood the algorithm. When it said
>
> >1. imagine a horizontal line through the Point
> >2. compute the x-value where any polygon side crosses the imaginary line
> >(simple geometry using the slope of the side)
> >3. if the x-coordinate of the Point is greater than an odd number of
> >x-values then the Point is inside the polygon. If it is less than the
> >lowest x-value or greater than an even number of x-values, then it is
> >outside the polygon
> >
>
> I read it as , if the number of x-values is an odd number, then if the
> x-coord is greater than any
> of them, it is inside. Etcc...
>
> Being a simple person, maybe it would have been clearer to me if it had
> of said:
>
> "If the number of x-values that are less than the x-coord is odd, it is
> inside."
>
> However, there is still the special case of x-values that are vertices.
>
> I'm not sure if they should be counted as two or one x-value.
>
> Consider these two case:
>
> A polygon with vertices at (0,0) (10,200) (20,50) and (200,100), and a
> point at (30,50).
>
> If we count vertices as two x-values then the algo above is fine.
>
> But:
>
> A polygon with vertices at (0,50) (50,100) (100,50) and (50,0), and a
> point at (50,50).
>
> If we count vertices as two x-values then the algo above fails.
>
> Any ideas?
> ---------
> Derek
>
>
> 26/02/2002 2:25:26 PM, David Cuny <dcuny at LANSET.COM> wrote:
>
> >
> >Derek Parnell wrote:
> >
> >> Not sure if this works for concave polygons.
> >
> >It should. Odd/Even edge crossing is pretty much the classic method.
> >Plus,
> >it's easy to optimize. You don't have to actually cast a ray, you just
> >count
> >the number lines that "cover" the point that lie above the point (ie:
> >the x
> >of the point lies between (x1, x2) and the one of (y1,y2) lies above the
> >y of
> >the point. Something like:
> >
> >-- p = {x,y}
> >-- l = { {x1,y1}, {x2,y2}}
> >function crosses( sequence p, sequence l )
> > if l[1][2] >= p[1] or l[2][2] >= p[2] then
> > if l[1][1] < l[2][1] then
> > return l[1][1] <= p[1] and l[2][1] >= p[1]
> > else
> > return l[2][1] <= p[1] and l[1][1] >= p[1]
> > end if
> > end if
> > return 0
> >end function
> >
> >Untested code, of course.
> >
> >-- David Cuny
> >
> >
> ---------
> Cheers,
> Derek Parnell
>
>
9. RE: finding if point is inside irregular rectangle
- Posted by bensler at mail.com
Feb 26, 2002
I thought the raytracing method was a form of the crossings count
algorithm?
Shoot a ray in a random direction from point, count the polygon edge
crossings. If crossing count is ODD, point is in polygon.
Check out this link that Al Gonzalez posted earlier. It describes quite
a few different methods, with benchmarks and C code.
http://www.acm.org/tog/resources/RTNews/html/rtnv5n3.html#art3
The 'sum of angles' method was discussed and deemed to be slower than
any of the crossings count algorithms. The argument is that the vector
math needed to get the sum of angles is much slower than any of the math
in the crossings count methods. But it IS an alternative.
I believe all the algorithms are presented if someone wants to translate
one. I'm not familiar enough with C syntax.
Chris
David Cuny wrote:
> Tone Skoda wrote:
>
> > I read somewhere that you could sum all angles between all polygon
> > vertices
> > and point. You would take two vertices from polygon and tested point and
> > make triangle from it. That sum should be 360 if point lies inside
> > polygon.
> > That should also work.
>
> Yes, this is a solution used in raytracing. I ran across it at:
>
> http://64.33.37.114/math_rot3.html
>
> Basically, you create a series of vectors by going clockwise (or
> counterclockwise) from the point P to each of the vertices (V1..V3). For
> a
> triangle, that would be:
>
> L1 = P->V1
> L2 = P->V2
> L3 = P->V3
>
> You then normalize the vectors (so they have a length 1) and take the
> dotproduct for each one:
>
> D1 = dotProduct( L1, L2 )
> D2 = dotProduct( L2, L3 )
> D3 = dotProduct( L3, L1 )
>
> You then get convert this to an angle using acos:
>
> sum = acos( D1 ) + acos( D2 ) + acos( D3 )
>
> and if they equal 360 degrees (2*PI radians) then it's inside. I have a
> feeling acos( D1 + D2 + D3) would also work, but I'm too tired to
> check.
>
> Anyway, it's all explained in the paper, with nice diagrams.
>
> -- David Cuny
>
>
