Points, Lines, and Polygons on Spheres with C/C++ [closed]

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 line segment between two points on the surface of sphere should lie on its great circle. Polygons should consist of a collection of the such lines. Furthermore, I would like to perform Set - Basic Operations like intersection, union, difference, complement on the shapes mentioned. These operations only need to output collections of points.

I tried to figure that out using CGAL's 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!

Placeeda

The "2D Boolean Operations on Nef Polygons Embedded on the Sphere" looks like it does what you need. Is there something specific you need help with? – Nobody

@Nobody I am not clear with your question. In first para you require drawing shapes on surface of the sphere, but in 2nd para you want lines/polygons to be drawn on great circle(which will actually draw line/polygon inside the sphere). – Insolation

@Pranav: Each "line" of the polygon on the surface of the sphere is a piece of a different great circle. – Parishioner

It is unclear what is meant by "These operations only need to output collections of points.". What kind of collections of points? – Catalysis

Answer 1

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.

Iridium

Answer 2

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/

Enphytotic

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.

Tetryl