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 ?
أكثر...
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 ?
أكثر...