StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>An octree will work as long as you can specify the spheres by their centres - it hierarchically bins points into cubic regions with eight children. Working out neighbours in an octree data structure will require you to do sphere-intersecting-cube calculations (to some extent easier than they look) to work out which cubic regions in an octree are within the sphere.</p> <p>Finding the nearest neighbours means walking back up the tree until you get a node with more than one populated child and all surrounding nodes included (this ensures the query gets all sides).</p> <p>From memory, this is the (somewhat naive) basic algorithm for sphere-cube intersection:</p> <p>i. Is the centre within the cube (this gets the eponymous situation)</p> <p>ii. Are any of the corners of the cube within radius r of the centre (corners within the sphere)</p> <p>iii. For each surface of the cube (you can eliminate some of the surfaces by working out which side of the surface the centre lies on) work out (this is all first-year vector arithmetic):</p> <p>a. A normal of the surface that goes to the centre of the sphere</p> <p>b. The distance from the centre of the sphere to the intersection of the normal with the plane of the surface (chord intersets plane the surface of the cube)</p> <p>c. Intersection of the plane lies within the side of the cube (one condition of chord intersection to the cube)</p> <p>iv. Calculate the size of the chord (Sin of Cos^-1 of ratio of normal length to radius of sphere)</p> <p>v. If the nearest point on the line is less than the distance of the chord and the point lies between the ends of the line the chord intersects one of the edges of the cube (chord intersects cube surface somewhere along one of the edges).</p> <p>Slightly dimly remembered but this is something I did for a situation involving spherical regions using an octee data structure (many years ago). You may also wish to check out KD-trees as some of the other posters suggest but your initial question sounds very similar to what I did.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload