0
$\begingroup$

Does anyone have a general algorithm for determining the orientation (CW/CCW) of a spherical polygon? Polygon orientation is an easy problem in cartesian space, but much tricker on the sphere. I'm looking for an algorithm that handles ALL cases, including the polygon enclosing a pole, and also straddling the antimeridian.

For example, here's a simple small square polygon that crosses the antimeridian, which will produce the wrong answer if you run it through the cartesian algorithm (coordinates are latitude, longitude):

10, 171 11, -169 -8, -169 -9, 168

The antimeridian discontinuity is a never-ending bugbear.

BTW, no, you can't just naively add 360 to all negative longitudes. That works in this case, but fails for an equivalent polygon straddling the meridian, such as:

12, 11 -9, 11 -8, -12 13, -11

Thank you!

--ian

Improve this question
$\endgroup$
2
  • $\begingroup$ Is it unambiguous what "10, 171 11, -169" means? Are there not two interpretations, depending on which arc of the great circle through these two points is intended? $\endgroup$
    – Joseph O'Rourke
    Commented Jan 9, 2015 at 20:58
  • $\begingroup$ On a sphere, a polygon can be continuously transformed into its reverse without self-intersections. Thus, there is no definition of polygon orientation that is continuous and antisymmetric. $\endgroup$
    – Geoffrey Irving
    Commented Jan 10, 2015 at 16:28

1 Answer 1

Reset to default
3
$\begingroup$

the problem is easily solved by calculating the crossproduct ot tangents of the ingoing and of the outgoing arc; if that vector points away from the sphere's center, then the spherical polygon is oriented counter clockwise (when looking from the outside towards the sphere's center).

Another, even simpler solution of the problem is the following:
under the assumption that the sphere is centered at the origin, all points on the sphere have equal distance from the origin and can also be interpreted as vectors of equal norm.
Lets further assume we are given three linearly independent vectors $$u,v,w\in\mathbb{R}^3\wedge \|u\|_2=\|v\|_2=\|w\|_2$$ of equal length, then the sequence $(u,v,w)$ is left turn on the sphere (and thus indicates counter clockwise traversal) iff $$((v-u)\times(w-v))^Tv\gt0$$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .