CODEWITHSUNDEEP
algorithmgeometrysimilarity
Zizi96
Zizi96

Reputation: 519

Calculating the similarity of 2 sets of convex polygons?

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:

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).

Upvotes: 0

Views: 1368

Answers (2)

Yulia Grinblat
Yulia Grinblat

Reputation: 31

As I understood you look for shape similarity or shape analysis algorithms. You will find more robust methods here: https://www.cs.princeton.edu/courses/archive/spr00/cs598b/lectures/polygonsimilarity/polygonsimilarity.pdf and https://student.cs.uwaterloo.ca/~cs763/Projects/phil.pdf

  1. Turning function;
  2. Graph matching;
  3. Shape signature.

Upvotes: 2

tstanisl
tstanisl

Reputation: 14167

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.

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

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

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.

Upvotes: 2

Related Questions