[MATHCAD] Polygons (again)

Re: [MATHCAD] Polygons (again)
Author: Jim Irving    Posted: Thu, 30 Sep 1999 00:32:17 +0100
Dear Chris, See my reply to an earlier question (copied herewith). It may be helpful to you. Regards, Jim Irving Dear Ronny, This may be a bit late but I'm slowed down with a ruptured Achilles tendon, in plaster and on crutches. Your question reminded me of a similar problem I had when working on earthquake hazards in the 1980's which was to determine computationally in which regions of the British Isles the epicentres were located from a list of position co-ordinates. I solved it using the property that if a vector drawn from the epicentre to the boundary is rotated through all the points defining the boundary, returning to the first point, the total angle swept out will be 360 degrees. However, if the epicentre is outside the closed boundary the swept angle will be zero. The simplest solution was to use the properties of vectors to determine the swept angles and hence the status "inbound" or "outbound". I think this is an exact analogy to your question and I have spent a little time producing a Mathcad 7 Pro worksheet with the derivation of the formulae and a practical illustration of the method. I have also made a V 6 copy. Both these files are in the attached Zip file Bounds.zip. I hope you find them useful - thanks for an interesting few days "a la recherche du temps perdus". Regards, Jim Irving ----- Original Message ----- From: Chris Whitford /> To: /> Sent: Wednesday, September 29, 1999 3:44 PM Subject: [MATHCAD] Polygons (again) > Earlier in the year there was some correspondence about finding if a point > is inside a polygon. I have recently had to code this into an application, > so I have had to take another look at it. > > The basic principle is that if a line is drawn from the point, in any > arbitrary direction, and the number of times the line crosses the boundary > of the polygon is counted, then if the point is inside the count is odd, > otherwise it is even (this was posted by Mike Yuratich). The problem arises > when the line goes through a vertex, or the point is on an edge or vertex. > Because of the finite machine precision, one has to be very careful that > such a situation is counted correctly. The following algorithm does this, I > think. > > First translate the coordinates to put the point at the origin, and take > the trial line to be on the +X axis, extending to infinity. Consider if the > line crosses the polygon edge from vertex 1 (x1,y1) to vertex 2 (x2,y2). > > if ((y1 > 0 and y2 <= 0) or (y1 <= 0 and y2 > 0)) > and (sign(y1 - y2) = sign(x2.y1 - x1.y2)) > then count this as a crossing > > The effect of this algorithm is: > a) if a vertex is at x>0, y=0, the edge will be counted if it is above the > X axis but not if it is below. > b) if the point is on the edge it will not be counted. > c) if a vertex is at x=0, y=0 neither edge ending at this vertex will be > counted. > > This gives a consistent counting of crossings which ensures the correct > result. It also ensures that if a surface is covered with a collection of > polygons with common edges, a point on an edge or vertex will be located > unambiguously in one and only one polygon. > > Chris Whitford > > +----------------------------------------------------------------------+ > + Chris Whitford University of Leicester + > + Tel: (44) 116 252 3496 Space Research Centre + > + Fax: (44) 116 252 2464 Physics and Astronomy Department + > + University Road + > + http://www.star.le.ac.uk/ LEICESTER LE1 7RH + > + UK + > +----------------------------------------------------------------------+ > > ------------------------------------------------------------- > The Mathcad List - Discussion, Support & News > Contributions: /> > To unsubscribe: Send in the body: unsubscribe mathcad > To: /> > Hosted by: Adept Scientific http://www.adeptscience.com > List Archive: http://lists.adeptscience.co.uk/ >
Attachments:  BoundsX.mcd

Previous by date: Re[2]: [MATHCAD] The Mathcad List and Adept, JasonCuadra
Next by date: Re: [MATHCAD] business, Ian Downie
Previous thread: RE: [MATHCAD] business, Shiner Adrian
Next thread: Re: [MATHCAD] business, Ian Downie