什么是管理正方形几何细分的适当数据结构？
我正在寻找一种数据结构，可以管理矩形对象（O LxH）的数据以及矩形对象的所有细分（内部分区）。
人们应该能够添加更多分区，以及访问现有分区。每个分区应被视为另一个矩形对象 (O LxH)。
我想我可以使用 BSP 树，但我认为这可能是解决我的问题的过于复杂的解决方案。
图中的示例
分区“B”应该是另一个具有原点、长度和长度的对象高度。
I'm looking for a data structure that can manage the data of a rectangle object (O LxH) as well as all the subdivision (internal partitions) of the rectangle object.
One should be able to add more partitions, as well as to access to the existing partitions. Each partition should be treated as another rectangle object (O LxH).
I was thinking I could use a BSP tree but I think that would probably be an over-sophisticated solution for my problem.
Example in the figure
the partition 'B' should be another object with an Origin, a Length, and an Height.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
基本实现是
......通常您需要添加递归 split() 和locate() 方法。
您尝试实现的内容看起来类似于四叉树 - 请参阅 http://en.wikipedia.org/wiki/四叉树或kd树，http://en.wikipedia.org/wiki/ K-d_tree。您可以尝试现有的实现。
The basic implementation is
...and typically you will need to add recursive split()- and locate()-methods.
What you try to implement looks similar to a Quadtree -- see http://en.wikipedia.org/wiki/Quadtree or a kd-tree, http://en.wikipedia.org/wiki/K-d_tree. You can try existing implementations.
我想说你肯定需要某种树。
您提到您担心 BSP 树对于这个问题可能过于复杂——这取决于您需要解决方案的稳健程度。您可能还想考虑对象是否可以划分为两个以上的部分 - 如果不能，那么您可以使用二叉树。
基本上，树中的每个节点都有一个大小和形状以及子（分区）节点。此外，该节点将负责确保其子节点的大小和形状有意义 - 即它们不重叠，它们填充整个父节点，并且不会超出父节点。
可以通过为每个节点提供相对于其父节点的相对 ID 来完成对分区的访问。第一个子节点获取
relativeID = 0，第二个子节点获取 1，依此类推。对每个级别的每个节点的子节点重复此操作。然后，您可以编写一个方法，该方法接受相对 ID 列表，并使用它来遍历树并找到正确的分区（每个级别剥离一个相对 ID，以便移动到下一个级别）。I'd say you definitely need some kind of tree.
You mention that you're worried that a BSP tree might be over sophisticated for this problem -- that depends on how robust you need the solution to be. You might also want to consider whether objects can be partitioned into more than two pieces -- if not, then you could use a binary tree.
Basically, each node in the tree would have a size and shape, and child (partition) nodes. Also, the node would be responsible for ensuring that the sizes and shapes of its children make sense -- i.e. that they don't overlap, they fill the entire parent, they don't go outside the parent.
Accessing the partitions could be accomplished by giving each node a relative id with respect to its parent. The first child gets
relativeID = 0, second child 1, etc. Repeat this for each node's children at every level. Then you can write a method that takes in a list of relative IDs, and uses that to traverse the tree and find the correct partition (each level strips off one relative ID, in order to move to the next level).