[intersection] \pgfintersectionofpaths yields an error when the lines are almost parallel

[pgf-tikz-bot]

Migrated from SourceForge
Author: avani42
Timestamp: 2015-10-22 18:47:05.333000

\pgfintersectionofpaths yields an error when the lines it is trying to intersect are almost parallel. This bug was discovered by users of package forest and attributed to PGF, see TeX.SE question http://tex.stackexchange.com/questions/204094/sn-edges-and-nice-empty-nodes-styles-in-forest-lead-to-dividing-by-zero-whats.

This is an example of code that produces the error.

\pgfintersectionofpaths{%
  \pgfpathmoveto{\pgfpoint{0.0pt}{-3.53297pt}}
  \pgfpathlineto{\pgfpoint{19.54204pt}{-31.44316pt}}%
}{%
  \pgfpathmoveto{\pgfpoint{34.6372pt}{-53.00208pt}}%
  \pgfpathlineto{\pgfpoint{19.54204pt}{-31.44316pt}}}

The error produced is

! Package PGF Math Error: You asked me to calculate 1/0.0', but I cannot divide any number by zero.

The "call stack" is (\pgfintersectionofpaths, \pgfpointintersectionoflines, \pgftransforminvert): so the error occurs during \pgftransforminvert, just as the documentation of this macro claims would happen if the matrix its trying to invert is near-singular.

Prior to calling \pgfpointintersectionoflines to actually compute the intesection of lines, \pgf@intersectionoflines (indirectly called by \pgfintersectionofpaths) tries to figure out whether the lines intersect at all, and the problem seems to be in this part of the code, namely macro \pgf@iflinesintersect, which apparently reports the lines to intersect, although computing the intersection later yields an error.

The expected behaviour would be for \pgfpointintersectionoflines and \pgfiflinesintersect to be consistent.

[pgf-tikz-bot]

Migrated from SourceForge
Author: mo-gul
Timestamp: 2018-12-21 22:47:39.689000

• summary: \pgfintersectionofpaths yields an error when the lines are almost parallel --> [intersection] \pgfintersectionofpaths yields an error when the lines are almost parallel
• Description has changed:

Diff:

--- old
+++ new
@@ -10,7 +10,11 @@
   \pgfpathlineto{\pgfpoint{19.54204pt}{-31.44316pt}}}

-The error produced is ! Package PGF Math Error: You asked me to calculate 1/0.0', but I cannot divide any number by zero.. The "call stack" is (\pgfintersectionofpaths, \pgfpointintersectionoflines, \pgftransforminvert): so the error occurs during \pgftransforminvert, just as the documentation of this macro claims would happen if the matrix its trying to invert is near-singular.
+The error produced is
+
+> ! Package PGF Math Error: You asked me to calculate 1/0.0', but I cannot divide any number by zero.
+
+The "call stack" is (\pgfintersectionofpaths, \pgfpointintersectionoflines, \pgftransforminvert): so the error occurs during \pgftransforminvert, just as the documentation of this macro claims would happen if the matrix its trying to invert is near-singular.

Prior to calling \pgfpointintersectionoflines to actually compute the intesection of lines, \pgf@intersectionoflines (indirectly called by \pgfintersectionofpaths) tries to figure out whether the lines intersect at all, and the problem seems to be in this part of the code, namely macro \pgf@iflinesintersect, which apparently reports the lines to intersect, although computing the intersection later yields an error.

[schar]

Has any progress been made on this issue?

[sasozivanovic]

There is a new situation triggering the bug, see this answer on TeX.SE. I believe the bug is triggered due to the increased accuracy of \pgfpointnormalised introduced in this commit.

[hmenke]

Thanks Sašo for investigating. Can you suggest a fix?

[sasozivanovic]

Confirmed, there are still some false positives. The lines below intersect at (7533.0596514639865, -18161.393051431558), which is out of TeX's range, so it should be reported as non-intersecting.

\pgfintersectionofpaths{%
  \pgfpathmoveto{\pgfpoint{0.0pt}{3.22221pt}}
  \pgfpathlineto{\pgfpoint{12.31886pt}{-26.4825pt}}%
}{%
  \pgfpathmoveto{\pgfpoint{8.98589pt}{3.22221pt}}%
  \pgfpathlineto{\pgfpoint{6.35397pt}{9.57619pt}}}

[sasozivanovic]

I looked at the code of \pgf@iflinesintersect just now, and in fact it had been recently (May 31) rewritten (commit 55d882f). Even though this bug wasn't closed, the example in my original bug report is now ok!

I'll investigate the new situation further to see if I was correct in thinking that the dimension too large occurs while computing the intersections.

[sasozivanovic]

In fact, I have a suggestion for a fix!

I have identified the points in \pgf@iflinesintersect@ where the DTL error occurs. If FPU is used there instead of TeX's math, the macro correctly reports whether the lines intersect.

I'm attaching the patch, but I believe it shouldn't be used as it is, as don't really know how to use FPU, so the code is clumsy.

[hmenke]

Thank you for the patch, but we can't use the FPU here, because it comes with a critical performance hit.

[sasozivanovic]

You're right, of course. The FPU-based patch increased the execution time by 4%, and I have noticed that it didn't address even half of the problematic points. The new fix incurs about 1.5% overhead. I've tested it extensively: the errors are gone, and the results match what Python computes (within the bounds of of TeX's precision) -- one can even use dimensions all the way up to \maxdimen, as long as no segment is longer than that.

The solution is simply to divide the given dimensions by 128 (128*128=\maxdimen) for multiplication tests, and by 2 for addition tests.

[sasozivanovic]

Incidentally, there's a pool size error when testing with a million intersections, but I'm guessing it is not produced by my code ... at least I don't see how it could be. The thing is, the error was impossible to reach in the version which overflowed, as a hundred dimension too large errors were reached very soon.