I have high order Bézier curve (n > 5). I would like to detect points of self intersection or too pointy ones. In lower degrees, I could use derivative of curve equation and solve roots for valeu = 0, but in higher dimensions, that would take too long.
Is there any other way? I am not looking for precise solution, just a closest possible. I dont even need the point value itself, just detection.
I was thinking of converting curve to lines and check angle, but that is not very accurate and can miss points if I choose lines too big (miss intresection) or too small (miss cusp via angle criteria)
Best Answer
For self-intersecting, you can refine Bezier curve's control polygon (by knot insertion) to a level that the sum of control polygon length converges (i.e., does not change within a certain tolerance) then use the control polygon to check if the curve self-intersect. This is better than sampling points on the curve and using line segments from these sampled points to check for self-intersection.
You can also use control polygon to detect cusps. Try to do degree elevation of the Bezier curve and the control points will start to form a loop around where the cusp is. The only problem with this approach is that the control polygon converges slowly with degree elevation.
The following pictures show an example of using degree elevation to narrow down the cusp. The first picture shows a degree 3 Bezier curve with a cusp at t=0.5. The 2nd and the 3rd picture show the result with degree being elevated to 7 and 15 respectively. As we can see that the control points start to loop around the cusp.