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
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.
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
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)
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:
they have same Length (within given LengthTolerance)
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:
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:
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
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…
(imagine these are the same length and have random knots all over the place)
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)