8000 API/MNT: re-arrange 0 length segment detection · matplotlib/matplotlib@ffaf302 · GitHub
[go: up one dir, main page]

Skip to content

Commit ffaf302

Browse files
committed
API/MNT: re-arrange 0 length segment detection
- move the "close to 0" computation from segments_intersect to path_intersects_path so we only do it once. - change the signature of the c function isclose to back the atol and rtol into the function (to make sure the two places we use it stay in sync)
1 parent 41fce6b commit ffaf302

File tree

1 file changed

+16
-26
lines changed

1 file changed

+16
-26
lines changed

src/_path.h

Lines changed: 16 additions & 26 deletions
Original file line numberDiff line numberDiff line change
@@ -814,8 +814,13 @@ int count_bboxes_overlapping_bbox(agg::rect_d &a, BBoxArray &bboxes)
814814
}
815815

816816

817-
inline bool isclose(double a, double b, double rtol, double atol)
817+
inline bool isclose(double a, double b)
818818
{
819+
// relative and absolute tolerance values are chosen empirically
820+
// it looks the atol value matters here bacause of round-off errors
821+
const double rtol = 1e-10;
822+
const double atol = 1e-13;
823+
819824
// as per python's math.isclose
820825
return fabs(a-b) <= fmax(rtol * fmax(fabs(a), fabs(b)), atol);
821826
}
@@ -830,33 +835,18 @@ inline bool segments_intersect(const double &x1,
830835
const double &x4,
831836
const double &y4)
832837
{
833-
// relative and absolute tolerance values are chosen empirically
834-
// it looks the atol value matters here bacause of round-off errors
835-
const double rtol = 1e-10;
836-
const double atol = 1e-13;
837-
838-
// if either segment is 0 length, they do not intersect
839-
// length-squared of each segment
840-
const double lensq_A = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
841-
const double lenqs_B = (x3 - x4) * (x3 - x4) + (y3 - y4) * (y3 - y4);
842-
843-
// one of the segments is 0 length
844-
if (isclose(lensq_A, 0, rtol, atol) || isclose(lenqs_B, 0, rtol, atol)) {
845-
return false;
846-
}
847-
848838
// determinant
849839
double den = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 - y1));
850840

851-
if (isclose(den, 0.0, rtol, atol)) { // collinear segments
841+
if (isclose(den, 0.0)) { // collinear segments
852842
if (x1 == x2 && x2 == x3) { // segments have infinite slope (vertical lines)
853843
// and lie on the same line
854844
return (fmin(y1, y2) <= fmin(y3, y4) && fmin(y3, y4) <= fmax(y1, y2)) ||
855845
(fmin(y3, y4) <= fmin(y1, y2) && fmin(y1, y2) <= fmax(y3, y4));
856846
}
857847
else {
858848
double intercept = (y1*x2 - y2*x1)*(x4 - x3) - (y3*x4 - y4*x3)*(x1 - x2);
859-
if (isclose(intercept, 0.0, rtol, atol)) { // segments lie on the same line
849+
if (isclose(intercept, 0.0)) { // segments lie on the same line
860850
return (fmin(x1, x2) <= fmin(x3, x4) && fmin(x3, x4) <= fmax(x1, x2)) ||
861851
(fmin(x3, x4) <= fmin(x1, x2) && fmin(x1, x2) <= fmax(x3, x4));
862852
}
@@ -871,10 +861,10 @@ inline bool segments_intersect(const double &x1,
871861
const double u1 = n1 / den;
872862
const double u2 = n2 / den;
873863

874-
return ((u1 > 0.0 || isclose(u1, 0.0, rtol, atol)) &&
875-
(u1 < 1.0 || isclose(u1, 1.0, rtol, atol)) &&
876-
(u2 > 0.0 || isclose(u2, 0.0, rtol, atol)) &&
877-
(u2 < 1.0 || isclose(u2, 1.0, rtol, atol)));
864+
return ((u1 > 0.0 || isclose(u1, 0.0)) &&
865+
(u1 < 1.0 || isclose(u1, 1.0)) &&
866+
(u2 > 0.0 || isclose(u2, 0.0)) &&
867+
(u2 < 1.0 || isclose(u2, 1.0)));
878868
}
879869

880870
template <class PathIterator1, class PathIterator2>
@@ -898,16 +888,16 @@ bool path_intersects_path(PathIterator1 &p1, PathIterator2 &p2)
898888

899889
c1.vertex(&x11, &y11);
900890
while (c1.vertex(&x12, &y12) != agg::path_cmd_stop) {
901-
// if the segment in path 1 is 0 length, skip to next vertex
902-
if ((x11 == x12) && (y11 == y12)) {
891+
// if the segment in path 1 is (almost) 0 length, skip to next vertex
892+
if ((isclose((x11 - x12) * (x11 - x12) + (y11 - y12) * (y11 - y12), 0))){
903893
continue;
904894
}
905895
c2.rewind(0);
906896
c2.vertex(&x21, &y21);
907897

908898
while (c2.vertex(&x22, &y22) != agg::path_cmd_stop) {
909-
// if the segment in path 2 is 0 length, skip to next vertex
910-
if ((x21 == x22) && (y21 == y22)) {
899+
// if the segment in path 2 is (almost) 0 length, skip to next vertex
900+
if ((isclose((x21 - x22) * (x21 - x22) + (y21 - y22) * (y21 - y22), 0))){
911901
continue;
912902
}
913903
if (segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22)) {

0 commit comments

Comments
 (0)
0