Compare Shapes

Yes, that was exactly what I meant when I said the method wouldn’t work for shapes with symmetry- there’s no way of differentiating symmetrical points and it comes down to essentially random numerical error.

My updated method should work for those cases through simple brute force… although thinking about it now, it only considers the curves’ control points and not their degree or knot vectors :confused:

So you might have a square matching a squircle of the same size… but given how NURBS knots behave at their seams, robust checking for those cases would be a bit trickier to incorporate.

Edit: Nope, turns out Rhino treats closed curves of degree N by wrapping the last N control points, so they would register as different.
image

The fact that seam can change an curve still looks the same is excluding control points comparison.
If we go further, circle for example can be rebuilt from 8/2 … to n/3 curve, where n is high int number so max.deviation is smaller than Rhino.RhinoMath.ZeroTolerance so basically both curves are from that point of view the same.
Also, if we have polyline, lest say rectangle, we can explode it, rebuilt one side from 2/1 to 10/1 (point counts/degree) curve, join everything together and we will again have two curves that we can consider the same even if they have different CP count.

Well… if we’re talking about arbitrary seam changes anywhere along the curve’s domain and arbitrary rebuilding of curves, that goes into the realm of fuzzy matching, and probably some overcomplicated heuristic algorithm from the field of Computer Vision would be needed (see wiki article above)

I made the assumption for simplicity’s sake that @MatrixRatrix’s original question only concerned matching curves with same number of control points and seam changes occurring at control points – if you do have a robust solution that covers those concerns you raised, I would be interested to find out :slight_smile:

Thank you all,

for simplicity I will show an example of what I want to do, and with this show that there is no control in the seam nor in the number of control points.

So, I build an EX: pavement as in the image:
pave

After drawing I need to separate into several pieces, for this I use the “curveBoolean” command to find all the regions,

“curveBoolean” returns a geometry that can not control the seam or the number of points, it can change depending on the original geometry.

Is possible I have two pieces exactly the same but with more number of controllable points, but the geometry is exactly the same.

This is a very simple little example, the goal is to find the parts quickly, otherwise I have to check one by one, this can take a long time in a more detailed project.

So, definition of problem to be solved in this case should look something like this.
Two curves (cuveA and curveB) shall be considered the same if:

  1. one of the curves (lets say curveA) can be transformed by move and/or rotate transformation in such a way that resulting curve curveA’ is “overlapping” with curveB

Overlapping means that
2) cuveA.Length == curveB.Length
3) cuveA.Knots.Count == curveB.Knots.Count
4) cuveA.Points.Count== curveB.Points.Count
5) cuveA.Degree == curveB.Degree
6) cuveA.Dimension == curveB.Dimension
7) cuveA.Domain == curveB.Domain
8) cuveA.IsPeriodic== curveB.IsPeriodic
9) cuveA.SpanCount== curveB.SpanCount

But if:

algorithm will be different…

Ah, your problem is easier to understand now with the example - just wondering, if you run _SimplifyCrv on your geometries and use my attached code above, does that give you good results or close-enough results that can be manually processed in a few extra steps?

Or are there any specific features of your ‘tiles’ such as number of corners, at least N straight sides, etc. that might make it easier to process? (programming a general shape-recognizer is not a trivial task, as pointed out above)

“Can be transformed” is the key phrase here and what makes this problem not as simple as it might seem… when given a solution, it’s indeed simple to check whether the curves are overlapping to a certain specification, but it’s much harder for the computer to discover such a transformation and if it even exists, given two input curves.

( Here lies the basis of complexity theory, P vs. NP and all that… the fact that we can intuitively ‘recognize’ two curves as the same says more about our highly tuned pattern-recognition abilities)

Hello qythium,

The result of Simplifycrv on the curves seems to me not to have great effect.

I know it’s not the same thing but, on the left was generated by my initial script (Check only length and area), and on the right was generated with your script,

compare

My script has detected all the parts that are the same, not yours.

The problem is that I know I can not trust my script for obvious reasons.

I’ve got an idea, how about using the G1 discontinuities (i.e. corners) as the reference points? Replace calls to rs.ControlPoints() with rs.CurveDiscontinuity() and see if it works any better-

Edit: turns out the rhinoscript method doesn’t consider kinks at seam points to be discontinuities, so use this function instead:

