How to compare two shapes?

by

  1. handle shape as polygon

    convert your points (each line) to set of lines (length,angle) like on this image:

    polygon representation

    this ensures invariance on rotation/translation. If you see more lines with angle=PI join them together to avoid miss comparisons of the same shapes with different sampling also try to match the same CW/CCW polygon winding rule for both shapes.

  2. find start point

    Can be biggest or smallest angle, length … or specific order of angles+lengths. So reorder lines of one polygon (cyclic shift) so your shapes are compared from the ‘same point’ if they can.

  3. comparison – for exact match

    • number of lines have to be the same
    • perimeters must be the same +/- some accuracy

    so for example:

    fabs (sum of all lengths of poly1 - sum of all lengths of poly2) <= 1e-3

    if not shapes are different. Then compare all lengths and angles. If any one value differs more then accuracy value then shapes are different.

  4. comparison – size does not matter

    compute perimeter of both polygons l1,l2 and resize all lengths of compared poly2 to match perimeter of poly1 so all lengths of poly2 are multiplied by value = l1/l2;. After this use comparison from bullet #3

  5. comparison – shape deviations can still do positive match (size must be the same)

    try to set the number of lines to the same value (join all lines with angle close to PI). Then perimeters should “match” … fabs(l1-l2)<=1e-3*l1. You can use bullet #4 comparison

  6. comparison – size and shape deviations can still match

    just resize poly2 to match perimeter of poly1 as in bullet #4 and then use bullet #5

If you can not find the start point in booth polygons (bullet #2)

Then you have to check for all start point shifts so if your polygons have booth 5 lines:

    poly1: l11,l12,l13,l14,l15
    poly2: l21,l22,l23,l24,l25

Then you have to compare all 5 combinations (unless you found match sooner):

    cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25)
    cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21)
    cmp (l11,l12,l13,l14,l15),(l22,l23,l24,l25,l21)
    cmp (l11,l12,l13,l14,l15),(l23,l24,l25,l21,l22)
    cmp (l11,l12,l13,l14,l15),(l24,l25,l21,l22,l23)
    cmp (l11,l12,l13,l14,l15),(l25,l21,l22,l23,l24)

[Notes]

  1. There are also faster ways to compare but they can miss in some cases

    • you can compare histograms of lines, angles
    • you can use neural network (I do not like them but they are ideal for classifications like this)

  2. if your shapes have to be oriented in the same ways (no rotation invariance)

    then instead of vertex angle use the line direction angle

  3. if you can not ensure the same winding rule for both compared polygons

    then you have to check them booth:

    cmp (l11,l12,l13,l14,l15),(l21,l22,l23,l24,l25)
cmp (l11,l12,l13,l14,l15),(l25,l24,l23,l22,l21)

I know it is a bit vague answer but still hope it helps at least a little …

More Related Contents:

  1. determine if a point sits inside an arbitrary shape?
  2. How to determine if a point is in a 2D triangle? [closed]
  3. An algorithm for inflating/deflating (offsetting, buffering) polygons
  4. Algorithm to detect intersection of two rectangles?
  5. How to calculate an angle from three points? [closed]
  6. How to find the intersection point between a line and a rectangle?
  7. Sort points in clockwise order?
  8. How do I efficiently determine if a polygon is convex, non-convex or complex?
  9. Finding whether a point lies inside a rectangle or not
  10. How do you calculate the average of a set of circular data? [closed]
  11. Algorithm to check similarity of colors
  12. What is the fastest algorithm to calculate the minimum distance between two sets of points?
  13. Is there an efficient algorithm to generate a 2D concave hull?
  14. Largest circle inside a non-convex polygon
  15. How to check if line segment intersects a rectangle?
  16. What string similarity algorithms are there?
  17. Combined area of overlapping circles
  18. Calculate largest inscribed rectangle in a rotated rectangle
  19. Two Rectangles intersection
  20. Circle-circle intersection points
  21. Find the set of largest contiguous rectangles to cover multiple areas [duplicate]
  22. Sort Four Points in Clockwise Order
  23. Collision detection of huge number of circles
  24. How can I create an internal spiral for a polygon?
  25. Calculating the position of points in a circle
  26. Find if a point is inside a convex hull for a set of points without computing the hull itself
  27. Best way to find a point on a circle closest to a given point
  28. Algorithm for reflecting a point across a line
  29. Compute the area of intersection between a circle and a triangle?
  30. How can I perform Collision Detection on rotated rectangles? [closed]

Leave a Comment