在 2D 空间中高效查找矩形的最近非碰撞位置？

Question

我一直在努力解决与 2D 空间中的碰撞检测和定位相关的问题，我确实可以使用一些指导来实现良好的性能。

我有一个矩形边界（蓝色）。在这个空间内，有一个可碰撞几何图形的列表，包括轮廓线和其他矩形（以红色标记）。此外，我还有其他矩形（标记为绿色），它们不得与红色矩形碰撞。

当绿色矩形与红色矩形碰撞时，我需要确定绿色矩形最近的有效位置，以确保它不与任何红色矩形和线条重叠。

我最初尝试使用强力方法来找到矩形最近的非碰撞位置。然而，这种方法在处理大量碰撞时可能会导致性能问题。

预期产出：

预期输出应提供绿色矩形最近的有效中心位置，按沿不同轴的移动进行分类：

Answer 1

为了设计一种高性能方法来解决这个问题，我们需要更多关于您的问题的详细信息。绿色矩形是否始终具有相同的尺寸等。自定义算法越具体和详细，执行效果就越好。可能改变的变量越多，算法就需要越通用、越慢。

此外，您的问题在运行之间有何变化。例如，对于数千次运行，红色矩形可能始终位于相同位置，因此值得进行预处理来识别可以从中选择的绿色安全位置，而不是在所有可能位置中搜索每个新运行。

您最关心的是什么？您是否会接受一种算法，该算法在 90% 的情况下给出最近的新位置，否则给出的答案比实际最近的位置远 10 个单位，但运行速度快 10 倍？

我注意到您提议使用Python。通常对于此类问题来说这太慢了。 C++ 将为您在相同的算法上提供高达 50 倍的性能提升（前提是您在两种语言中的实现同样熟练）

最后，您获得了什么性能，您需要什么性能？