4
$\begingroup$

Suppose I have a sphere of points with two coordinates (two angles), all points are located on a unit sphere, so radius of the sphere is one.

Now my problem is, I want to find empty circles, or rather the center of circles, on that sphere, that fit between points with a radius that is greater than a specified angular radius, for example 0.1 rad. And with empty is meant, that inside that circle there are no other points.

As a practical example, think of the points on the sphere as stars limited by magnitude, and the circle describes an empty, dark spot for doing some background measurements with an instrument, whose field of view should be smaller than the diameter of the circle.

My idea is first to calculate all great arc distances between three close stars, or formulated differently, to span a net of spherical triangles onto that sphere.

And after that trying to calculate the in-circle in the triangles.

This is where I am stuck, I don't know how to do this on a sphere, in cartesian 2D-Coordinates this would be easier.

I suppose I can't use the formulas for an in-circle in cartesian coordinates for spherical coordinates, or only for a really rough estimation.

Do you have some ideas that would push me into the right direction?

$\endgroup$
2
$\begingroup$

Find the convex hull of the set of points. This is a polyhedron, and for every face of the polyhedron, all the points in your given set are either on that face or on the "inside" side of that face.

Where the plane of each face of the convex hull intersects the sphere is a circle. On one side of this plane there are no points from your original set. The part of the sphere on that side of the plane is the "dark spot" you are looking for.

One way to find the center of one of the "dark spots" is to find a unit vector orthogonal to the plane by which you found it. Either that unit vector or the unit vector in the opposite direction is the displacement from the center of the sphere to the center of the "dark spot".

Of course you can then examine all the "dark spots" to see which one is the largest, if that is your goal, or simply examine them until you find one that is large enough.

There are algorithms for finding convex hulls in three dimensions, but if you do not want to use any of them, and there are not too many points, you can take the points three at a time and put a plane through the three selected points. If all other points in your set are on the same side of that plane (or on the plane) then you have found one of the faces of the convex hull.

It is easier to work all of these steps in Cartesian coordinates than in polar coordinates. So your first step should probably be to convert all the coordinates to Cartesian triples.

$\endgroup$
  • $\begingroup$ Thanks, I'll read into that. Your answer also gave me another simple idea: After conversion to cartesian triples I can do a simple 3D circle fit, since I can "convert" my FOV on the unit circle to a "cartesian radius". $\endgroup$ – user3199134 Mar 3 '15 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.