Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Appearance settings

Commit fef57d4

Browse filesBrowse 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 5beea73 commit fef57d4
Copy full SHA for fef57d4

File tree

Expand file treeCollapse file tree

1 file changed

+16
-26
lines changed
Filter options
Expand file treeCollapse file tree

1 file changed

+16
-26
lines changed

‎src/_path.h

Copy file name to clipboardExpand all lines: src/_path.h
+16-26Lines 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)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.