jezebel@ut-emx.UUCP (Jim @ MAC@/) (02/25/88)
Have a nice one here: Have a boundary defined on the screen. Boundary is composed of points joined by lines... Now some random points are generated and I want to check if a given point is within or outside the existing boundary.. Any algorithm for this ? Is it at all possible ???? Running with GKS....under Fortran... Mind-boggling for you ? If not, you are the guy/gal who has the solution to my problem..... Please respond..... Jim
ugfailau@sunybcs.uucp (Fai Lau) (02/25/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a nice one here: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for >this ? Is it at all possible ???? >Running with GKS....under Fortran... Yes, it is at all possible. It is not easy though, but it can be done. All you have to do is to look up some good computer graphics book. Being able to determine if a point is inside a boundary is the building block of several more complicated algorithms dealing with windowing, clipping, and so forth. Actually, in order to simulate the problem and the solutions to the problem, all that is needed are C and a decent graphics package (anything that lets you put a line or a point on the screen is all right.) Fai Lau SUNY at Buffalo (The Arctic Wonderland) UU: ..{rutgers,ames}!sunybcs!ugfailau BI: ugfailau@sunybcs INT: ugfailau@joey.cs.buffalo.EDU
vanhove@XN.LL.MIT.EDU (Patrick Van Hove) (02/25/88)
>Keywords: READ THIS ONLY IF YOUR IQ >>125 ... >Running with GKS....under Fortran... Some inconsistency there! Trick.
begeman@geza.SW.MCC.COM (Michael Begeman) (02/25/88)
In article <971@ut-emx.UUCP>, jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: > > Have a boundary defined on the screen. Boundary is composed of points > joined by lines... Now some random points are generated and I want to check > if a given point is within or outside the existing boundary.. This is a simple variation of the "convex hull" problem. The C-H problem involves finding, for a set of points, that subset which when connected by line segments encloses the remaining points (you can think of this as playing connect-the-dot around the outer edge). In the convex-hull problem, the question takes the form: Given a new point, does it change the convex hull? The result if FALSE if it lies within the existing convex hull (what you described as the boundary), TRUE if outside. I'll refer you to the following reference: Kant, Elaine and Newell, Allen. Problem Solving Techniques for the Design of Algorithms. Information Processing & Management, Vol 20, No. 1-2, pp. 97-118, 1984. This was reprinted in the second edition of an IEEE tutorial entitled Human Factors in Software Development edited by Bill Curtis. IEEE Computer Society Order Number 577. The article describes the ways different designers approached this problem, and contains several tenable solutions. P.S. Sorry, but I can't claim the IQ >> 125 prize. I'd only have earned that had I worked on the problem for weeks before discovering that it was already solved! ------- Of all the things I've lost, I miss my mind the most. +----------------------------------------------------------------+ | Michael L. Begeman, MCC, 9390 Research Blvd., Austin TX 78759 | | (512)338-3308 begeman@mcc.com | | {gatech,harvard,pyramid,seismo}!ut-sally!im4u!milano!begeman | +----------------------------------------------------------------+
pjs@granite.dec.com (Philip J. Schneider) (02/26/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a nice one here: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for >this ? Is it at all possible ???? >Running with GKS....under Fortran... >Mind-boggling for you ? If not, you are the guy/gal who has the >solution to my problem..... >Please respond..... >Jim I think I speak for many, many people who read this newsgroup when I tell you that this is an extremely trivial problem to solve, and frankly, I'm tired of seeing it asked over and over and over again here. Why don't you ask around locally, or do some searching on your own in the standard references, before you post questions to the entire world, which, by the way, costs $$. -- Philip J. Schneider | pjs@decwrl.dec.com DEC Workstation Systems Engineering | pjs@granite.dec.com 100 Hamilton Avenue | (415)853-6538 Palo Alto, CA 94306 | (415)493-3244
msprick@amdcad.AMD.COM (Rick Dorris) (02/26/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a nice one here: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for >this ? Is it at all possible ???? >Jim Well not to say that I'm intelligent, but here's a solution. You can figure if the point is within the boundary by drawing a line from the point to the edge of the screen. Count how many times this line crosses your boundary. If odd, the point is inside the boundary, if even, it is not. If I understood your problem correctly, this should work. How to actually program this--- well I told you that I wasn't that intelligent! Rick
cosell@bbn.com (Bernie Cosell) (02/26/88)
In article <210@geza.SW.MCC.COM> begeman@geza.SW.MCC.COM (Michael Begeman) writes: >In article <971@ut-emx.UUCP>, jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >> >> Have a boundary defined on the screen. Boundary is composed of points >> joined by lines... Now some random points are generated and I want to check >> if a given point is within or outside the existing boundary.. > >This is a simple variation of the "convex hull" problem. The C-H problem >involves finding, for a set of points, that subset which when connected >by line segments encloses the remaining points (you can think of this as >playing connect-the-dot around the outer edge). Sorry, no cigar I think. What if the line segments give you a non-convex shape? For convex shapes the problem is pretty easy (the only interesting part is figuring out tricks to make it be quickly-calculable). One thing that comes to mind quickly for arbitrary (!!) regions is to find a point *known* to be outside the region and then take the line segment from the point-being-tested to the known-outside-point. Now check how many region-boundary segments this line segment intersects. If the number is odd, then the point is inside the region, if even it is outside the region. (if you handle "intesection" properly, you can just pick an endpoint of one of the region-boundary lines as the known-outside point). also note that this trick (the parity of the number of intersections) works pretty much no matter WHAT the boundary of the region is (e.g., if you had the boundary built up of splines, this'd STILL work, although the did-it-intersect question would probably be harder to figure out) __ / ) Bernie Cosell /--< _ __ __ o _ BBN Labs, Cambridge, MA 02238 /___/_(<_/ (_/) )_(_(<_ cosell@bbn.com
madden@batcomputer.tn.cornell.edu (Pat Madden) (02/26/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm >for this ? Is it at all possible ???? Yes, and luckily enough, it's not too difficult to implement. You do need a reference point which you know to be either inside or outside the closed region bounded by the points/lines (a point off the screen will do nicely). Call the reference point R. Given a list E(1..n) of n edges, and the point P being tested, perform the following: 1. Count = 0 2. For each i, 1 <= i <= n, DO 3. IF segment PR intersects edge E(i) THEN increment Count. 4. END 5. IF Count is even, then P is on the same side of boundary as R ELSE P is on other side of boundary. Here's a short explanation/demonstration to justify this algorithm: Draw an arbitrary boundary on paper. Draw two points at any locations, and slowly sketch a line from one point to the other. Whenever you cross a boundary, you must be either going into or leaving from the bounded area, since you can not cross a boundary and still be on the same side. So, if your start point was outside the boundary, the first crossing would bring you inside, the next one out again, and so on, until you get to the endpoint; hence the even/odd condition in step 5 above. Note that this algorithm will work for any shaped region, not necessarily convex. I hope this helps. --Pat -- ========================================================================== Pat Madden {cmcl2, shasta, uw-beaver, rochester}!cornell!batcomputer!madden madden@batcomputer.tn.cornell.edu
flaig@cit-vlsi.Caltech.Edu (Charles M. Flaig) (02/26/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a nice one here: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for >this ? Is it at all possible ???? >Running with GKS....under Fortran... >Mind-boggling for you ? If not, you are the guy/gal who has the >solution to my problem..... >Please respond..... >Jim Maybe I've missed something (and have to get my IQ rechecked :-), but can't you just: 1) Extend a line segment from the point to infinity (or to any other point known to be outside the boundary). 2) Calculate intersections between this line segment and those making up the boundary. It does not count as an intersection if it is a parallel line (overlaps). If the intersection is at a vertex, you count it as +1/2 intersection if the line from the vertex is to the "right" of your test line, and -1/2 if it is to the "left". 3) Total the number of intersections. Odd total => inside, even => outside. Of course if your point is ON a segment, then it is ON the boundary. Seems simple enough. But I'll put on my handy helmet in case I'm wrong.... ______________________________________________________________________________ ___ , , ,;,;;;, / Y /| /| Charles Flaig ;/@-@\; | |/ __, ,__ |/ flaig@csvax.caltech.edu | ^ | | /^\ / | | | / /\ /\ \=/ \____/| \_/|_/\_/ \_/ \_\/_/_/_/ "What, you think they PAY me for this?"
beatyr@pur-ee.UUCP (Robert Beaty) (02/26/88)
In article <20533@amdcad.AMD.COM> msprick@amdcad.UUCP (Rick Dorris) writes: >In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >>Have a nice one here: >>Have a boundary defined on the screen. Boundary is composed of points >>joined by lines... Now some random points are generated and I want to check >>if a given point is within or outside the existing boundary.. Any algorithm for >>this ? Is it at all possible ???? >>Jim > >Well not to say that I'm intelligent, but here's a solution. >You can figure if the point is within the boundary by drawing >a line from the point to the edge of the screen. Count how many >times this line crosses your boundary. If odd, the point is inside >the boundary, if even, it is not. If I understood your problem >correctly, this should work. How to actually program this--- well >I told you that I wasn't that intelligent! > >Rick I have seen this type of algorithm before and the one I thought up in an afternoon is FAR surperior and vastly simpler to code up. Let's define the points that define the boundary lines segments as Si, 1 <= i <= N. Also, the unknown point is P. All of these are in rectangular coordinates. Assign some reference origin to the system and then compute the angle theta, between the horizontal axis and the line segment between P and Si. You will now have N values of theta. Add these up. If the point is inside the boundary region this sum will be very close to 360 degrees - the only reason it will be off is due to numerical inaccuracies in the trig functions. If the point, P, is outside the region the sum will be zero (or very close). Use a simple threashold of 180 degrees - >180 inside, <180 outside. >Running with GKS....under Fortran... >Mind-boggling for you ? If not, you are the guy/gal who has the >solution to my problem..... >Please respond..... >Jim In a formula: N \----| / \ -1 ( Si(y) - P(y) ) | > 180 then INSIDE \ tan ---------------- { / ( Si(x) - P(x) ) | < 180 then OUTSIDE / \ /----| i=1 where: Si = ( Si(x), Si(y) ) P = ( P(x), P(y) ) No problem ( I have used it before in a program ) I think it is a pretty neat solution - And it doesn't use much time. If you have any other questions about this method I am sure I can whip up some FORTRAN code to do it in about 5 min., so let me know. Bob ---------- ... ihnp4!pur-ee!beatyr <- usenet ... beatyr@ee.ecn.purdue.edu <- arpa-net ... beatyr@pur-ee.UUCP <- UUCP ----------
amlovell@phoenix.Princeton.EDU (Anthony M Lovell) (02/27/88)
Don't worry about these algorithms being posted. Save yourself the heartache and go pull Sedgewick's book "Algorithms" (title?) off the library shelf. It describes a method based on integer math , and not really an algorithm at all. This will be QUICK. -- amlovell@phoenix.princeton.edu
cosell@bbn.com (Bernie Cosell) (02/27/88)
In article <7626@pur-ee.UUCP> beatyr@pur-ee.UUCP (Robert Beaty) writes: >I have seen this type of algorithm before and the one I thought up >in an afternoon is FAR surperior and vastly simpler to code up. > >Let's define the points that define the boundary lines segments >as Si, 1 <= i <= N. Also, the unknown point is P. All of these are in >rectangular coordinates. Assign some reference origin to the system >and then compute the angle theta, between the horizontal axis and the >line segment between P and Si. You will now have N values of theta. >Add these up. If the point is inside the boundary region this sum >will be very close to 360 degrees - the only reason it will be off is >due to numerical inaccuracies in the trig functions. >If the point, P, is outside the region the sum will be zero (or very close). >Use a simple threashold of 180 degrees - >180 inside, <180 outside. ... >No problem ( I have used it before in a program ) I think it is a pretty >neat solution - And it doesn't use much time. "superior" is clearly in the eye of the beholder. Doing line intersections is a trivial and VERY quick affair that can be done easily in fixed point. Just _thinking_ about calling a trig function, much less calculating any significant number of them is SURELY going to eat up beau coup CPU time, AND require that you be working in floating point (another invitation for many machines to go into snail-mode). I had worked on a sort-of similar line of reasoning but abandoned it because I couldn't figure out how to make it fast enough to be practically calculable. Also -- I think you got the algorithm wrong (or else I misread it). Let the point-in-question, P, be at the original, and let the X-axis be the reference axis. Now assume that the region-in-question is a simple square, ABCD. Assume that the square is a long distance off up the Y axis. The P-A, P-B ... angles wrt to the X axis will all be very close to 90 degress, and so the sum of the angles will be close to 360. What WILL work (but is even HARDER to calculate) is to compute the angle subtended by each segment of the boundary (with the angle being negative if the angle is subtended "the other way"). *THEN* you get 360 or 0. (in your original terminology, instead of measuring Si-P-xaxis, you measure Si-P-Si+1). Still MUCH too hard to calculate, I think. __ / ) Bernie Cosell /--< _ __ __ o _ BBN Labs, Cambridge, MA 02238 /___/_(<_/ (_/) )_(_(<_ cosell@bbn.com
ksbooth@watcgl.waterloo.edu (Kelly Booth) (02/27/88)
Help! We just had this discussion a couple of months ago. The answer is computational geometry. All of the approaches were posted (multiple times) to this news group. Read the various text books on computational geometry. Read the proceedings of the various SIGACT-SIGGRAPH symposia on computational geometry. Read the SIAM journals that report on such algorithms. Read the (now 10+ year old) papers in Information Processing Letters that give simple solutions to the problems.
jejones@mcrware.UUCP (James Jones) (02/27/88)
I've seen several responses to the query that state a method based on the Jordan theorem--since the original poster didn't give details of the figure, it probably merits pointing out the hypothesis of said theorem requires that the curve in question be a simple closed curve, i.e. it can't cross itself. (If you allow crossings, then consider a figure eight. There are a whole lot of points people would normally consider to be on the "outside" from which one can draw a ray that hits the figure eight right where the top and bottom halves touch. One might be able to work around this by saying "well, that counts as two intersections--consider the number of times you cross the ray if you draw the figure eight with a pencil." It could get tricky, though, e.g. if the line segments the original poster said he was starting with end at a crossover point.) James Jones
sullivan@marge.math.binghamton.edu (fred sullivan) (02/27/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for See "Algorithms" by Robert Sedgewick, pp. 315-317. Fred Sullivan Department of Mathematical Sciences State University of New York at Binghamton Binghamton, New York 13903 Email: sullivan@marge.math.binghamton.edu
ksbooth@watcgl.waterloo.edu (Kelly Booth) (02/28/88)
In article <210@geza.SW.MCC.COM> begeman@geza.SW.MCC.COM (Michael Begeman) writes: > >P.S. Sorry, but I can't claim the IQ >> 125 prize. I'd only have > earned that had I worked on the problem for weeks before discovering > that it was already solved! On the contrary! You WIN the prize. Working on a problem for weeks before discovering that it has already been solved is far too often what happens in computer science. Most disciplines take pride in knowing the literature and making every effort to build on past successes. As Richard Hamming (I believe) once said in this context, "Newton may have stood on the shoulders of giants, but in computer science we stand on each other's toes." (Pardon the loose quote here, I don't have the original, but I think it is from his Turing Award address, which appeared in CACM and in the ACM Press book containing the first 20 Turing Award talks -- well worth reading if only to see how little has been accomplished in computer science in terms of solving basic problems posed by the award winners.)
tada@athena.mit.edu (Michael Zehr) (02/29/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: > [need algorithm to determine point-inside-polygon] In article <20533@amdcad.AMD.COM> msprick@amdcad.UUCP (Rick Dorris) writes: >Well not to say that I'm intelligent, but here's a solution. >You can figure if the point is within the boundary by drawing >a line from the point to the edge of the screen. Count how many >times this line crosses your boundary. If odd, the point is inside >the boundary, if even, it is not. If I understood your problem >correctly, this should work. How to actually program this--- well >I told you that I wasn't that intelligent! > >Rick In article <7626@pur-ee.UUCP> beatyr@pur-ee.UUCP (Robert Beaty) writes: >I have seen this type of algorithm before and the one I thought up >in an afternoon is FAR surperior and vastly simpler to code up. >[describes ...] >In a formula: > > N > \----| / > \ -1 ( Si(y) - P(y) ) | > 180 then INSIDE > \ tan ---------------- { > / ( Si(x) - P(x) ) | < 180 then OUTSIDE > / \ > /----| > i=1 "FAR superior" ? In what way? You want to do a divide and a tan-1 for each edge or the polygon? And need to sum all of them before having an answer? The method I use in some graphics programs requires a compare and an xor for each edge of the polygon, and 2 multiplies (total, not for each edge). (And it works for concave as well, but might require more multiplies in that case.) ------- michael j zehr "My opinions are my own ... as is my spelling."
posdamer@wucs2.UUCP (Jeff Posdamer) (03/01/88)
In article <608@mcrware.UUCP>, jejones@mcrware.UUCP (James Jones) writes: > I've seen several responses to the query that state a method based on > the Jordan theorem--since the original poster didn't give details of the > figure, it probably merits pointing out the hypothesis of said theorem > requires that the curve in question be a simple closed curve, i.e. it > can't cross itself. > > (If you allow crossings, then consider a figure eight. There are a > whole lot of points people would normally consider to be on the > original poster said he was starting with end at a crossover point.) > There is no reason for either positive or negative flames her, HOWEVER: There exists a list of questions, each of which is answered in every introductory graphics text and/or course and/or tutorial. It seems that very often, it is more convenient to bang out a net request than do some homework. The problem is not in taking this approach. The real problem is that those who reply are frequently incorrect in their responses. As with newspaper or TV reports that are incorrect, the damage lives on long after the netlanders or even the replier have corrected the posting. A simple request: Do NOT post items of the "it seems to me...", or "An obvious solution..." variety. Almost all of these problems have well understood, tested, valid solutions. Look in: Foley and Van Dam, Fundamentals of Interactive Computer Graphics Newman and Sproull, Principals of Interactive Computer Graphics Preparata and Shamos, Computational Geometry and the list goes on. Maybe that was a flame; if so, flame off Jeff Posdamer -- Jeff Posdamershington University, St. Louis, MO, (314) 889-6147 UUCP: posdamer@wucs1.UUCP or ...!{ihnp4,seismo}!wucs1!posdamer ARPANET: wucs1!posdamer@seismo.CSS.GOV (or .ARPA) CSNET: wucs1!posdamer%seismo.CSS.GOV@csnet-relay
saponara@batcomputer.tn.cornell.edu (John Saponara) (03/01/88)
In article <867@bingvaxu.cc.binghamton.edu> sullivan@marge.math.binghamton.edu.cc.binghamton.edu (fred sullivan) writes: >In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >>Have a boundary defined on the screen. Boundary is composed of points >>joined by lines... Now some random points are generated and I want to check >>if a given point is within or outside the existing boundary. Any algorithm for > >See "Algorithms" by Robert Sedgewick, pp. 315-317. This is an excellent place to go for good start on the problem. Go read it. Now that you've read it, forget it. The problem with Sedgewick is that, to quote Sedgewick, "The program assumes that p[1] [the second point in the polygon] is the point with the smallest x coordinate among all the points with the smallest y coordinate, so that if p[1] is on the test line, then p[0] cannot be." This is a pretty hefty assumption under some circumstances, and it puts the burden of finding p[1] on the programmer. Sedgewick's point here is that he wants to avoid having p[0] and p[1] both start on the horizontal ray which he shoots off from the test point. Something unstated by Sedgewick is that he assumes that the points are in a counter-clockwise order (if they were clockwise, p[1] and p[0] could lie on a horizontal line even with these funky conditions on p[1] - I leave this as an exercise for the dedicated knurds (like me) ;^) ). You can do away with Sedgewick's p[1] assumption and start with any vertex you want by making one simplification: make the horizontal ray emanating from the test point not a set of points but rather a simple dividing line, which divides vertices into two sets: those above the horizontal X line (i.e. those with Y >= 0) and those below (Y < 0). You've just defined the special case of points on the test line away: there are now NO points on the ray, as we've defined it. This turns out to get rid of all those nasty special cases. For a full explanation, see my course notes for the SIGGRAPH '87 "Introduction to Ray Tracing" tutorial (they'll be in this year's tutorial notes, too, whatever good that'll do you right now). A problem with both of these methods, by the way, is that points exactly on the edge of the polygon will sometimes be considered inside, sometimes outside the polygon. This can be easily solved in theory (with precision error creeping in and messing things up), and for applications like ray-tracing it's almost always irrelevant. Eric Haines (not John Saponara)
karl@sugar.UUCP (Karl Lehenbauer) (03/02/88)
In article <20533@amdcad.AMD.COM>, msprick@amdcad.AMD.COM (Rick Dorris) writes: >Keywords: READ THIS ONLY IF YOUR IQ >>125 ^^^^^^^^ Nobody can read it cuz everyones' IQs shifted right by 125 are 0 ;-) -- "Lack of skill dictates economy of style." - Joey Ramone ..!uunet!nuchat!sugar!karl, Unix BBS (713) 438-5018
William_Charles_Thibault@cup.portal.com (03/03/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for If a lot of "random points" are to be tested for inclusion in the region, you might want to build a search structure for the boundary. This requires a preprocessing step, but can save time in the long run. There are good (optimal) techniques for convex polygons, but very little work deals with concave ones. One possibility is to use a 2D BSP tree for the search structure. See the paper "Set Operations on Polyhedra Using Binary Space Partitioning Trees," W. Thibault and B. Naylor, Computer Graphics 21(4) (SIGGRAPH Proceedings), July 1987.
michael@trigraph.UUCP (Michael Winser) (03/03/88)
In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: >Have a nice one here: >Have a boundary defined on the screen. Boundary is composed of points >joined by lines... Now some random points are generated and I want to check >if a given point is within or outside the existing boundary.. Any algorithm for >this ? Is it at all possible ???? >Running with GKS....under Fortran... >Mind-boggling for you ? If not, you are the guy/gal who has the >solution to my problem..... >Please respond..... >Jim All you have to do is "draw" a line from the given point to a point known to be outside the boundary, then see how many times that line intersects with the set of lines that make up the boundary. If the number of intersections is odd then your point is inside the boundary. You must also check for the special case of the intersection occuring at one of the boundary points, such a point must only be counted once. GKS may have some nice routine defined that does this for you, but I'd be quite surprised. Michael -- ...mnetor!utzoo!trigraph!michael Michael Winser michael@trigraph.UUCP Trigraph Inc. 5 Lower Sherbourne St. #201 (416) 363-8841 Toronto,Ontario M5R 3H8
spencer@spline (Spencer W. Thomas) (03/04/88)
Another possibility (disclaimer: I haven't implemented this technique, and in fact, haven't carefully read the article) is "A New-Point Location Algorithm and its Practical Efficiency", Edahiro, Kokubo, and Asano, TOG 3, 2, pp86-109 =Spencer (spencer@crim.eecs.umich.edu)
posdamer@wucs2.UUCP (Jeff Posdamer) (03/04/88)
In article <3634@cup.portal.com>, William_Charles_Thibault@cup.portal.com writes: > In article <971@ut-emx.UUCP> jezebel@ut-emx.UUCP (Jim @ MAC@/) writes: > >Have a boundary defined on the screen. Boundary is composed of points > >joined by lines... Now some random points are generated and I want to check > >if a given point is within or outside the existing boundary.. Any algorithm for > > If a lot of "random points" are to be tested for inclusion in the region, > you might want to build a search structure for the boundary. This requires > a preprocessing step, but can save time in the long run. There are > good (optimal) techniques for convex polygons, but very little work > deals with concave ones. One possibility is to use a 2D BSP tree > for the search structure. See the paper "Set Operations on Polyhedra > Using Binary Space Partitioning Trees," W. Thibault and B. Naylor, > Computer Graphics 21(4) (SIGGRAPH Proceedings), July 1987. I hate to continue beating a dead and decaying horse BUT... Preparata and Shanos, Computational Geometry:An Introduction, Springer- Verlag, 1985 Mehlhorn, Multi-dimensional Searching and Computational Geometry, Springer_ Verlag, 1984 Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987 are three good places to start looking at problems like this. The work has been done on these algorithms!! With preprocessing, point in polygon can be done O(log n). If computer science ever amounts to anything, we better start learning our own research results Jeff Posdamer -- Jeff Posdamershington University, St. Louis, MO, (314) 889-6147 UUCP: posdamer@wucs1.UUCP or ...!{ihnp4,seismo}!wucs1!posdamer ARPANET: wucs1!posdamer@seismo.CSS.GOV (or .ARPA) CSNET: wucs1!posdamer%seismo.CSS.GOV@csnet-relay
ncperson@ndsuvax.UUCP (Brett Person) (03/09/88)
Don't most of us have to do something like this little graphing excersise at some time? I think I remember doing this in basic! I don't see what the big deal is, unless I'm missing something....
steve@slovax.UUCP (Steve Cook) (03/11/88)
Duh, since I'm not very intelligent could you explain the question
to me again....
Does the subject line of this guys posting bother anyone else???
Obviously, if he would look in a graphics text he could find the answer
to his problem.
--
Steve Cook
Hah... try to find me at {psivax,ism780}!logico!slovax!steve
or at {hplsla,uw-beaver}!tikal!slovax!steve
I dare you to, RDA will disavow all knowledge of me.gtchen@tybalt.caltech.edu (George T. Chen) (03/12/88)
Does any of the previously mentioned algorithm work with overlapping polygons? For example, consider the grid 1 2 3 4 5 6 7 8 9 Consider the polygon defined by: 1-2-6-9-7-4-2-3-5-1 Most algorithms (including the odd-even boundary method) will consider the diamond region between 2 and 5 to be outside the polygon although it's suppose to be inside. Comments?
dick@slvblc.UUCP (Dick Flanagan) (03/13/88)
In article <708@ndsuvax.UUCP> ncperson@ndsuvax.UUCP (Brett Person) writes: > Don't most of us have to do something like this little graphing excersise > at some time? I think I remember doing this in basic! I don't see what > the big deal is, unless I'm missing something.... You aren't missing anything. This sounds like an under-graduate student who thinks it would be cute if a world-wide network did his homework for him. The adolescent Subject: line also strengthens this hypothesis. Dick -- Dick Flanagan, W6OLD GEnie: FLANAGAN UUCP: ...!ucbvax!ucscc!slvblc!dick Voice: +1 408 336 3481 Internet: slvblc!dick@ucscc.UCSC.EDU LORAN: N037 04.7 W122 04.6 USPO: PO Box 155, Ben Lomond, CA 95005
dave@viper.Lynx.MN.Org (David Messer) (03/14/88)
In article <5740@cit-vax.Caltech.Edu> gtchen@tybalt.caltech.edu.UUCP (George T. Chen) writes: >Most algorithms (including the odd-even boundary method) will consider >the diamond region between 2 and 5 to be outside the polygon although >it's suppose to be inside. Who says? It is inside only if your definition says so. If you want it to be inside, make your algorithm say it is. Don't we have something better to discuss? This is a pretty trivial subject. -- If you can't convince | David Messer - (dave@Lynx.MN.Org) them, confuse them. | Lynx Data Systems -- Harry S. Truman | | amdahl --!bungia!viper!dave | hpda / Copyright 1988 David Messer -- All Rights Reserved This work may be freely copied. Any restrictions on redistribution of this work are prohibited.
johng@ecrcvax.UUCP (John Gregor) (03/14/88)
In article <5740@cit-vax.Caltech.Edu> gtchen@tybalt.caltech.edu.UUCP (George T. Chen) writes: >Does any of the previously mentioned algorithm work with overlapping >polygons? For example, consider the grid > > [ Grid deleted ] > >Most algorithms (including the odd-even boundary method) will consider >the diamond region between 2 and 5 to be outside the polygon although >it's suppose to be inside. > >Comments? The non-zero winding number rule will completely fill the polygon. Like the even-odd rule, to determine if a point is "inside" take a ray from that point to infinity. For each ray-edge intersection increment the intersection count if the edge passes from left to right, and subtract one if the edge passes from right to left. If the count is 0, then the point is "outside" the polygon. See Adobe's Red Book (Postscript Reference Manual) for a couble of sample pictures. -- pqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpqpq bdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbdbd John Gregor johng%ecrcvax.UUCP@germany.CSNET