circle percision, points of tangency and intersection detection

[ravas]

I've been helping the open source 2D CAD project LibreCAD with some bug hunting; and found that the snap mode for intersections finds two intersections extremely close together instead of one point of tangency (regarding an incircle of a triangle).

The developer working on it has said:
"""
It's not a problem of detecting intersections.

the problem is that inscribed circle is generated correct up to relative precision of 1e-8, while the tangential points are test at a precision level of 1e-10. Therefore, the inscribed circle actually intersects with one line.

The reasonable way is to improve the equation solver to get the inscribed circle more accurate.
"""

and after some more investigation:

"""
the tolerance itself is always there, even if we can solve equations at higher precision:

currently, we can generate the tangential circle correct up to 10^-8, but intersection detection is up to 10^-10, causing a tangential point (by the definition of tangential circle) to be detected as intersection points.

because the actual precision is up to the floating point, there's no clear answer close to precision level.

One clear hint, if user specifies to draw with precision 10^-4(as in Current Drawing Preferences), there's no need to report two points 10^-8 apart.

Lots of work need to implement this idea;
"""

I'm wondering if anyone has any thoughts on this issue.

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

[Victor Bazarov]

On 5/11/2015 4:37 AM, ravas wrote:
> I've been helping the open source 2D CAD project LibreCAD with some
bug hunting; and found that the snap mode for intersections finds two
intersections extremely close together instead of one point of tangency
(regarding an incircle of a triangle).
>

[...]

>
> I'm wondering if anyone has any thoughts on this issue.

Immediate thought: How is that a C++ language issue?

Second thought: isn't there a discussion part to any open source
project? Post there.

Third thought: instead of creating a stand-alone point, model a point
that is "a point of tangency" with entities stored in it. Use
polymorphism to provide snapping behavior.

Fourth thought: (engineering solution) if you find two points (of
intersection) instead of the needed single one, find the average of the
two and use it.

V
--
I do not respond to top-posted replies, please don't ask

[Öö Tiib]

On Monday, 11 May 2015 11:38:00 UTC+3, ravas wrote:
> I've been helping the open source 2D CAD project LibreCAD with some
> bug hunting; and found that the snap mode for intersections finds two
> intersections extremely close together instead of one point of tangency
> (regarding an incircle of a triangle).

Any issues with floating points and accuracy of calculations are general
in computer science, not C++ specific. Perhaps that good old David
Goldberg's paper discusses it most nicely:
http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html

Wherever we use floating point calculations we have to take these
issues into account and deal with those or we inevitably receive some
nuisances like you describe later.

[Chris M. Thomasson]

> "ravas" wrote in message
> news:cfb1144c-b652-4162...@googlegroups.com...

> I've been helping the open source 2D CAD project LibreCAD with some bug
> hunting; and found that the snap mode for intersections finds two
> intersections extremely close together instead of one point of tangency
> (regarding an incircle of a triangle).

> [...]

FIWIW, you can get tangent circles if you move them together just right.
I have a method of finding circle intersections briefly described here:

http://webpages.charter.net/appcore/fractal/ttr/circle_isect/circle_isect_draft.pdf

I created a quick and dirty online app that can find tangencies:

http://webpages.charter.net/appcore/fractal/ttr/circle_isect

You can get it to display tangent by using these simple settings:
_________________________________
c0_x = 200
c0_y = 100
c0_r = 50

c1_x = 300
c1_y = 100
c1_r = 50
_________________________________


I have found many other tangents for different sized circles in different
positions
just by softly moving the circles closer to each other. I cannot remember
the settings,
but I will try again and give them to you.

Sorry if this is off base for your needs...

;^o

[Chris M. Thomasson]

> "Chris M. Thomasson" wrote in message
> news:mir3cq$1m8$1...@speranza.aioe.org...

> > "ravas" wrote in message
> > news:cfb1144c-b652-4162...@googlegroups.com...

> > I've been helping the open source 2D CAD project LibreCAD with some bug
> > hunting; and found that the snap mode for intersections finds two
> > intersections extremely close together instead of one point of tangency
> > (regarding an incircle of a triangle).

[...]

> I have found many other tangents for different sized circles in different
> positions just by softly moving the circles closer to each other. I cannot
> remember the settings, but I will try again and give them to you.

FWIW, try these settings:

_______________________________
c0_x = 200
c0_y = 100

c0_r = 90

c1_x = 270
c1_y = 120
c1_r = 162.80109889280520001
_______________________________

in the online program:

http://webpages.charter.net/appcore/fractal/ttr/circle_isect/

I happen to get a result of:

The circles c0 and c1 are tangent.

;^)

[ravas]

Thanks everyone!