假设您在 R^2 中有一组段（称为 S）。每个段都包含在一个尺寸为 WxH 的盒子中（因此，集合 S 有四个额外的段，盒子的每一侧都有一个段）和一个要添加到 S 的段 s。段 s 从点 A 开始（将属于到 S 中的一个线段）并在 B 点结束。我要计算的是点 B'，这样 B'属于 S 中的一个线段，而 AB'不与 S 中的任何其他线段相交。是否有在不使用蛮力算法的情况下计算 B' 的 wat（即，将 AB 与 S 中的每个其他段相交）？
问问题
85 次
1 回答
0
Ericson的“实时碰撞检测”（目录）是解决此类问题的绝佳资源。第 7 章空间划分列出了许多适合解决此类问题的方法。
考虑从八叉树、KD-Trees 或空间散列开始。它们都相当容易实现，并且会使问题从 O(n^2) 变为（从内存中）O(n log n)
于 2012-06-04T10:07:33.837 回答