2D cubic Bezier curve. Point of self-intersection

Question

I have a 2D cubic Bézier curve defined by a set of control points A, B, D and C. How can I find a point of self-intersection P (two parameter values t)?

---

Answer 1

I solved this problem years ago and the relevant code is still in my Kinross repository.

Represent the cubic Bézier curve in the power basis: $$(x(t),y(t))=(x_3t^3+x_2t^2+x_1t+x_0,y_3t^3+y_2t^2+y_1t+y_0)$$ Let the self-intersection parameters be $\lambda$ and $\mu$, then obviously $x(\lambda)-x(\mu)=y(\lambda)-y(\mu)=0$. Expanding, then dividing by $\lambda-\mu$ (the trivial solution), gives $$x_3(\lambda^2+\lambda\mu+\mu^2)+x_2(\lambda+\mu)=-x_1\\ y_3(\lambda^2+\lambda\mu+\mu^2)+y_2(\lambda+\mu)=-y_1$$ Now solve this linear system for $\lambda^2+\lambda\mu+\mu^2$ and $\lambda+\mu$ and obtain $$\lambda\mu=(\lambda+\mu)^2-(\lambda^2+\lambda\mu+\mu^2)$$ Finally, by Viète's formulas, $\lambda$ and $\mu$ are the roots of $t^2-(\lambda+\mu)t+\lambda\mu$. Either may be outside $[0,1]$, indicating a self-intersection outside the curve proper, or both may be complex, indicating no self-intersection even in the extended curve.

---

My implementation of the above algorithm in Kinross first makes an affine transformation mapping $A,B,C$ to $(0,0),(0,1),(1,1)$ respectively. Because Bézier curves are equivariant under affine transformations of their control points, the parameters of self-intersection do not change. After transforming, $D$ is at $(x,y)$ and $$\lambda+\mu=\frac{x-3}{x+y-3}$$ $$\lambda\mu=(\lambda+\mu)^2+\frac3{x+y-3}$$