How to compare two figures?

Question

Is there a way to compare two geometric shapes (or any two more general data structures) without using brute force at tolerance?

Brute force (comparing each value of each object with each value of another object) works, but it is slow, and I cannot use it.

I tried sorting data and comparing two sorted collections. It works fast, but only works with zero tolerance. As soon as I add tolerance, I get lost. The problem is that the two values ​​may be the same when I compare and differ when sorting.

Here are some details of my problem.

In my Excel VBA add-in, I have a collection of Shape objects created by a collection of Line objects created by two Point objects. The add-in views the CAD drawing through COM and creates a collection of Shape objects.

A simplified version can generate this:

  Shape 1 Shape 2 Point 1 0.0 5.0 0.0 4.9 Point 2 4.9 0.0 5.1 0.0 Point 3 5.0 5.0 5.0 5.0 

I need to find which forms are identical to those forms where the same means have the same shape, size and orientation, but not the same position (still this is trivial) plus or minus the tolerance (not so trivial!)

Point.IsIdenticalTo(OtherPoint) is defined as:

 Function IsIdenticalTo(OtherPoint As Point) As Boolean IsIdenticalTo = Abs(X - OtherPoint.X) < Tolerance And Abs(Y - OtherPoint.Y) < Tolerance End Function 

Working with the brute force of Shape.IsIdenticalTo(OtherShape) works, but it is too slow: if each Line(I) has the identical OtherShape.Line(J) and vice versa, then the two forms are identical. Sometimes I have hundreds of shapes with hundreds of lines, so brute force solution does not work for me.

I tried two approaches, including sorted collections. Both of them are fast, because comparing two sorted collections is faster than brute force, but both of them do not work in some conditions:

• The A SortedValues contains all the X and Y values ​​of all rows. The values ​​are sorted, so information about whether the value is X or Y is lost. I used this approach for several months without problems, but it does not work, for example, when the only difference between the two forms is between the points (10, 20) and (20, 10) . I added the line corner to the list of values, everything has improved, but there are still cases where this approach fails because some information is lost when the values ​​are sorted together. In the above example, this approach will work with the following collections:

   Shape 1 Shape 2 0.0 0.0 0.0 0.0 4.9 4.9 5.0 5.0 5.0 5.0 5.0 5.1 

• A SortedLines contains all rows sorted counterclockwise and starting at the point closest to the origin. This approach does not lose any information, but in the example above it does not work, because the sorting algorithm is not consistent with equality comparison. If the tolerance is 0.5, they should be identical, but the sorting algorithm creates the collections shown below. Everything becomes more complicated because my figures contain subforms, so there are many starting points on each figure.

    Shape 1 Shape 2 Point 1 4.9 0.0 0.0 4.9 Point 2 5.0 5.0 5.1 0.0 Point 3 0.0 5.0 5.0 5.0 

EDIT:

Forms are imported from an external graphics application through COM. The shape can be as simple as a rectangle or as complex as any fancy layout with 10 circles inside, 20 inner shapes and 30 lines. They are panels with holes and simple decorations, and sometimes they have the shape of a saw blade, which makes a dozen ribs.

Answer 1

• handle shape as a polygon

  convert your points (each line) into a set of lines (length,angle) , as in this image:

  

  this provides rotation / translation invariance. If you see more lines with angle=PI , combine them together to avoid the coincidence of the same shapes with a different selection, also try to match the same CW / CCW rule of the polygonal winding for both shapes.

• find starting point

  May be the largest or smallest angle, length ... or a specific order of angles+lengths . Therefore, reorder the lines of one polygon (cyclic shift) so that your shapes compare with the "same point" if they can.

• comparison - for exact match

  • the number of lines should be the same
  • perimeters should be the same +/- some accuracy

  for example:

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

  If not different shapes. Then compare all the lengths and angles. If any value differs more than the value of accuracy, then the shapes are different.

• comparison - size doesn't matter

  calculate the perimeter of both polygons l1,l2 and change the size of all lengths of the compared poly2 to match the perimeter of poly1 so that all lengths of poly2 multiplied by value = l1/l2; . After that use comparison with bullet # 3

• comparison - shape deviations can still have a positive result (the size should be the same)

  try setting the number of rows to the same value (connect all rows with an angle close to PI ). Then the perimeters must "correspond" ... fabs(l1-l2)<=1e-3*l1 . You can use bullet comparison # 4

• comparison - deviations in size and shape may still correspond

  just resize poly2 to fit the perimeter of poly1 like in pool # 4 and then use bullet # 5

If you cannot find the starting point in the polygons of the stand (bullet # 2 )

Then you need to check all the shifts of the starting point, so if your polygons have a stand of 5 lines:

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

Then you need to compare all 5 combinations (unless you have found a match before):

  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) 

[Note]

• There are also faster comparison methods, but in some cases they may skip

  • you can compare histograms of rows, angles
  • you can use a neural network (I don’t like them, but they are ideal for such classifications)

• if your figures should be oriented in the same way (without rotation invariance)

  then instead of the vertex angle use the line direction angle

• if you cannot provide the same winding rule for both compared polygons

  then you should check their stand:

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

I know this is a slightly vague answer, but still hope this helps at least a little ...

Answer 2

I have the same problem. I compute an adjacent matrix of vertices weighted with distances. It calculates the entire length and diagonals of the sides. Then, if the module of each row or column of the matrix matches the other matrix, then the two forms are the same. For tolerance, simply use the round () function before starting. The complexity is O (n2 / 2), because you only need to calculate half of the adjacent matrix, which is symmetric. The problem is that I cannot determine if the form is redrawn.