计算2组凸多边形的相似度? [英] Calculating the similarity of 2 sets of convex polygons?

问题描述

我用不同的算法生成了2套凸多边形.每个集合中的每个多边形都由一个坐标数组[n_points，xy_coords]来描述，所以一个正方形由数组[4,2]描述，但是具有圆角的五边形具有[80,2]，另外75个点是用来描述曲率.

I have generated 2 sets of convex polygons from with different algorithms. Every polygon in each set is described by an array of coordinates[n_points, xy_coords], so a square is described by an array [4,2] but a pentagon with rounded corners has [80,2], with the extra 75 points being used to describe the curvatures.

我的目标是量化两组几何图形之间的相似度.

My goal is to quantify how similar the two sets of geometries are.

有人可以推荐这样做的任何方法吗?

Can anyone recommend any methods of doing so?

到目前为止，我遇到过:

So far I've come across:

• 锤击距离
• 豪斯道夫距离

我想知道2D多边形还有哪些其他鲁棒的相似性度量.理想情况下，该方法需要在凸多边形上具有鲁棒性，并能够度量大集合(每个集合10,000+)之间的相似度.

I would like to know what other robust measures of similarity for 2D polygons. The method ideally needs to be robust across convex polygons and and give a measure of similarity between large sets (10,000+ each).

推荐答案

假定两个多边形都对齐，居中和凸出，则可以尝试通过计算较小多边形的面积与两个多边形的凸包的面积之比来评估相似性.

Assuming that both polygons are aligned, centered and convex you could try to assess similarity by computing ratio of area a smaller polygon to area of convex hull of both polygons.

比率=最小值(面积(A)，面积(B))/面积(凸包(A，B))

Ratio = Min(Area(A), Area(B)) / Area(ConvexHull(A, B))

如果两个多边形相等，则比率将为1，如果点和正方形严重不同，则比率将为0.

The ratio will be 1 if both polygon are equal, and 0 if the differ severely like a point and a square.

多边形的面积可以用O(N)时间计算.请参见多边形面积.凸包可以用O(N log N)计算.请参见凸包计算.通过合并已排序的两个多边形的顶点并应用 Graham扫描算法.

Area of the polygon can be computed in O(N) time. See Area of polygon. The convex hull can be computed in O(N log N). See Convex Hull Computation. It could be speed up to O(N) by merge-sorting already sorted vertices of both polygons and applying the second phase of Graham Scan Algorithm.

这篇关于计算2组凸多边形的相似度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！