StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
19303113
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
1
CommunityOwnedDate
CreationDate
2013-10-10T18:10:16.103
FavoriteCount
0
LastActivityDate
2015-02-24T22:05:33.113
LastEditDate
2015-02-24T22:05:33.113
LastEditorUserId
214070
OwnerUserId
214070
ParentId
17331203
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
UPDATE: Upon closer review of the animation and the Wikipedia article, I've decided my algorithm is not Bouncing Bubble. From the animation it is clear that Bouncing Bubble moves the bounding sphere, while my algorithm only grows it in one direction at a time. Also, my understanding is that Bouncing Bubble uses an approximation and may not contain all the points; however, there seems to be a tolerance parameter that you can control. I think my algorithm still has some nice properties: <ol> <li>It's O(n).</li> <li>It's incremental.</li> <li>It's guaranteed to contain all the points.</li> <li>It's dead simple. The only thing simpler would be to find the axis-aligned bounding box, and then put a sphere around that, but that's surely going to be a larger volume than this algorithm produces.</li> </ol> <hr> I came up with a O(n) incremental algorithm on my own, which from the description on Wikipedia I believe must be the Bouncing Bubble algorithm. I have no idea how close it comes to the minimally bounding circle. First I'll try to explain my reasoning behind the algorithm. It may help to draw this on paper. Imagine you have a bounding circle with some center C and radius r. You want to extend the circle to contain a new point P. You compute the distance d from C to P and find that it is greater than r, so it must be outside the circle. Now if you cast a ray from P through C, it exits the back of the circle at A. Now imagine you pin the circle down at A and then expand it along the ray back toward P. It will continue to contain all the previous points, and now it contains P. The diameter of this new circle is r + d, thus its radius is r' = (r + d) / 2. Walk along the ray from P to A by the distance of the new radius, and you're at the center of the new circle. Here's a sketch of the algorithm: <ol> <li>Initialize the bounding sphere to be centered on the first point C with a radius r of 0.</li> <li>For each remaining point P: <ol> <li>If the distance d from P to C is <= r, skip it.</li> <li>If d > r: <ol> <li>The new radius r' = (r + d) / 2.</li> <li>The new center C' = P + r' (C - P) / d.</li> </ol></li> </ol></li> </ol> And here's some Objective-C code I wrote just today: <pre><code>- (void)updateBoundingVolume { self.boundingSphereCenter = GLKVector3Make(0, 0, 0); self.boundingSphereRadius = 0; GLfloat* vertex = self.vertices; GLfloat* endV = vertex + 3 * self.vertNum; if (vertex < endV) { // initialize to zero radius sphere centered on the first point self.boundingSphereCenter = GLKVector3Make(vertex[0], vertex[1], vertex[2]); vertex += 3; } while (vertex < endV) { GLKVector3 p = GLKVector3Make(vertex[0], vertex[1], vertex[2]); vertex += 3; float d = GLKVector3Distance(self.boundingSphereCenter, p); if (d <= self.boundingSphereRadius) { // already inside the sphere continue; } // length of line from other side of sphere through the center to the new point // divide by 2 for radius self.boundingSphereRadius = (self.boundingSphereRadius + d) / 2; // unit vector from new point to old center GLKVector3 u = GLKVector3DivideScalar(GLKVector3Subtract(self.boundingSphereCenter, p), d); // step back from the new point by the new radius to get the new center self.boundingSphereCenter = GLKVector3Add(p, GLKVector3MultiplyScalar(u, self.boundingSphereRadius)); } } </code></pre>
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POBouncing Bubble Algorithm for smallest enclosing sphere
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USbugloaf
UserOwnerUserId
1. USbugloaf
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.