Re: Spherical Trigonometry Application

*To*: mathgroup at smc.vnet.net*Subject*: [mg2276] Re: Spherical Trigonometry Application*From*: Jorma Virtamo <jorma.virtamo at vtt.fi>*Date*: Mon, 23 Oct 1995 12:38:04 -0400

In article <DGBJLI.MM8 at wri.com> Roger Uribe <ui at uribe.demok.co.uk> writes: > > Given a roughly convex polygon on the Earth's surface - typically 1000 > miles "diameter" and 3 - 12 vertices. I need to know whether a given > point is in it or not. There are about 10,000+ such points to test so > I need an effecient method. > > Any ideas, or know of any software that will do something like it. > > I guess defining the enclosing circle and discarding any points > outside that would get rid of most of them. > > I don't want a lesson in spherical trig, I'm no expert but I know > enough, it's the methods and short cuts I'm after. > > Thanks Roger. > The following should work if the polygon is strictly convex: Assume the polygon is given by the sequence of points pts = {p1,p2,...,pn} where each point is represented in the {x,y,z} form. Further assume that the sequence is given in the counterclockwise direction (when looked from the outside of the sphere). Finally, assume that the "polygon" is defined by great circles between the consecutive points, i.e. the circle cut by the plane defined by the origin and the two consecutive points. Then the task is to check that the given point R is on the right side of each plane. For instance, for the first pair {p1,p2} this can be seen from the sign of the determinant Det[{p1,p2,R}] which should be positive. Let us first form all consecutive pairs of points pairs = Transpose[{pts,RotateLeft[pts]}] Then you can make the check for each pair by inq = Det[Append[#,R]]>0 & /@ pairs which returns a list of Trues and Falses. To check whether all of them are Trues just apply And And @@ inq Hope this works. -- Jorma Virtamo ============================================================ Jorma Virtamo VTT Information Technology / Telecommunications P.O. Box 1202, FIN-02044 VTT, Finland phone: +358 0 456 5612 fax: +358 0 455 0115 email: jorma.virtamo at vtt.fi web: http://www.vtt.fi/tte/ ============================================================