2
\$\begingroup\$

Lets say we have a set of points (x, y, z) where we know 0 < x < 1 (same for y and z). Now that 3d space is populated with monsters, players or what not. The points represent their location. We want to find the largest vacant 3d space. What would be an effective algorithm to find, let's say, the k largest disjoint empty boxes inside that space?

I was thinking of using Voronoi Diagram and measuring the space near each seed (the points being the seeds) and looking for pairs of neighbors that have a large space.

Improve this question
\$\endgroup\$
6
  • \$\begingroup\$ What are the rules for defining the concept of "empty space" in your context? That is, how do two different "empty space" regions know they're separate? The question is potentially very interesting, but I think it needs this extra bit of clarification to benefit from correct answers. \$\endgroup\$
    – teodron
    Mar 1, 2015 at 15:00
  • 1
    \$\begingroup\$ Well, in the case I described, it's a box (not axis aligned) that does not contain any of the points. I don't actually want a box. Any convex 3d shape would be fine. I just figure a box is simpler. It wouldn't be bad to generalize it and find the largest k disjoint boxes that contain only m points (where m is very small). \$\endgroup\$
    – AturSams
    Mar 1, 2015 at 15:20
  • 1
    \$\begingroup\$ If you restrict it to the largest convex space, you might be able to use a greedy approach whereby you delete points from the convex hull which reduce its size the least, take the convex hull of that, and keep iterating until there are no more points inside the hull (only on the surface). A similar approach could be used for the larges bounding box. \$\endgroup\$
    – mklingen
    Mar 1, 2015 at 22:05
  • 2
    \$\begingroup\$ Note that if there are no restrictions like convexity, this problem is ill-formed, because the largest empty space is trivially the unit cube minus the points in the point set. \$\endgroup\$
    – mklingen
    Mar 1, 2015 at 22:06
  • 1
    \$\begingroup\$ Another thing you could do is voxelize the cube to some resolution, and then do a flood fill of all the voxels that contain no points. The connected components of this flood fill are the empty regions. \$\endgroup\$
    – mklingen
    Mar 1, 2015 at 22:11

1 Answer 1

Reset to default
1
\$\begingroup\$

EDIT:

My first approach is still below, but I found a problem with it. If the large empty region is on a border (outside the convex hull of your points), it won't be detected. Putting points on the border like I did with the corners doesn't help because the triangles can be made bouncing from your points to those new points.

Another approach, which ought to work but might be too expensive to compute, is to generate a mesh of evenly spaced points across the space and use a nearest neighbors algorithm on each of the points in this mesh to find the point from your original points that's closest. The mesh point that is most distant from anything is the center of the biggest empty region.

I don't know how to find the second most empty region.

OLD ANSWER:

I think you're on the right track. I'm trying to do a similar thing for a scientific application in Python (where my problem is N-dimensional).

Take your set of points and add the corners of the space to the set of points.

Then you can do a Delaunay triangulation (this the dual of Voronoi diagram) in 3 dimensions. (The library call in Python is scipy.spatial.Delaunay.)

Go through all the triangles (in 3 dimensions, these are tetrahedrons) and calculate their volume. (The library call in Python is scipy.spatial.ConvexHull.volume.) I think these are your biggest empty spaces, or if they're not, it's at least an indicator of a big empty space.

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ I think you can do one better, and calculate the volume of the circumsphere of each tetrahedron, which by the Delaunay condition has no points in its interior. The distinction matters because you can sometimes have a skinny tetrahedron with a large circumsphere. \$\endgroup\$
    – DMGregory ♦
    Apr 21, 2021 at 23:20
  • \$\begingroup\$ @DMGregory the volume of that largest circumsphere could fall mostly outside the "play area", as it does in the diagram on the "Delaunay triangulation" Wikipedia page. \$\endgroup\$
    – Jim Hunziker
    Apr 22, 2021 at 12:29
  • \$\begingroup\$ Sorry, I considered it obvious that one would clip any spheres crossing the play area bounds when computing their volumes, counting only the relevant portion inside the bounds. \$\endgroup\$
    – DMGregory ♦
    Apr 22, 2021 at 12:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .