{"action":"opened","issue":{"url":"https://api.github.com/repos/behdad/fonttools/issues/617","repository_url":"https://api.github.com/repos/behdad/fonttools","labels_url":"https://api.github.com/repos/behdad/fonttools/issues/617/labels{/name}","comments_url":"https://api.github.com/repos/behdad/fonttools/issues/617/comments","events_url":"https://api.github.com/repos/behdad/fonttools/issues/617/events","html_url":"https://github.com/behdad/fonttools/issues/617","id":158872753,"number":617,"title":"solveCubic needs fixes (or perhaps its algorithm replaced)","user":{"login":"miguelsousa","id":2119742,"avatar_url":"https://avatars.githubusercontent.com/u/2119742?v=3","gravatar_id":"","url":"https://api.github.com/users/miguelsousa","html_url":"https://github.com/miguelsousa","followers_url":"https://api.github.com/users/miguelsousa/followers","following_url":"https://api.github.com/users/miguelsousa/following{/other_user}","gists_url":"https://api.github.com/users/miguelsousa/gists{/gist_id}","starred_url":"https://api.github.com/users/miguelsousa/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/miguelsousa/subscriptions","organizations_url":"https://api.github.com/users/miguelsousa/orgs","repos_url":"https://api.github.com/users/miguelsousa/repos","events_url":"https://api.github.com/users/miguelsousa/events{/privacy}","received_events_url":"https://api.github.com/users/miguelsousa/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":0,"created_at":"2016-06-07T09:00:58Z","updated_at":"2016-06-07T09:00:58Z","closed_at":null,"body":"I've been investigating why Robofab's [correctDirection](https://github.com/robofab-developers/robofab/blob/673acdc829b85af6393b64d79e89fb63ae13d312/Lib/robofab/objects/objectsBase.py#L1552) fails to correctly set the direction of some contours, and I think I found one possible cause: the method uses FontTools' [PointInsidePen](https://github.com/behdad/fonttools/blob/c3056bcae52087efadbd976b1d793c8a90fc35ad/Lib/fontTools/pens/pointInsidePen.py#L20) which in turn relies on [solveCubic](https://github.com/behdad/fonttools/blob/c3056bcae52087efadbd976b1d793c8a90fc35ad/Lib/fontTools/misc/bezierTools.py#L289). What I found in my exploration is that in some cases `solveCubic` does not return the correct list roots. Observe these two examples:\r\n```python\r\nfrom fontTools.misc.bezierTools import solveCubic\r\nprint solveCubic(-10.0, -9.0, 48.0, -29.0)     #1\r\nprint solveCubic(-9.875, -9.0, 47.625, -28.75) #2\r\n```\r\n**Equation 1: `-10x³ - 9x² + 48x - 29 = 0`**\r\n[This equation has two solutions](http://www.wolframalpha.com/input/?i=solve+-10.0*x**3+-+9.0*x**2+%2B+48*x+-+29+%3D+0), `x = 1` and `x = -29 / 10`.\r\nThe output of `solveCubic` is ```[-2.9, 0.9999999999999993, 1.000000000000001]```.\r\n\r\n**Equation 2: `-9.875x³ - 9x² + 47.625x - 28.75 = 0`**\r\n[This equation also has two solutions](http://www.wolframalpha.com/input/?i=solve+-9.875*x**3+-+9.0*x**2+%2B+47.625*x+-+28.75+%3D+0), `x = 1` and `x = -230 / 79`.\r\nThe output of `solveCubic` is ```[-2.911392405063291]```.\r\n\r\nWhile the rounding error in the results of the first equation is expected, the missing solution(s) in the output of the second equation is a real problem.\r\n\r\nThere are several [methods for solving cubic functions](https://en.wikipedia.org/wiki/Cubic_function). I've experimented with the method detailed [on this page](http://www.1728.org/cubic2.htm). It yielded several more correct path directions, but wasn't the silver bullet I was hoping for. Perhaps it's still not the best algorithm, or there are possibly other bugs in the code path chain.\r\n\r\nIt'd be great if you guys could have a look at this. Thanks!"}}
{"actor":{"display_login":"miguelsousa"}}