cannot snap intersection of two inscribed ellipses

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
10 messages Options
Reply | Threaded
Open this post in threaded view
|

cannot snap intersection of two inscribed ellipses

Tonyeltigresa
Hello all,

this seems to be a perennial problem, one which I feel may have a now forgotten solution.

I can't snap to the intersection of two inscribed ellipses. It's an intermittent problem, sometimes it works and sometimes it doesn't. For example I just went to make an example drawing to accompany this post and I could snap to the intersection of two inscribed ellipses in that drawing, but it does not work in the drawing I have linked below.

I don't know how to recreate the problem, but I've had it a few times since I started using LibreCAD.

Any help appreciated.

Link to an example .dxf file ->    https://drive.proton.me/urls/FH8GGYHE0G#mnGIFy2iXr3K

EDIT: so I've just opened the above drawing in LibreCAD running on top of Debian 12 and snap intersection works on the ellipses there, but it doesn't work on Windows 11. However, I have had this same problem in the past on Debian 12, so I don't know what specifically is different now I've tried on a different OS.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
This post was updated on .
Hi,

This is a major issue we would like to address, but technically, it's a quite difficult problem without using a topological layer.

In summary, we try to find tangent points as intersection. For example, given a circle and one line tangent to the circle. While it might be obvious to identify the tangent point as an intersection, CAD relies on solving the equations of the line and the circle to find common solutions.

When a line intersects with the circle, two solutions can be found, so intersections are found reliably.
When there's no intersection, no solution is found, and that's just  what is expected.
When they are tangential, the point is created when the solver should find exactly 1 solution. However, due to the topology of tangent curves, any small noise adding to the curves, they may become intersecting with at two points, or disconnected with a gap.

 Now, rerun the equation solver, the equations are still being solved, but as we do everything with floating points, with rounding errors,  i.e. noises. The system may find two solutions, one solution, or no solution at all. That's exactly the root cause of finding intersections appears to be random for the end user, as you observed. Without going into the details of equations, just imagine a circle and a tangent line of it, now, both the circle and the line have some uncertainty due to rounding errors, so  there are always some random noises added to both of them, in positions, radius, etc. then, you can pick 2 intersections, 1, or none.

Possible solutions:

1. Create a topology layer, so the system will remember coincidence and tangential relations;
2. actively find tangential points, and add them to intersections. We do have reliable ways to find tangent points, by using dual curves from projective geometry, so finding tangent lines becomes finding intersections for dual curves.

We do know what won't work, blindly increasing the precision level of equation solving. This is an issue at the conceptual level, not only at the implementation level.

Workaround: try to create tangent lines, and snap to end points instead of intersections.

Tonyeltigresa wrote
Hello all,

this seems to be a perennial problem, one which I feel may have a now forgotten solution.

I can't snap to the intersection of two inscribed ellipses. It's an intermittent problem, sometimes it works and sometimes it doesn't. For example I just went to make an example drawing to accompany this post and I could snap to the intersection of two inscribed ellipses in that drawing, but it does not work in the drawing I have linked below.

I don't know how to recreate the problem, but I've had it a few times since I started using LibreCAD.

Any help appreciated.

Link to an example .dxf file ->    https://drive.proton.me/urls/FH8GGYHE0G#mnGIFy2iXr3K

EDIT: so I've just opened the above drawing in LibreCAD running on top of Debian 12 and snap intersection works on the ellipses there, but it doesn't work on Windows 11. However, I have had this same problem in the past on Debian 12, so I don't know what specifically is different now I've tried on a different OS.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

Tonyeltigresa
In reply to this post by Tonyeltigresa
Thanks for the detailed reply!

I wont pretend to understand all of it, but I'm sure that at some point it will  be of use to someone who does.

I've no idea how typical my own requirements are, but I'd imagine the geometry I'm trying to draw is somewhat common. It would be great if snap to intersection worked reliably with inscribed ellipses because it's really the only bug I've encountered that has a material impact on the programs usability.

I'll try the workaround and report back.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
Adding the link to the original GitHub discussion