def get_discontinuities(crv_id):
    rs.SimplifyCurve(crv_id)
    crv = rs.coercecurve(crv_id) # RhinoCommon Curve
    t = crv.Domain[0]
    pts = []
    while t < crv.Domain[1]:
        success, t = crv.GetNextDiscontinuity(Rhino.Geometry.Continuity.G1_locus_continuous, t, crv.Domain[1])
        if not success:
            break
        pts.append(crv.PointAt(t))
    return pts

Identical_pieces_v3.py (4.3 KB)

Note, this assumes your ‘tiles’ have corners – it won’t work on completely smooth curves like circles.

Thank you,

At this moment I can not do many tests but, I think it is working well.

now it’s the way it works, it only works in swith corners, now I just need to do the same in forms without corners.

Then just create an if, if the entry shape has corners then only compare shapes with corners, and vice versa.

Giving it a try.

Lets assume that 2d shapes (= planar closed curves) may be very different in sense of “topology” - different degree, number of c-points, number of discontinuities, etc. But they can be very similar in look. So we have to decide what it means to be similar. So lets say curves are “Similar” if:

  1. they have same Length (within given LengthTolerance)
  2. they have same Area (within given AreaTolerance)

Next thing that is important for further comparison is AreaCentroid.
3.1. For every curve we find AreaCentroid
3.2. For every curve we find point closest to to AreaCentroid, lets call it InitialClosestPt
3.3. We measure distance btw AreaCentroid and InitialClosestPt and for similar curves this distance should be within given tolerance
So for now if any of conditions 1., 2. or 3.3 is not valid we consider curves not to be similar, otherwise we have to go on with checking additional properties.
Here is photo of curves which have first 3 conditions valid but are obviously different:

One more thing we should consider is the fact that curve can have more than one closest point (closest to AreaCentroid). Such closest points are properties that are important for us because if curves are Similar we should be able to find closest point on first curve that “corresponds” to at least one closest point on second curve. Meaning of corresponds is that if we orient first curve by using AreaCentroid-ClosestPoint as references we will end up with more-less overlapping curves (within given tolerance).
Because there may be many closest points on some curves it would be good to do some check if we can early detect that curves are not similar.
So if we use this approach to previous curves we see that each curve has more closest points.
For each curve we construct circle with center in AreaCentroid and radius eq. to distance AreaCentroid - InitialClosestPt and intersect such circle with curve - this will give us all closest points:

Now we can create some algorithm that should produce similar result for similar curves.
One approach is to divide curve by lets say 11 points using DivideByCount(11,…) for every ClosestPoint (changing seam of curve to ClosestPoints[i] and then DivideByCount() ).
So curve will be similar if there is at least one division on curve one (division = 11 points on curve) that corresponds to at least one division on curve two.
So now we come to the point where we can define corresponds criteria:

  1. if we construct polyline from division points on first curve and similarly on second curve, such polylines should have similar length (equal within given tolerance)
    This condition 4 failed for our two curves so we assume that these two curves are not similar:

We can go on with creating additional criteria for checking similarity:

  1. For example, we can construct vectors from AreaCentroid to dividing points, and again we can have more then one set of vectors if curve has more then one closets point. After we create such vectors for each closets point set of dividing points on each curve we can “compare” this vectors. For example we can sum these vectors and compare resulting vector lengths btw curves. If we don’t find any set of vectors on first curve that has the same length (within tolerance) with at least one set of vectors on second curve, we can assume that curves are not similar

And so on…

1 Like

Nice, I had been thinking about how to differentiate and group sets of equidistant points but somehow it didn’t occur to me to use circle intersections. One possible concern is if the curves aren’t straight-sided polylines but has arcs centered around the area centroid…
image
(imagine these are the same length and have random knots all over the place)

It’s quite an interesting puzzle :slight_smile:

Can you post curves for which you think there may be problem to detect similarity.
I already have code working ( but needs some cleaning before I can post it) so I would like to test it.

Here is the code that checks for similar closed curves (2d-shapes) in XY plane based on previously described algorithm…

If tolerances are larger nums than it will take more tome to determine which curves are similar (ie. early exit conditions will be passed because of larger tolerance).
First is checked Length, after that Area, etc.
Order can be changed if methods are added in different order to the List of Func<>.
Main method that does the job, CompareShapesE(…) is called recursively till there are methods in the list of methods that compare two curves based on their index…
2D_shape_comparison_RG2.gh (372.0 KB)