1. finding if point is inside irregular rectangle
- Posted by tone.skoda at siol.net Feb 25, 2002
- 462 views
This is a multi-part message in MIME format. ------=_NextPart_000_0064_01C1BE3A.1CBCA430 charset="iso-8859-2" 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: Please view in a fixed-width font such as Courier. |-- | ---- | --- | ---- | --- | ---- | -\ | \\ | \ | \ | \\ | \ | \ | \\ |------ \ ----------- \ ---------- \\ ----------- \ -----\ Below is function which needs to be finished. I would do it myself but I'm not too good at math. -- bounds parameter should define 4 points of rectangle and should have these members: -- 1,2: left_top_x, left_top_y, -- 3,4: left_bottom_x, left_bottom_y, -- 5,6: right_top_x, right_top_y, -- 7,8: right_bottom_x, right_bottom_y. function is_point_in_irregular_rect (sequence point, sequence bounds) -- This is returned. integer is_point_in_rect -- TODO return is_point_in_rect end function ------=_NextPart_000_0064_01C1BE3A.1CBCA430 Content-Type: text/html; charset="iso-8859-2" Content-Transfer-Encoding: 8bit <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META http-equiv=Content-Type content="text/html; charset=iso-8859-2"> <META content="MSHTML 5.50.4522.1800" name=GENERATOR> <STYLE></STYLE> </HEAD> <BODY bgColor=#ffffff> <DIV><FONT face=Arial size=2> <DIV><FONT face=Arial size=2>Here's another problem: </FONT><FONT face=Arial size=2>I need to find out if point lies inside<BR>an irregular rectangle. Irregular rectangle has<BR>4 corners but they don't need to be 90 degree, although they can still be.</FONT></DIV> <DIV><FONT face=Arial size=2><BR>Example of irregular rectangle:<BR><BR> Please view in a fixed-width font such as<BR> Courier.</FONT></DIV> <DIV> </DIV><FONT face=Arial size=2> <DIV><BR> |--<BR> | ----<BR> | ---<BR> | ----<BR> | ---<BR> | ----<BR> | -\<BR> | \\<BR> | \<BR> | \<BR> | \\<BR> | \<BR> | \<BR> | \\<BR> |------ \<BR> ----------- \<BR> ---------- \\<BR> ----------- \<BR> -----\<BR><BR></DIV> <DIV><FONT face=Arial size=2>Below is function which needs to be finished. I would do it myself but I'm not too good at math.</FONT></DIV> <DIV> </DIV> <DIV>-- bounds parameter should define 4 points of rectangle and should have these members:</DIV> <DIV>-- 1,2: left_top_x, left_top_y,<BR>-- 3,4: left_bottom_x, left_bottom_y,<BR>-- 5,6: right_top_x, right_top_y,<BR>-- 7,8: right_bottom_x, right_bottom_y.<BR>function is_point_in_irregular_rect (sequence point, sequence bounds)<BR> -- This is returned.<BR> integer is_point_in_rect<BR> -- TODO<BR> return ------=_NextPart_000_0064_01C1BE3A.1CBCA430--
2. Re: finding if point is inside irregular rectangle
- Posted by euman at bellsouth.net Feb 25, 2002
- 442 views
Hi Tone, Im not sure how this fits in but Jiri Babor wrote a DOS progam a few yrs ago that does real fast flood fills, maybe looing at how he filled shaped might help you figure out how to do this. Euman euman at bellsouth.net
3. Re: finding if point is inside irregular rectangle
- Posted by tone.skoda at siol.net Feb 25, 2002
- 450 views
Thanks. I'll look at it. Do you know the name of this program maybe? ----- Original Message ----- From: <euman at bellsouth.net> To: "EUforum" <EUforum at topica.com> Subject: Re: finding if point is inside irregular rectangle > > Hi Tone, > > Im not sure how this fits in but Jiri Babor wrote a DOS progam a few yrs ago > that does real fast flood fills, maybe looing at how he filled shaped might > help you figure out how to do this. > > Euman > euman at bellsouth.net > > > >
4. Re: finding if point is inside irregular rectangle
- Posted by tone.skoda at siol.net Feb 25, 2002
- 423 views
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> 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 tone.skoda at siol.net Feb 25, 2002
- 444 views
Yes, as long it has 4 sides and corners. I didn't know what was the expression in English, or in my language. ----- Original Message ----- From: "Brian Broker" <bkb at cnw.com> To: "EUforum" <EUforum at topica.com> Subject: 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: > > > >
6. Re: finding if point is inside irregular rectangle
- Posted by euman at bellsouth.net Feb 25, 2002
- 434 views
http://homepages.paradise.net.nz/~jbabor/eu/graphics/fill.zip Actually this ones better I think. http://homepages.paradise.net.nz/~jbabor/eu/graphics/map.zip Jiri's the man! Euman euman at bellsouth.net >
7. Re: finding if point is inside irregular rectangle
- Posted by gwalters at sc.rr.com Feb 25, 2002
- 439 views
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> 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: > > > > > > > > >
8. Re: finding if point is inside irregular rectangle
- Posted by Derek Parnell <ddparnell at bigpond.com> Feb 25, 2002
- 432 views
No Chris, he means a four-side shape - a quadrilateral. The internal angles don't have to be 90 degrees, just have to total 360 degrees. ----- Original Message ----- From: <bensler at mail.com> To: "EUforum" <EUforum at topica.com> 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: > > > > > > >
9. Re: finding if point is inside irregular rectangle
- Posted by cetaylor at compuserve.com Feb 25, 2002
- 444 views
This is one way of doing it: 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 Colin Taylor ----- Original Message ----- From: "Al Gonzalez" <alg at nomscon.com> To: "EUforum" <EUforum at topica.com> Sent: Monday, February 25, 2002 4:52 PM Subject: 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: > > > > > > > > > >
10. Re: finding if point is inside irregular rectangle
- Posted by Derek Parnell <ddparnell at bigpond.com> Feb 25, 2002
- 429 views
Not sure if this works for concave polygons. 26/02/2002 10:37:49 PM, cetaylor at compuserve.com wrote: > >This is one way of doing it: > >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 > >Colin Taylor > >----- Original Message ----- >From: "Al Gonzalez" <alg at nomscon.com> >To: "EUforum" <EUforum at topica.com> >Sent: Monday, February 25, 2002 4:52 PM >Subject: 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: >> > > > > >> > > > > > > > --------- Cheers, Derek Parnell
11. Re: finding if point is inside irregular rectangle
- Posted by rforno at tutopia.com Feb 25, 2002
- 443 views
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 > > > > > > 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: > > > > > > > > > > > > > > >
12. Re: finding if point is inside irregular rectangle
- Posted by Dan Moyer <DANIELMOYER at prodigy.net> Feb 25, 2002
- 434 views
Tone, What is the type & range of values for the points to test and of the corners of your quadrilateral? Are they non-integer, like when you were interested in finding if points were inside a normal rectangle? I ask because for integers within a certain range of values (video screen settings), there is a very easy way to tell if a candidate point is within a polygon of any shape at all. You just draw the polygon on a non-displayed screen, filled with some color other than background, and then test if the point in question is that color. It's probably not fast, but it's easy. Dan Moyer ----- Original Message ----- From: <tone.skoda at siol.net> To: "EUforum" <EUforum at topica.com> Sent: Monday, February 25, 2002 11:22 AM Subject: finding if point is inside irregular rectangle 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: Please view in a fixed-width font such as Courier. |-- | ---- | --- | ---- | --- | ---- | -\ | \\ | \ | \ | \\ | \ | \ | \\ |------ \ ----------- \ ---------- \\ ----------- \ -----\ Below is function which needs to be finished. I would do it myself but I'm not too good at math. -- bounds parameter should define 4 points of rectangle and should have these members: -- 1,2: left_top_x, left_top_y, -- 3,4: left_bottom_x, left_bottom_y, -- 5,6: right_top_x, right_top_y, -- 7,8: right_bottom_x, right_bottom_y. function is_point_in_irregular_rect (sequence point, sequence bounds) -- This is returned. integer is_point_in_rect -- TODO return is_point_in_rect end function
13. Re: finding if point is inside irregular rectangle
- Posted by David Cuny <dcuny at LANSET.COM> Feb 25, 2002
- 425 views
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
14. Re: finding if point is inside irregular rectangle
- Posted by tone.skoda at siol.net Feb 25, 2002
- 418 views
With help of your link I found this C code by searching for "inpoly.c" on google: http://www.math.iastate.edu/burkardt/c_src/orourke/inpoly.c I translated it to Euphoria and it didn't work. I must have done something wrong. Then I tested it in C++ by slightly modifying it to work with vector arrays and it works. Some C code is also here, I didn't test it: http://www.ce.berkeley.edu/~doolin/code/jsystem/jointsystem.c.html 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. ----- Original Message ----- From: "Al Gonzalez" <alg at nomscon.com> To: "EUforum" <EUforum at topica.com> Sent: Monday, February 25, 2002 10:52 PM Subject: 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: > > > > > > > > > > > > >
15. Re: finding if point is inside irregular rectangle
- Posted by Derek Parnell <ddparnell at bigpond.com> Feb 25, 2002
- 424 views
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
16. Re: finding if point is inside irregular rectangle
- Posted by tone.skoda at siol.net Feb 25, 2002
- 420 views
They are decimal numbers, and quite big. If they would be small integers your method would work and would be easy to write, good idea. ----- Original Message ----- From: "Dan Moyer" <DANIELMOYER at prodigy.net> To: "EUforum" <EUforum at topica.com> Subject: Re: finding if point is inside irregular rectangle > > Tone, > > What is the type & range of values for the points to test and of the corners > of your quadrilateral? Are they non-integer, like when you were interested > in finding if points were inside a normal rectangle? > > I ask because for integers within a certain range of values (video screen > settings), there is a very easy way to tell if a candidate point is within a > polygon of any shape at all. You just draw the polygon on a non-displayed > screen, filled with some color other than background, and then test if the > point in question is that color. It's probably not fast, but it's easy. > > Dan Moyer > > ----- Original Message ----- > From: <tone.skoda at siol.net> > To: "EUforum" <EUforum at topica.com> > Sent: Monday, February 25, 2002 11:22 AM > Subject: finding if point is inside irregular rectangle > > > 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: > > Please view in a fixed-width font such as > Courier. > > > |-- > | ---- > | --- > | ---- > | --- > | ---- > | -\ > | \\ > | \ > | \ > | \\ > | \ > | \ > | \\ > |------ \ > ----------- \ > ---------- \\ > ----------- \ > -----\ > > > Below is function which needs to be finished. I would do it myself but I'm > not too good at math. > > -- bounds parameter should define 4 points of rectangle and should have > these members: > -- 1,2: left_top_x, left_top_y, > -- 3,4: left_bottom_x, left_bottom_y, > -- 5,6: right_top_x, right_top_y, > -- 7,8: right_bottom_x, right_bottom_y. > function is_point_in_irregular_rect (sequence point, sequence bounds) > -- This is returned. > integer is_point_in_rect > -- TODO > return is_point_in_rect > end function > > > >
17. Re: finding if point is inside irregular rectangle
- Posted by David Cuny <dcuny at LANSET.COM> Feb 26, 2002
- 429 views
I should have noted an important caveat: I'm assuming that both the point and the polygon have been converted to screen space (typically translated in the z direction and then divided by z). Also, make sure you're not assuming that in a line {{x1,y1},{x2,y2}} that x1 < x2 - you have to test it! -- David Cuny
18. Re: finding if point is inside irregular rectangle
- Posted by David Cuny <dcuny at LANSET.COM> Feb 26, 2002
- 440 views
Chris wrote: > What happens if both l[1][2] and l[2][2] < p[2]? It's still gonna check > if p[1] is in bounds. If both the l[1][y] and l[2][y] are both < p[y], then the line lies underneath the point. But I see the bug in my code. If you have l1 above and to the left of the point, and l2 below and to the right, my code assumes that the point crosses the line. that's not the case - you can only assume that if both y values are above the point. otherwise, you *do* have to figure out the point of intersection, and see if the point lies below. something like: function crosses( sequence p, sequence l ) atom x, y, x1, y1, x2, y2, t x = p[1] y = p[2] x1 = l[1][1] y1 = l[1][2] x2 = l[2][1] y2 = l[2][2] -- is the point above the line? if y > y1 and y > y2 then -- the point is above, so it doesn't cross return 0 end if -- is the point below the line? if y < y1 and y < y2 then -- point crosses line return 1 end if -- does the line run left to right? if x2 < x1 then -- swap points t = x2 x2 = x1 x1 = t t = y2 y2 = y1 y1 = t end if -- point to left of line? if x < x1 then return 0 end if -- point to right of line? if x > x2 then return 0 end if -- now we have to do math... end function It's too late at night for my brain to think this hard... At the 'we do math' part, you plug in the line equation: y = mx + b and determine the (x',y') value where x' = x. if y < y', that means that the point crosses. Otherwise, it doesn't. I *think* that should cover it. Sorry about that! -- David Cuny
19. Re: finding if point is inside irregular rectangle
- Posted by David Cuny <dcuny at LANSET.COM> Feb 26, 2002
- 466 views
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
20. Re: finding if point is inside irregular rectangle
- Posted by Jiri Babor <jbabor at PARADISE.NET.NZ> Feb 27, 2002
- 439 views
A lot of wise words has been wasted on the subject. But talk is cheap, and I have not seen any usable code so far. The function below is, roughly, what I proposed four or five years ago, when the subject cropped up for the first time in this forum. It's only my vague recollection, just to get the ball rolling again - sorry I have not kept the original copy. jiri function inpoly(sequence poly, integer x, integer y) -- return 1 (true) if point x,y is inside polygon sequence s integer m,n,xi,x1,x2,y1,y2 s = {} m = length(poly) n = 0 x2 = poly[m][1] y2 = poly[m][2] for i = 1 to m do x1 = x2 y1 = y2 if x = x1 and y = y1 then -- vertices are tricky... return 1 end if x2 = poly[i][1] y2 = poly[i][2] if y1 = y2 and y = y1 then -- horizontal side if y = y1 then return (x1<=x and x2>=x) or (x2<=x and x1>=x) end if elsif (y1 < y and y2 > y) or (y2 < y and y1 > y) then xi = x1 + floor((x2-x1)*(y-y1)/(y2-y1)) s &= xi end if end for for i = 1 to length(s) do if s[i] < x then n += 1 end if end for return and_bits(n, 1) -- odd end function
21. Re: finding if point is inside irregular rectangle
- Posted by tone.skoda at siol.net Feb 27, 2002
- 425 views
Here is program to test it, it works. -- begin code include graphics.e include get.e function inpoly(sequence poly, integer x, integer y) -- return 1 (true) if point x,y is inside polygon sequence s integer m,n,xi,x1,x2,y1,y2 s = {} m = length(poly) n = 0 x2 = poly[m][1] y2 = poly[m][2] for i = 1 to m do x1 = x2 y1 = y2 if x = x1 and y = y1 then -- vertices are tricky... return 1 end if x2 = poly[i][1] y2 = poly[i][2] if y1 = y2 and y = y1 then -- horizontal side if y = y1 then return (x1<=x and x2>=x) or (x2<=x and x1>=x) end if elsif (y1 < y and y2 > y) or (y2 < y and y1 > y) then xi = x1 + floor((x2-x1)*(y-y1)/(y2-y1)) s &= xi end if end for for i = 1 to length(s) do if s[i] < x then n += 1 end if end for return and_bits(n, 1) -- odd end function ---- test ---- if graphics_mode(261) then end if function get_rand_polygon () atom a, b, c, d, e, f, g, h a = rand (100) b = 100 + rand (100) c = a + rand (100) d = 100 + rand (100) e = 200 + rand (100) f = 100 + 200 + rand (100) g = rand (100) h = 100 + 200 + rand (100) return {{a, b}, {c, d}, {e, f}, {g, h}} end function sequence rand_point sequence rand_polygon integer is_inside while 1 do rand_point = {rand (300), 100 + rand (300)} rand_polygon = get_rand_polygon () ellipse (MAGENTA, 1, {rand_point [1] - 2, rand_point [2] - 2}, {rand_point [1] + 2, rand_point [2] + 2}) is_inside = inpoly (rand_polygon, rand_point [1], rand_point [2]) if is_inside then polygon (GREEN, 0, rand_polygon) text_color (GREEN) puts (1, "point is inside polygon\n") text_color (WHITE) else polygon (RED, 0, rand_polygon) text_color (RED) puts (1, "point is not inside polygon\n") text_color (WHITE) end if puts(1, "\nPress spacebar for next or any other key to exit.\n") if wait_key() = 32 then clear_screen() else exit end if end while -- end code ----- Original Message ----- From: "Jiri Babor" <jbabor at PARADISE.NET.NZ> To: "EUforum" <EUforum at topica.com> Sent: Wednesday, February 27, 2002 10:56 AM Subject: Re: finding if point is inside irregular rectangle > > A lot of wise words has been wasted on the subject. But talk is cheap, and I > have not seen any usable code so far. The function below is, roughly, what I > proposed four or five years ago, when the subject cropped up for the first > time in this forum. It's only my vague recollection, just to get the ball > rolling again - sorry I have not kept the original copy. > > jiri > > function inpoly(sequence poly, integer x, integer y) > -- return 1 (true) if point x,y is inside polygon > > sequence s > integer m,n,xi,x1,x2,y1,y2 > > s = {} > m = length(poly) > n = 0 > x2 = poly[m][1] > y2 = poly[m][2] > for i = 1 to m do > x1 = x2 > y1 = y2 > if x = x1 and y = y1 then -- vertices are tricky... > return 1 > end if > x2 = poly[i][1] > y2 = poly[i][2] > if y1 = y2 and y = y1 then -- horizontal side > if y = y1 then > return (x1<=x and x2>=x) or (x2<=x and x1>=x) > end if > elsif (y1 < y and y2 > y) or (y2 < y and y1 > y) then > xi = x1 + floor((x2-x1)*(y-y1)/(y2-y1)) > s &= xi > end if > end for > for i = 1 to length(s) do > if s[i] < x then > n += 1 > end if > end for > return and_bits(n, 1) -- odd > end function > > > >
22. Re: finding if point is inside irregular rectangle
- Posted by euman at bellsouth.net Feb 27, 2002
- 447 views
Thats a cool demo Tone.. Euman euman at bellsouth.net
23. Re: finding if point is inside irregular rectangle
- Posted by Jiri Babor <jbabor at PARADISE.NET.NZ> Feb 28, 2002
- 441 views
Tone, looking at my five year old code, unearthed by Thomas, I realized the function can be simplified and, hopefully, made a bit faster as well. jiri function inpoly(sequence poly, integer x, integer y) -- return 1 (true) if point x,y is inside polygon integer m,n,x1,x2,y1,y2 m = length(poly) n = 0 x2 = poly[m][1] y2 = poly[m][2] for i = 1 to m do x1 = x2 y1 = y2 if x = x1 and y = y1 then -- vertices are tricky... return 1 end if x2 = poly[i][1] y2 = poly[i][2] if y1 = y2 and y = y1 then -- horizontal side if y = y1 then return (x1<=x and x2>=x) or (x2<=x and x1>=x) end if elsif (y1 < y and y2 > y) or (y2 < y and y1 > y) then if x > x1 + (x2-x1)*(y-y1)/(y2-y1) then n += 1 end if end if end for return and_bits(n, 1) -- odd end function