Movatterモバイル変換

[0]ホーム
URL:

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

 Sign up
Appearance settings

Commitff04b25

Browse files
jklymaktacaswell
authored andcommitted
Backport PR#16250: Fix zerolen intersect
Merge pull request#16250 from tacaswell/fix_zerolen_intersectFix zerolen intersectAlso re-factors some tests.Conflicts:lib/matplotlib/tests/test_path.py - unrelated change to test above new test. Kept old version of test and added new test
1 parentd10aacf commitff04b25

File tree

2 files changed

+121
-71
lines changed

2 files changed

+121
-71
lines changed

‎lib/matplotlib/tests/test_path.py

Lines changed: 95 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -273,81 +273,78 @@ def test_path_deepcopy():
273273
copy.deepcopy(path2)
274274

275275

276-
deftest_path_intersect_path():
276+
@pytest.mark.parametrize('phi',np.concatenate([
277+
np.array([0,15,30,45,60,75,90,105,120,135])+delta
278+
fordeltain [-1,0,1]]))
279+
deftest_path_intersect_path(phi):
277280
# test for the range of intersection angles
278-
base_angles=np.array([0,15,30,45,60,75,90,105,120,135])
279-
angles=np.concatenate([base_angles,base_angles+1,base_angles-1])
280281
eps_array= [1e-5,1e-8,1e-10,1e-12]
281282

282-
forphiinangles:
283+
transform=transforms.Affine2D().rotate(np.deg2rad(phi))
283284

284-
transform=transforms.Affine2D().rotate(np.deg2rad(phi))
285+
# a and b intersect at angle phi
286+
a=Path([(-2,0), (2,0)])
287+
b=transform.transform_path(a)
288+
asserta.intersects_path(b)andb.intersects_path(a)
285289

286-
# a and bintersect at angle phi
287-
a=Path([(-2,0), (2,0)])
288-
b=transform.transform_path(a)
289-
asserta.intersects_path(b)andb.intersects_path(a)
290+
# a and btouch at angle phi at (0, 0)
291+
a=Path([(0,0), (2,0)])
292+
b=transform.transform_path(a)
293+
asserta.intersects_path(b)andb.intersects_path(a)
290294

291-
# a and btouch at angle phi at (0,0)
292-
a=Path([(0,0), (2,0)])
293-
b=transform.transform_path(a)
294-
asserta.intersects_path(b)andb.intersects_path(a)
295+
# a and bare orthogonal and intersect at (0,3)
296+
a=transform.transform_path(Path([(0,1), (0,3)]))
297+
b=transform.transform_path(Path([(1,3), (0,3)]))
298+
asserta.intersects_path(b)andb.intersects_path(a)
295299

296-
# a and b areorthogonal and intersect at (0, 3)
297-
a=transform.transform_path(Path([(0,1), (0,3)]))
298-
b=transform.transform_path(Path([(1,3), (0,3)]))
299-
asserta.intersects_path(b)andb.intersects_path(a)
300+
# a and b arecollinear and intersect at (0, 3)
301+
a=transform.transform_path(Path([(0,1), (0,3)]))
302+
b=transform.transform_path(Path([(0,5), (0,3)]))
303+
asserta.intersects_path(b)andb.intersects_path(a)
300304

301-
# a and b are collinear and intersect at (0, 3)
302-
a=transform.transform_path(Path([(0,1), (0,3)]))
303-
b=transform.transform_path(Path([(0,5), (0,3)]))
304-
asserta.intersects_path(b)andb.intersects_path(a)
305+
# self-intersect
306+
asserta.intersects_path(a)
305307

306-
# self-intersect
307-
asserta.intersects_path(a)
308+
# a contains b
309+
a=transform.transform_path(Path([(0,0), (5,5)]))
310+
b=transform.transform_path(Path([(1,1), (3,3)]))
311+
asserta.intersects_path(b)andb.intersects_path(a)
308312

