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

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking us to recommend or 开发者_如何学Gofind a tool, library or favorite off-site resource are off-topic for Stack Overflow as they tend to attract opinionated answers and spam. Instead, describe the problem and what has been done so far to solve it.

Closed 8 years ago.

Improve this 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!

---

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.

---

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/

---

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.