如何确定两个凹/凸形状是否处于特定距离

How to determine if two concave/convex shapes are at particular distance?

本文关键字：是否距离于特定何确定两个更新时间：2023-09-26

我必须确定两个凹/凸形状之间的距离是否为d。我知道分离轴定理在确定距离时可能很方便，但它在O（n2）时间内运行，我正在寻找适用于任何形状的O（n）或O（nlogn）算法。我想在JavaScript

中为任意两个SVG实现这一点

这是一个广泛而艰巨的问题。

要处理最困难的情况（如椭圆/Bezier距离），您需要以某种方式压平轮廓，因此我建议在所有情况下都要压平，并仅解决两个多边形的问题。

令人惊讶的是，你在网上几乎找不到关于两个多边形之间距离的资源。

假设处理的是形状的内部（而不仅仅是轮廓），则必须首先检查多边形是否存在空心相交（否则距离为0）。我想这可以在时间O（N.Log（N））内完成。

然后，如果我是对的，两个多边形之间的最近距离是所有顶点到另一个多边形的最短距离。如果你构造两个多边形的Voronoi图（在时间O（N.Log（N））中是可行的），你会得到两个平面细分，在这个细分中，你可以解决每个点在时间Log（N）中的点位置问题。

所有这些加在一起应该产生O（N.Log（N））解决方案。你需要一个专门的计算几何库来实现这一点。