确定一个点是否在任意数量的框中的最有效方法是什么
我知道如何检查 X,Y 点是否是单个矩形区域，但假设我有多个可能重叠的区域（这些区域将具有 X,Y,宽度,高度,Z 索引（或 x1,y1,x2 ，y2 如果这更容易——我不会担心如何存储它，如果它是相关的）
是否有任何有效的算法来确定该点是否在某个区域内，而不必迭代每个区域，
我更喜欢没有的东西 。添加或删除区域时需要很长的重新计算时间，但这比查找要少得多，
谢谢！
I know how to check if a X,Y point is a single rectangular region, but say I have multiple regions that can potentially overlap ( the regions would have X,Y,Width,Height,Z-index ( or x1,y1,x2,y2 if that's easier -- I am not fussed on how I store that, if it's relevant )
Are there any efficient algorithms to determine if the point is inside one of the regions without having to iterate over every region.
I would prefer something without a long recalculation time when a region is added or removed, however that will be rarer then lookups.
Thank you!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以将区域存储到 四叉树（如果是 3D，则为八叉树）。这将帮助您在进入真正的碰撞测试之前拒绝大多数区域。
如果您有多个层，只需每层有一个四叉树，并根据您的点所在的层使用相关的四叉树。
You could store your regions into a Quadtree (or Octree if 3D). This would help you to reject most of the regions before getting into the real collision-test.
If you have multiple layers, simply have a quadtree per layer and use the relevant one according to the layer in which your point lies.
体积 kd 树？
Volumetric kd-trees?