CODEWITHSUNDEEP
algorithmgeometry
user80551
user80551

Reputation: 1164

Computing points within an angular distance in spherical coordinates

Suppose I have a graticule (say 1 degree resolution) in spherical coordinates.

Spherical graticule

Now, assuming that a certain spherical object is in a known direction (known phi and lambda) and has a known angular diameter as viewed from the origin of the coordinate system, how can I efficiently compute a list of graticule points that "end up" on the object?

The naive algorithm is of course to calculate the angle between every graticule direction and the known (phi/lambda) direction of the object, and include the point if it is less than the angular radius. This is very slow if the graticule is fine.

What algorithms can I use to speed up this computation?

Upvotes: 2

Views: 567

Answers (2)

MBo
MBo

Reputation: 80187

Let's you have base coordinates (lat0, lon0), grid step da and max big circle arc angle AA (half of your "known angular diameter").

You can use algorithm similar to rasterization at Cartesian plane: enumeration of integer points on every scanline (here parallels) inside a circle.

Start from the central (lat0, lon0) point. Walk along meridian up and down and get points at the parallel inside given angular radius

Edit: big circle arc calculation has been rewritten

For every point at meridian (lat[i], lon0) get list of points with the same latitude usinf BigArc calculation from here (distance section). 

 var a = Math.sin(diflat/2) * Math.sin(diflat/2) +
         Math.cos(lat0) * Math.cos(alat) *
         Math.sin(diflon/2) * Math.sin(diflon/2);
 var BigArc = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));

(This method might fail when pole lies inside radius)

meridiansteps = Floor(AA / da)
for i = - meridiansteps to meridiansteps: 
    diflat = da * i
    alat = lat0 + diflat
    addpoint(alat, lon0)  
    diflon = da
    while BigArc <= AA:
        addpoint(alat, lon0  + diflon)  
        addpoint(alat, lon0  - diflon)  //symmetric
        diflon = diflon + da

Upvotes: 2

mcdowella
mcdowella

Reputation: 19601

If you can find the closest point on the graticule to the object, for instance by projecting the direction to the object onto the orientation of the graticule, then you have one point which is either on the graticule or not, and if it is not on the graticule, no point is.

Because the object is convex, its projection onto the graticule should be convex, so the points on the graticule which end up on the object should be contiguous. With one point on the object, you can use binary chop to find the two points on either side of it which are only just on the object.

The set of graticule points on the object is then all graticule points between these two furthest points.

Upvotes: 0

Related Questions