Points, Lines, and Polygons on Spheres with C/C++

Question

My application is to represent shapes on the Earth's (using a sphere is sufficient) surface. Those can be points, lines, and polygons. Coordinates should be defined by using degrees or radians (just like geographic coordinates).

A (straight) line for example should be defined by two coordinates and use the great circle (http://en.wikipedia.org/wiki/Great_circle) to connect them. Polygons should consist of a collection of the lines mentioned. Furthermore I would like to perform operations like intersection, union, difference, complement on the shapes mentioned. Set - Basic Operations gives an idea of the operations assuming that the circles would be polygons. Of course those operations would differ if I for example intersect two lines. These operations only need to output collections of coordinates.

What I don't need is extended functionality like Voronoi diagrams, Triangulations, and so on. Also I don't need to graphically display the results.

I tried to figure that out using CGAL. More precisely I was looking at the "3D Spherical Geometry Kernel" and "2D Boolean Operations on Nef Polygons Embedded on the Sphere". Actually I already had problems with putting a line on the sphere. Additionally CGAL works in the Euclidean Space, which still leaves me with the geometric operations necessary, to work with great circles placed on the sphere.

My question is, if you can assist me in realizing the functionality mentioned in CGAL or if you can recommend another library for C/C++ that does that. Thank you very much!

Answer 1

Just googled this: http://www.codecogs.com/d-ox/geometry/spherical/position.php

Answer 2

I'd suggest you to take a look at this:

http://www.codeguru.com/Cpp/Cpp/algorithms/general/article.php/c5115/

The question 1E solves your problem of intersection between two grand circles. From this you can define the basic operation of your shapes on the sphere without a big dependency like CGAL or GEOS.

Answer 3

Finding the intersection of two objects typically requires setting the equations defining the objects equal to each other.

Here is one way, which perhaps just another phrasing of Vitor's answer.

Start by defining each line(arc) as a parametric equation. For better or worse I see these arcs as the path normalized vectors take when rotated. So that's how i would define them (I bet there is a better way).

So I would take the start and end points, treat them as vectors, take there cross product to get the axis of rotation, and that the dot product to get the angle.

so my equation for a arc would look like

arc(t) = startPoint * (axisAngleToRotationMatrix (axis, t * angle))

You would then set the two arcs equation equal to each other and solve the system of equations that results, for the "t"'s in each equation.

Answer 4

If you want to do general polygon set operation like union/intersection etc., then you can look into General polygon clipper library from http://www.cs.man.ac.uk/~toby/alan/software/