用于二维路径比较的 Java 库

Question

我有一条 2d 线(它可以是一条曲线，带有环等)，以及多条相似的路径。我想将第一条路径与其余路径进行比较，并确定哪条路径最相似(如果可能，以百分比表示)。

我在想也许可以将路径转换为位图，然后使用库来比较位图，但这似乎有点过分了。在我的例子中，我只有一条不间断的路径，由点组成，没有不同的颜色或任何东西。

谁能帮帮我？

编辑:

所以第一行是黑色的。我将所有其他行与它进行比较。我想要一个可以说的库或算法:红线准确率为 90%(因为它的形状几乎相同，并且接近黑线)；蓝线准确率为 5% - 这个百分比是为这个例子弥补的...... - 因为它有相似的形状，但它更小并且不靠近黑色路径。

所以相似性的标准是:

• 线条之间的距离有多近
• 它们有什么形状
• 它们有多大

(颜色无所谓)

我知道不可能找到一个考虑到所有这些的图书馆。但最重要的比较应该是:它们的形状和大小是否相同？我可以自己计算的距离。

Answer 1

我可以想到两种度量来表示两条线 N 之间的相似性(定义为点 p0、p1...pr 之间的直线段) M(在 q0、q1、...qs 之间有直线段)。我假设 p0 和 q0 总是比 p0 和 qs 更近。

1)面积

使用 N 和 M 之间包围的面积之和，其中 N 和 M 的面积越大，差异越大。 要使 N 和 M 形成闭合形状，您应该将 p0 和 q0 以及 pr 和 qs 用直线段连接起来。 为了能够计算封闭区域的表面，在 N 和 M 的线段之间的交点处引入新点，以便您获得一个或多个没有孔或自交的简单多边形。这种多边形的面积计算起来相对简单(在网络上搜索“多边形面积计算”)，对面积求和，就可以衡量(不)相似性。

2)采样

取位于 N 上的预定义数量(例如 1000)的样本点 O(相对于整条线均匀分布，或均匀分布 在 N) 的每个线段上。对于 O 中的每个样本点 o，我们将计算到 M 上最近对应点的距离:结果是这些距离的总和。 接下来，反转角色:从 M 中取出样本点并计算 N 上每个最近的对应点，并将它们的距离相加。 这两者中哪一个产生最小的总和(它们可能不一样!)是(不)相似性的度量。
注意:要定位M上最近的对应点，请定位M中每条直线段的最近点(这是简单的代数，谷歌“点与直线段之间的最短距离”) .使用与 o 距离最小的线段的结果。

比较

方法一需要几个几何图元(点、线段、多边形)和对它们的操作(比如计算交点和多边形面积)， 为了实现。这需要更多工作，但会产生更稳健的结果，并且更容易优化包含大量线段的线。

方法 2 需要选择“正确”数量的样本点，如果线条有交替部分且细节很少，这可能很难 和有很多细节的部分(即很多线段靠在一起)，它的实现可能会很快变得(非常)慢 具有大量样本点(将每个样本点与每个线段匹配是二次运算)。 从好的方面来说，它不需要大量的几何运算并且相对容易实现。