New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Use root finder to solve ellipse/ellipse intersections #116

Open
AndrewMartchenko opened this Issue Dec 1, 2016 · 7 comments

Comments

Projects
None yet
3 participants
@AndrewMartchenko
Copy link

AndrewMartchenko commented Dec 1, 2016

I found a bug in the arc intersect function. The bug occurs when you try to find the intersects of two arcs with one of the arcs inside the other and they are touching at one point. Basically you get different results depending how the intersect function is called. For example, calling

a = arc1:intersect(arc2)

will give you a different result compared to

b = arc2:intersect(arc1)

One of the tables of intersects will have some additional points in it, which are not intersection points of the two ellipses.
I have attached a test.lua ipelet and a test.ipe file to reproduce the results. All you have to do is load the test.ipe file and run the "Intersect Test" ipelet.

Happy debugging.

Andrew M.

arc_bug.zip

@otfried otfried self-assigned this Dec 9, 2016

@otfried

This comment has been minimized.

Copy link
Owner

otfried commented Dec 9, 2016

Intersecting ellipses isn't straightforward. The current code was contributed a few years ago, it simply subdivides the ellipses and uses a straight approximation to find intersections. This makes this kind of effect unavoidable.

I would either have to implement special code to handle the case of circles, or use a real root solver...

@otfried

This comment has been minimized.

Copy link
Owner

otfried commented Dec 9, 2016

See also #32.

@AndrewMartchenko

This comment has been minimized.

Copy link

AndrewMartchenko commented Dec 14, 2016

Hi Otfried,
I had a go at solving this problem in Octave and I think I did it. I tried to translate the code to Lua, however I had problems importing a complex number package. For some reason I am unable to include lua files using require, loadfile or dofile. Perhaps there is a better way to implement the quartic_roots function to avoid complex number, but I could not figure it out.
I have attached my (rather nasty) solution in case you are interested. Note that the program finds the intersect of an ellipse and a unit circle.
ellipse_intersect.m.zip

@AndrewMartchenko

This comment has been minimized.

Copy link

AndrewMartchenko commented Dec 14, 2016

I've been doing a bit of reading on solving for the roots to quartic functions and it looks like the approach that I've taken in my intersection code may be numerically unstable. I think a root finder will be safer.

@otfried

This comment has been minimized.

Copy link
Owner

otfried commented Dec 14, 2016

In any case, Lua isn't good enough to replace the current intersection code - it's in the C++ library that implements the basic Ipe objects, and needs to be fast enough to support snapping to intersection points. This is done entirely in C++.

@AndrewMartchenko

This comment has been minimized.

Copy link

AndrewMartchenko commented Dec 15, 2016

I agree that the intersection code should be implemented in C++, however, I am a noobe when it comes to contributing to IPE, so I will stick to lua ipelets for now . In any case, I've been doing a bit more reading (Numerical Recipes) and decided to implement a Newton-Raphson root finder ipelet to solve for the roots of the quartic involved in the ellipse intersection code. The attached code works very well. It is much cleaner than the closed form solution, converges at a quadratic rate and is guaranteed to converge to the real roots.
ellipse_intersect.lua.zip

@CzarnyPijar

This comment has been minimized.

Copy link

CzarnyPijar commented Dec 18, 2016

I'm not going to write C++ code, but maybe this interactive demo (html+JavaScript) will inspire someone to do such a thing.
bezier_intersect.zip
.

@otfried otfried changed the title Bug in the Arc intersect function Use root finder to solve ellipse/ellipse intersections Jan 6, 2019

@otfried otfried added the enhancement label Jan 6, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment