From: Giovanni Mascellani Subject: Re: [PATCH 4/4] d2d1: Implement cubic bezier-line intersection. Message-Id: Date: Wed, 1 Apr 2020 18:04:24 +0200 In-Reply-To: <20200331201103.15219-4-conmanx360@gmail.com> References: <20200331201103.15219-1-conmanx360@gmail.com> <20200331201103.15219-4-conmanx360@gmail.com> Hi, Il 31/03/20 22:11, Connor McAdams ha scritto: > + p = (3.0f * b - a * a) / 3.0f; > + p_3 = p / 3.0f; > + q = (2.0f * a * a * a - 9.0f * a * b + 27.0f * c) / 27.0f; > + q2 = q / 2.0f; > + disc = q2 * q2 + p_3 * p_3 * p_3; I don't think it is advisable to use Cardano's formula to solve a cubic, because it can go numerically bad in a lot of ways. After a quick chat with a friend into numerical computing, it seems that it is probably better to do a few iterations of a numerical method, like the Aberth method (see the Wikipedia page), which should converge rather quickly and more or less always if the initial values are chosen not to be symmetrical around the real axis. However, it requires to use complex numbers. A good criterion for halting the iterative search is when abs(p/p') is smaller than epsilon, because that condition implies that a root is in a neighbourhood of size approximately epsilon. HTH, Giovanni. -- Giovanni Mascellani Postdoc researcher - Université Libre de Bruxelles -----BEGIN PGP SIGNATURE----- iHUEARYKAB0WIQSiBF6hBvCQNcghJEaNr8EMz954SQUCXoS7iAAKCRCNr8EMz954 Sd0IAQDlgosAxjyL29tKSSSBf64Gwk4aVbxrJNAItkcSvn2pEQEA9UbjD0k5KLou KxgZ3h6KAzM6zZ+azxeIel0A30Hg5Q4= =ntFj -----END PGP SIGNATURE-----