2

I'm looking for an algorithm to calculate the 3d bounding box of a spherical polygon - i.e. the min/max X, Y and Z over that part of the surface of a unit sphere.

The purpose is to aid fast area-overlap calculations for large numbers of simple (convex) spherical polygons : Having all the bounding boxes will let you quickly calculate, for a given target polygon, a large majority of the other polygons which definitely do not intersect it (because their bounding boxes are disjoint).

I already have a calculation that does this type of selection, using polygon centres and maximum-radii. However, that will take O(N^2) time to calculate (for all source polygons; for all target polygons). Whereas, this approach would hopefully run in O(N.log N) time, as the XYZ information can be ordered and then sorted/searched (e.g. using kdtrees).

I think this is a bit less trivial than it sounds. For instance, the max X value on a polygon boundary segment (which is a great circle) can obviously occur at a point somewhere between the two endpoints. But also, in fact, an extreme value can occur somewhere inside the polygon away from the boundary -- for example, we must be able to get a max Z=1.0 for a polygon drawn around the North pole, even though its boundary lies entirely South of the pole.

Can anyone help with this ?

  • Your original problem of using bounding boxes to speed up intersection queries can be solved in two dimensions, as described at gis.stackexchange.com/questions/17788. The only complication is minor: the planar extent of a bounding box can be the union of two rectangles. The solution is to index the two rectangles individually. This won't change the asymptotic scaling of the calculation. – whuber Jul 1 '15 at 14:18

Your Answer

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

Browse other questions tagged or ask your own question.