309-
# a contains b
310-
a=transform.transform_path(Path([(0,0), (5,5)]))
311-
b=transform.transform_path(Path([(1,1), (3,3)]))
312-
asserta.intersects_path(b)andb.intersects_path(a)
313+
# a and b are collinear but do not intersect
314+
a=transform.transform_path(Path([(0,1), (0,5)]))
315+
b=transform.transform_path(Path([(3,0), (3,3)]))
316+
assertnota.intersects_path(b)andnotb.intersects_path(a)
317+
318+
# a and b are on the same line but do not intersect
319+
a=transform.transform_path(Path([(0,1), (0,5)]))
320+
b=transform.transform_path(Path([(0,6), (0,7)]))
321+
assertnota.intersects_path(b)andnotb.intersects_path(a)
322+
323+
# Note: 1e-13 is the absolute tolerance error used for
324+
# `isclose` function from src/_path.h
313325

314-
# a and b are collinear but do not intersect
326+
# a and b are parallel but do not touch
327+
forepsineps_array:
315328
a=transform.transform_path(Path([(0,1), (0,5)]))
316-
b=transform.transform_path(Path([(3,0), (3,3)]))
329+
b=transform.transform_path(Path([(0+eps,1), (0+eps,5)]))
317330
assertnota.intersects_path(b)andnotb.intersects_path(a)
318331

319-
# a and b are on the same line but do not intersect
332+
# a and b are on the same line but do not intersect (really close)
333+
forepsineps_array:
320334
a=transform.transform_path(Path([(0,1), (0,5)]))
321-
b=transform.transform_path(Path([(0,6), (0,7)]))
335+
b=transform.transform_path(Path([(0,5+eps), (0,7)]))
322336
assertnota.intersects_path(b)andnotb.intersects_path(a)
323337

324-
# Note: 1e-13 is the absolute tolerance error used for
325-
# `isclose` function from src/_path.h
326-
327-
# a and b are parallel but do not touch
328-
forepsineps_array:
329-
a=transform.transform_path(Path([(0,1), (0,5)]))
330-
b=transform.transform_path(Path([(0+eps,1), (0+eps,5)]))
331-
assertnota.intersects_path(b)andnotb.intersects_path(a)
332-
333-
# a and b are on the same line but do not intersect (really close)
334-
forepsineps_array:
335-
a=transform.transform_path(Path([(0,1), (0,5)]))
336-
b=transform.transform_path(Path([(0,5+eps), (0,7)]))
337-
assertnota.intersects_path(b)andnotb.intersects_path(a)
338-
339-
# a and b are on the same line and intersect (really close)
340-
forepsineps_array:
341-
a=transform.transform_path(Path([(0,1), (0,5)]))
342-
b=transform.transform_path(Path([(0,5-eps), (0,7)]))
343-
asserta.intersects_path(b)andb.intersects_path(a)
344-
345-
# b is the same as a but with an extra point
338+
# a and b are on the same line and intersect (really close)
339+
forepsineps_array:
346340
a=transform.transform_path(Path([(0,1), (0,5)]))
347-
b=transform.transform_path(Path([(0,1), (0,2), (0,5)]))
341+
b=transform.transform_path(Path([(0,5-eps), (0,7)]))
348342
asserta.intersects_path(b)andb.intersects_path(a)
349343

350-
return
344+
# b is the same as a but with an extra point
345+
a=transform.transform_path(Path([(0,1), (0,5)]))
346+
b=transform.transform_path(Path([(0,1), (0,2), (0,5)]))
347+
asserta.intersects_path(b)andb.intersects_path(a)
351348

352349

353350
@pytest.mark.parametrize('offset',range(-720,361,45))
@@ -360,3 +357,46 @@ def test_full_arc(offset):
360357
maxs=np.max(path.vertices,axis=0)
361358
np.testing.assert_allclose(mins,-1)
362359
assertnp.allclose(maxs,1)
360+
361+
362+
deftest_disjoint_zero_length_segment():
363+
this_path=Path(
364+
np.array([
365+
[824.85064295,2056.26489203],
366+
[861.69033931,2041.00539016],
367+
[868.57864109,2057.63522175],
368+
[831.73894473,2072.89472361],
369+
[824.85064295,2056.26489203]]),
370+
np.array([1,2,2,2,79],dtype=Path.code_type))
371+
372+
outline_path=Path(
373+
np.array([
374+
[859.91051028,2165.38461538],
375+
[859.06772495,2149.30331334],
376+
[859.06772495,2181.46591743],
377+
[859.91051028,2165.38461538],
378+
[859.91051028,2165.38461538]]),
379+
np.array([1,2,2,2,2],
380+
dtype=Path.code_type))
381+
382+
assertnotoutline_path.intersects_path(this_path)
383+
assertnotthis_path.intersects_path(outline_path)
384+
385+
386+
deftest_intersect_zero_length_segment():
387+
this_path=Path(
388+
np.array([
389+
[0,0],
390+
[1,1],
391+
]))
392+
393+
outline_path=Path(
394+
np.array([
395+
[1,0],
396+
[.5,.5],
397+
[.5,.5],
398+
[0,1],
399+
]))
400+
401+
assertoutline_path.intersects_path(this_path)
402+
assertthis_path.intersects_path(outline_path)

