Java的2D路径比较库

Question

我有一条二维线（它可以是带有环的曲线），还有多条类似的路径。我想将第一条路径与其余路径进行比较，并确定哪一条相似度最高（如果可能，以百分比表示）。

我在考虑将路径转换为位图，然后使用库来比较位图，但这似乎有些过度了。在我的情况下，我只有一个由点组成的不间断路径，没有不同的颜色或其他什么东西。

有人能帮助我吗？

编辑：

所以第一条线是黑色的。我将所有其他线与它进行比较。我想要一个可以说出：红线正确率为90%（因为它几乎具有相同的形状，并且靠近黑线）；蓝线的正确率为5％ - 这个百分比是为了方便举例而编造的...- 因为它具有类似的形状，但更小且与黑色路径不接近。

因此相似性标准应该是：

- 线之间的接近程度 - 它们的形状是什么 - 大小如何

（颜色无关紧要）

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

- Florin Vistig

---

线条在哪种对象中表示？ - mauretto

一个点的数组（带有x，y坐标） - Florin Vistig

相似性的标准是什么？ - stan0

感谢您的编辑，它使问题更清晰了。现在我会从寻找行末（或者寻找两行中最上方、最左侧的点）开始，并计算距离。然后我会尝试沿着这两行移动，并为每次移动重新计算距离。最后，我会将距离总和起来。 - bpgergo

Answer 1

我可以想到两种方法来表达两条线段N和M之间的相似度。假设p0和q0总是比p0和qs更接近。 1) 面积 使用N和M之间围绕的面积之和，当N和M差异越大时，面积越大。为了使N和M形成一个封闭的形状，您应该用直线段连接p0和q0以及pr和qs。为了能够计算封闭区域的表面积，在N和M的线段交点处引入新点，这样您就可以获得一个或多个没有孔洞或自相交的简单多边形。这样一个多边形的面积相对容易计算（在网上搜索“多边形面积计算”），将面积相加，您就有了（不）相似性的度量。 2) 采样 取预定义数量（例如1000）的N上的采样点O（可以均匀分布在整个线上，也可以均匀分布在每个N的线段上）。对于O中的每个采样点o，我们将计算到M上最近对应点的距离：结果是这些距离的总和。接下来，反转角色：从M中取样点，并计算每个最近对应的点在N上的距离，并总和它们的距离。这两者中产生最小总和（它们可能不相同！）是（不）相似性的度量。
注意：要在M上定位最近对应的点，请找到M中每个直线段的最近点（这是简单的代数，可以在Google上搜索“点和直线段之间的最短距离”）。使用距离o最小的线段的结果。 比较 方法1需要几何原语（点、线段、多边形）和对它们进行的操作（例如计算交点和多边形面积），以便实现。这更费力，但产生更强大的结果，并且更容易针对由许多线段组成的线进行优化。

方法2需要选择一个“正确”的采样点数，如果线具有交替部分，其中有很少的细节和很多细节（即很多靠近一起的线段），则可能很难（例如1000）确定采样点数。并且随着大量采样点的增加，其实现很快会变得（非常）缓慢（将每个采样点与每个线段匹配是一个二次操作）。好处是它不需要很多几何运算，并且相对容易实现。

- Leon Bouquiet

---

非常感谢您的深入回复。这两种方法在我的情况下都很好！干杯 - Florin Vistig