Re: Spherical trig application

*To*: mathgroup at smc.vnet.net*Subject*: [mg2242] Re: Spherical trig application*From*: danl (Daniel Lichtblau)*Date*: Wed, 18 Oct 1995 01:54:38 -0400*Organization*: Wolfram Research, Inc.

(mail to <ui at uribe.demok.co.uk> bounced) 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. > I know nothing about sperical trig. You could try this. First, set up coordinates so that your region of interest lies in the first octant less the equator. From the diameter restriction, you know you can do this. You can now exclude any point with a negative coordinat. Now translate from the sphere to the plane by mapping (x,y,z) -> (x/z, y/z). Translate your region to the plane. Maybe use a pair of circles circumscribing/enscribiing your plane region to include/exclude points, and for the remaining points check a bunch of planar inequalities. The point is inside iff all chacks pass (if the region was actually convex). Daniel Lichtblau Wolfram Research