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/
============================================================