https://github.com/LibreCAD/LibreCAD/issues/523

Tonyeltigresa wrote
Thanks for the detailed reply!

I wont pretend to understand all of it, but I'm sure that at some point it will  be of use to someone who does.

I've no idea how typical my own requirements are, but I'd imagine the geometry I'm trying to draw is somewhat common. It would be great if snap to intersection worked reliably with inscribed ellipses because it's really the only bug I've encountered that has a material impact on the programs usability.

I'll try the workaround and report back.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
In reply to this post by Tonyeltigresa
I will quickly add fixes to 2.2.1:

1, if no intersection is found, check for tangent conditions;
2, since the tangent condition is not actually decidable with rounding errors, without a topology layer, we are going to allow false interactions, but avoid missing real tangent points.

Due to rounding errors, a tangent line of a circle may see random noises in position relative to the circle. We will accept tangent points whether 0, 1, 2 intersections are found. It means even if the line is actually 1e-6 from closest point on the circle, a tangent point will be identified. Depending on the tolerance level, we are going to report intersections from two close but not contacting curves.

The basic idea, it's acceptable to report a false interaction, but not acceptable to miss a real one.

If there's no objection, I will add this to 2.2.1 and quickly release 2.2.1 as the latest stable.

Tonyeltigresa wrote
Thanks for the detailed reply!

I wont pretend to understand all of it, but I'm sure that at some point it will  be of use to someone who does.

I've no idea how typical my own requirements are, but I'd imagine the geometry I'm trying to draw is somewhat common. It would be great if snap to intersection worked reliably with inscribed ellipses because it's really the only bug I've encountered that has a material impact on the programs usability.

I'll try the workaround and report back.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
in 2.2.1, added new algorithm to recover tangent points within tolerance(1e-5 of the curve length).

if two curves are found within this distance, the offset of one curve is used to locate the tangent point.

For example, if two tangent circles doesn't have an intersection, due to rounding errors. For the CAD engine, there's a gap of 1e-9 between them. Slighly increase the radius of the smaller circle by 2e-9, and the intersections can be now found using the enlarged circle and the other circle.

The algorithm uses bisection to find the optimum shape/position changes to locate a tangent point.

The clear drawback, if the two circles are actually separated by a gap of 1e-9, a tangent point will still be found, but it's less problematic, compared with failure in finding an actual tangent point.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
This post was updated on .
Added the same fix to 2.2.2_alpha, with support for cases with at least one curve is either a line, arc/circle, or an ellipse.

It means what are not supported:

If both curves are either a Hyperbola or a parabola. Since we don't have actual hyperbola support yet, the only tangent point failures are for those tangent points between two parabolas.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
Adding a fix for parabolas soon.

The parabola implementation is not as mature as other primitive geometries, so it takes longer.

Hyperbola support would be the next one to go. Feel free to help.

After hyperbola, support for splines should be a focus.

dxli wrote
Added the same fix to 2.2.2_alpha, with support for cases with at least one curve is either a line, arc/circle, or an ellipse.

It means what are not supported:

If both curves are either a Hyperbola or a parabola. Since we don't have actual hyperbola support yet, the only tangent point failures are for those tangent points between two parabolas.
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

Tonyeltigresa
I just wanted to say that although my non-existent knowledge of geometric algorithms means I can't engage on a technical level, I really appreciate you seeing to this for myself and the wider LibreCAD community
Reply | Threaded
Open this post in threaded view
|

Re: cannot snap intersection of two inscribed ellipses

dxli
Thanks a lot for your kindness.

Since the fix is in 2.2.2_alpha and 2.2.1_rc for all primitive types with the exception of splinepoints and splines.

Please help testing the feature, so we can finally resolve the GitHub issue #523.

The solution is not perfect, but should be good enough for end users. The solution is not truly on topology concepts, so it is also robust, because it doesn't suffer from potential topology layer troubles.


Tonyeltigresa wrote
I just wanted to say that although my non-existent knowledge of geometric algorithms means I can't engage on a technical level, I really appreciate you seeing to this for myself and the wider LibreCAD community