Compare Shapes


(Ricardo) #1

Hello,

I need compare if one shapes exactly the same as another, same size, same curve, same diameter etc.

independent of rotation

Same

I need a script that tell me How many pieces do I have the same?

I’ve tried some ways, but the problem is if the shape is slightly rotate.

Any Tip

Thank you


#2

How about comparing curve lengths?


(Ricardo) #3

Thank you,

I already try compare the length and area and vertices.

The problem is if I have one shape that is a mirror, in this case the shape is not the same but the comparation is true, so, don’t work.


(Lando Schumpich) #4

If it’'s mirrored then the curvature vector won’t be the same


(Ricardo) #5

I say mirror with example to explain.

In other example is, two square shapes,
10x10 and other 15x5, the shape is not the same and both have the same length and same area and same vertices.


#6

I’d try the following, if the seam does not change, then the relationships between different points of the curve should be invariant:

bool CurvesAreTheSame(CurveA, CurveB) {
1) Normalize curve domains.
2) offset = 0.3
3) For i to 20
    - Get params t = i/20, t0 = (t- offset+1)%1, t1 = (t+offset)%1.
    - Get points pa,pb with t, p0a,p0b with t0, p1a,p1b with t1. 
    - Get vectors v0a (p0a-pa), v0b (p0b-pb) and v1a (p1a-pa), v1b (p1b-pb).
    - if( v0a.Length != v0b.Length OR v1a.Length != v1b.Length ) return false.
    - if( Angle(v0a, v1a) != Angle(v0b, v1b) ) return false.
4) return true.
}

#7

You may consider a multi-step verification.
Once the lengths match, for example divide the shape in 3 and check the lengths of AB and AC vectors…
Or even use the resulting 3 points to orient-copy 2 shapes to the worldXY origins and compare these point locations…


(qythium) #8

The original problem isn’t very well defined - is this limited to planar 2D curves? Will curves translated or rotated out-of-plane be considered ‘same’ as each other? What about 2 lines of the same length but different number of segments?

(Note that a mirrored 2D curve corresponds to 180º 3D rotation around the mirror axis)


(Ricardo) #9

The seam can change.

Yes is limited to 2d curves.

The objective is, find on drawing how many shapes is equal, can be a square, can be round or other shape, the shapes is always close and 2d in top view.

Tomorrow I can put one specific example.


(qythium) #10

You could maybe look at extracting the control points, checking to make sure that the count, degree and overall knot multiplicity is the same, and then doing rigid point set registration https://en.wikipedia.org/wiki/Point_set_registration and seeing if the error is below a certain threshold.

Edit: I thought a little more about this , maybe the above is a bit overkill for your situation (it was the first thing that came to mind).
For a less robust but simpler algorithm you could try:

  1. Calculate the curve centroid/ control pt average
  2. sort curve control points by distance to the centroid
  3. construct plane aligned to world Z axis and the nearest / farthest point from center
  4. orient one set of sorted points to the other
  5. check if distance between point sets below threshold

Grasshopper implementation:
2D_shape_comparison.gh (13.9 KB)


(Ricardo) #11

Thank you,

Sorry, I’ve never used Grasshopper.

do you have any examples in python?

Thank you


(qythium) #12

Ah, sorry for the late reply - could you figure it out from the ‘pseudocode’ instructions that I posted?


(Ricardo) #13

I have no idea how to do it direcly on python…


(qythium) #14

Maybe you could post what you have so far? Are you having trouble with the understanding of the algorithm or with the scripting syntax itself? ( i.e. are you familiar with using rhinoscriptsyntax / RhinoCommon )


(Ricardo) #15

Ok, this is the script that I am using, so, I compare the length and the area, if is the identical the geometry is true, if not the gemotry is false, (I also put a small tolerance, sometimes even being equal geometries, the script returns faulty)

Identical_pieces.py (1.8 KB)

I usually use rhinoscriptsyntax, never use RhinoCommon.


(qythium) #16

Hmm, so this turned out to be more tricky than I thought…

My algorithm outlined above works for comparing irregular shapes, but not for regular ones like the squares and circles, because there isn’t a consistent way of sorting their vertices due to their symmetry.

I’ll just leave what I’ve got so far, hopefully you can get some ideas from it -

Edit: see post below for updated solution

Identical_pieces_edited.py (3.1 KB)

P.S. don’t name your variables O (uppercase O), that can get really confusing to read… I also flatted a chunk of pyramid code.


(Radovan Grmusa) #17

Hi

When testing your solution in two cases i got wrong results.
Case A:
-two different curves (but the same length, the same area, and the same num.of ctrl points)
-result gives Registration error = 0

Case B:
-two identical curves (one is copy of the other moved by vector(6,0,0) )
-result gives Registration error = 62.2…

Internalised curves: 2D_shape_comparison_A_B_Curves.gh (3.8 KB)


(qythium) #18

Yeah, just realised my basic idea is flawed if your shapes have any sort of symmetry to them… I guess that’s the part of the reason for the complexity behind the actual robust algorithms I linked to in the wikipedia article.

For a small enough dataset though, a “dumb” brute-force approach might suffice… test every control point in the curve as a candidate seam point in both directions, to see if it matches the original one :sweat_smile: Worst case O(n*m) complexity, but probably closer to O(n) with early exit conditions (n = number of curves, m = number of control points)


(qythium) #19

The brute force approach turned out to be much simpler to code… see the attached:

Identical_pieces_v2.py (3.9 KB)

from Rhino.Geometry import Vector3d

def get_signature(crv):
    """
    Gets the signature of a closed 2d curve on the XY plane. 
    => Cross product of the relative positions of each control point w.r.t the starting seam point with the Z Axis
      then projected onto the vector of the first segment.
    """
    control_pts = rs.CurvePoints(crv)
    start_pt = control_pts[0]
    reference_vec = control_pts[1] - start_pt
    signature = [rs.VectorCrossProduct((pt - start_pt), Vector3d.ZAxis) * reference_vec for pt in control_pts]
    return signature


def compare_curve_to_sig(crv, sig, tol=0.01):
    """
    returns True if curve matches signature of another curve under specified tolerance
    """
    control_pts = rs.CurvePoints(crv)
    num_pts = len(control_pts)

    if num_pts != len(sig):
        return False

    for start_index in range(num_pts):
        # brute force check for every possible starting seam point
        start_pt = control_pts[start_index]
        
        # forward direction
        reference_vec = control_pts[(start_index + 1) % num_pts] - start_pt
        for i in range(num_pts):
            val = rs.VectorCrossProduct(control_pts[(start_index + i) % num_pts] - start_pt, Vector3d.ZAxis) * reference_vec
            if abs(val - sig[i]) > tol:
                break  # early exit
        if i == num_pts - 1:
            # completed inner loop without breaking -> all vectors match
            return True  # another early exit
        
        # backward direction
        reference_vec = control_pts[(start_index - 1) % num_pts] - start_pt
        for i in range(num_pts):
            val = rs.VectorCrossProduct(control_pts[(start_index - i) % num_pts] - start_pt, Vector3d.ZAxis) * reference_vec
            if abs(val - sig[i]) > tol:
                break  # early exit
        if i == num_pts - 1:
            # completed inner loop without breaking -> all vectors match
            return True  # another early exit

    # exhausted all possibilities
    return False

(Radovan Grmusa) #20

Actually, one thing you should take care of is double precision error.
For example

  • you have circle with center at point cA=(0,0,0)
  • and you create 10 points on that circle (lets say by dividing circle), pointsA[]
  • and sort these points by distance to cA, orderedPointsA[]

If you copy and move that circle, center point (cB), and points( pointsB[] ) by some vector (vx,vy,0) and again sort these points by distance to center point, orderedPointsB[] YOU MAY GET DIFFERENT order …
2D_shape_comparison_DoublePrecisionIssue.gh (16.7 KB)