How to compare shape of Bezier curves

Question

I want to compare 2 Bezier curves. I know coordinates of endpoints and control points, but for 2 compared curves this coordinates may not be the same. I need to compare shape of this curves. To be"true" that shapes have to be approximately the same.

I work with javascript and paper.js.

Please see the image:

https://habrastorage.org/files/825/6e5/36c/8256e536c9ce4f01bf12d792473038d5.png

Where is the way out? Thanx.

Answer 1

A cubic Bézier spline is defined by any four points: start, control-1, control-2, and end, which I will number 0, 1, 2, 3. For now we'll assume that the four points are distinct, and no three are in a straight line.

The curve can take three fundamentally different forms, depending on the direction of the turns between lines 0--1 and 1--2, and between 1--2 and 2--3, and whether 0--1 and 2--3 cross.

In type 1, both turns are to the right, or both are to the left, and 0--1 doesn't cross 2--3. That gives a curve like a, b or c in the questioner's example. In type 2, the first turn is to the left and the second to the right, or vice versa, giving a curve like d in the questioner's example, with a kink. In type 3, both turns are in the same direction, but lines 0--1 and 2--3 cross, giving a curve with a loop.

We can first categorise single cubic splines as one of three types, giving them a type string: ordinary ('' - the empty string), kinked ('K') and looped ('L').

However, example e is made of two smoothly joined cubic splines. To handle such sequences, we traverse them and create a string, appending a K for each kinked curve and an L for each looped curved. We also add a K for every join between two splines where the turn before the join is the opposite way from the turn after it: left then right, or right then left.

This gives us the type string 'K' for example e, matching it with d as desired.

We also allow a match where one type string is the reverse of the other: thus 'KL' matches 'LK'.

Answer 2

From the examples you provided I assume

• the size is not relevant
• shape can be distorted up to a point

if rotated curves are not the same

1. sample curves by N points

   • just step through parameter by some step ...
   • for cubic curve I would use from 16 to 32 sampled points
   • the more points the more precise comparison
   • but bigger runtimes ...

2. compute angle of each segment

   • use atan2 or atanxy
   • store these angles in array

3. compare these arrays

   • the best and easiest way to do this propperly is correlation coefficient
   • if correlation coefficient is near +1 then the shapes are similar or the same

If rotated similar curves should be resulted as same

1. rotations

   • then do the above for few rotations (for example for 0,10,20,...,350 degrees)
   • if any if these are the same stop and return true
   • if none then return false
   • rotation of curve is just add a constant to all its angles really ...

2. rotation invariance

   • if you offset both compared curve angles to start at angle 0
   • so just substract first angle from all angles of curve
   • then you align both curves to each other so just 2 positions to compare is needed
   • so you compare this
   • and if not the same add 180 degrees to one curve and compare again
   • that is sufficient

[Notes]

• you should normalize all angles before correlation (get it to interval <0.0,2.0*PI>)
• For more ideas look here How to compare two shapes?

Answer 3

Try X-Axis aligning your cubic curves first by working out a T(ranslation) matrix (-P0) P0 is the first control point of the curve. And a R(otation) matrix (the rotation angle needs to land the last control point P3 on the axis, you can work out the math).

Once the curves are axis-aligned, all you have to worry about is the meat of the curve (P1 & P2). You can compare them against the other curve's values, for a custom predefined error threshold, and see if the two curves match.