MathGroup Archive 1995

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Spherical Trigonometry Application

In article <DGBJLI.MM8 at> Roger Uribe <ui at> 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     web:

  • Prev by Date: Restrictions
  • Next by Date: Re: Re: Bug in interpretation of mma Series[] command?
  • Previous by thread: Spherical Trigonometry Application
  • Next by thread: Puzzle