‎src/_path.h

Lines changed: 26 additions & 16 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-
inlineboolisclose(double a,double b,double rtol,double atol)
817+
inlineboolisclose(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+
constdouble rtol =1e-10;
822+
constdoubleatol =1e-13;
823+
819824
// as per python's math.isclose
820825
returnfabs(a-b) <=fmax(rtol *fmax(fabs(a),fabs(b)),atol);
821826
}
@@ -830,40 +835,36 @@ inline bool segments_intersect(const double &x1,
830835
constdouble &x4,
831836
constdouble &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-
constdouble rtol =1e-10;
836-
constdoubleatol =1e-13;
837838
// determinant
838839
double den = ((y4 - y3) * (x2 - x1)) - ((x4 - x3) * (y2 -y1));
839840

840-
if (isclose(den,0.0, rtol,atol)) {// collinear segments
841+
if (isclose(den,0.0)) {// collinear segments
841842
if (x1 == x2 && x2 == x3) {// segments have infinite slope (vertical lines)
842843
// and lie on the same line
843844
return (fmin(y1, y2) <=fmin(y3, y4) &&fmin(y3, y4) <=fmax(y1, y2)) ||
844845
(fmin(y3, y4) <=fmin(y1, y2) &&fmin(y1, y2) <=fmax(y3, y4));
845846
}
846847
else {
847848
double intercept = (y1*x2 - y2*x1)*(x4 - x3) - (y3*x4 - y4*x3)*(x1 - x2);
848-
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
849850
return (fmin(x1, x2) <=fmin(x3, x4) &&fmin(x3, x4) <=fmax(x1, x2)) ||
850851
(fmin(x3, x4) <=fmin(x1, x2) &&fmin(x1, x2) <=fmax(x3, x4));
851852
}
852853
}
853-
854+
854855
returnfalse;
855856
}
856857

857-
double n1 = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
858-
double n2 = ((x2 - x1) * (y1 - y3)) - ((y2 -y1) * (x1 - x3));
858+
constdouble n1 = ((x4 - x3) * (y1 - y3)) - ((y4 - y3) * (x1 - x3));
859+
constdouble n2 = ((x2 - x1) * (y1 - y3)) - ((y2 -y1) * (x1 - x3));
859860

860-
double u1 = n1 / den;
861-
double u2 = n2 / den;
861+
constdouble u1 = n1 / den;
862+
constdouble u2 = n2 / den;
862863

863-
return ((u1 >0.0 ||isclose(u1,0.0, rtol,atol)) &&
864-
(u1 <1.0 ||isclose(u1,1.0, rtol,atol)) &&
865-
(u2 >0.0 ||isclose(u2,0.0, rtol,atol)) &&
866-
(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)));
867868
}
868869

869870
template<classPathIterator1,classPathIterator2>
@@ -887,9 +888,18 @@ bool path_intersects_path(PathIterator1 &p1, PathIterator2 &p2)
887888

888889
c1.vertex(&x11, &y11);
889890
while (c1.vertex(&x12, &y12) != agg::path_cmd_stop) {
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))){
893+
continue;
894+
}
890895
c2.rewind(0);
891896
c2.vertex(&x21, &y21);
897+
892898
while (c2.vertex(&x22, &y22) != agg::path_cmd_stop) {
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))){
901+
continue;
902+
}
893903
if (segments_intersect(x11, y11, x12, y12, x21, y21, x22, y22)) {
894904
returntrue;
895905
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp