Public Group

# generate pair of parallel planes to evenly divide set of 3d points

This topic is 3471 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Okay, I'm creating a game engine for a "space sim" type game, where you do a lot of interstellar travel. Consequently, the entities are easily represented as single points, and the biggest challenge is what to do with all that empty space. My plan is to create something akin to a binary tree. I need an algorithm that will do this, as part of the map pre-compiling process: Take a set of unsorted 3D points (a parent node.) Generate two parallel planes. The two planes act as a "thick" plane that divides up the 3D points into two sets (child nodes.) The planes must fit these criteria: * None of the points fall between the two planes (mandatory.) * None of the points are on the two planes (mandatory.) * The two sets of 3D points should have as similar a number of points as possible. * The two planes must be as far apart as possible, to maximize the amount of negative space being removed. How will I go about generating these planes? EDIT: By the way, the only languages I know are BASH, C++, and Python. I plan to prototype it in Python, and rewrite it in C++ if I have to.

• 10
• 48
• 12
• 10
• 10
• ### Forum Statistics

• Total Topics
631382
• Total Posts
2999679
×