Skip to content

Commit bc77b48

Browse files
barendgehrelsbarendgehrels
authored
Merge pull request boostorg#773 from barendgehrels/fix/fraction-by-arrival
Fix turns where segments arrive at an intersection point, or leave
2 parents 632d1fc + 42bd7cf commit bc77b48

File tree

8 files changed

+70
-30
lines changed

8 files changed

+70
-30
lines changed

‎include/boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -28,6 +28,7 @@ inline char method_char(detail::overlay::method_type const& method)
2828
case method_touch_interior : return 'm';
2929
case method_collinear : return 'c';
3030
case method_equal : return 'e';
31+
case method_start : return 's';
3132
case method_error : return '!';
3233
default : return '?';
3334
}

‎include/boost/geometry/algorithms/detail/overlay/get_turn_info.hpp

Lines changed: 43 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -179,6 +179,39 @@ struct base_turn_handler
179179
ti.operations[1].fraction = info.fractions[index].robust_rb;
180180
}
181181

182+
template <typename TurnInfo, typename IntersectionInfo, typename DirInfo>
183+
static inline void assign_point_and_correct(TurnInfo& ti,
184+
method_type method,
185+
IntersectionInfo const& info, DirInfo const& dir_info)
186+
{
187+
ti.method = method;
188+
189+
// For touch/touch interior always take the intersection point 0 (there is only one).
190+
static int const index = 0;
191+
192+
geometry::convert(info.intersections[index], ti.point);
193+
194+
for (int i = 0; i < 2; i++)
195+
{
196+
if (dir_info.arrival[i] == 1)
197+
{
198+
// The segment arrives at the intersection point, its fraction should be 1
199+
// (due to precision it might be nearly so, but not completely, in rare cases)
200+
ti.operations[i].fraction = {1, 1};
201+
}
202+
else if (dir_info.arrival[i] == -1)
203+
{
204+
// The segment leaves from the intersection point, likewise its fraction should be 0
205+
ti.operations[i].fraction = {0, 1};
206+
}
207+
else
208+
{
209+
ti.operations[i].fraction = i == 0 ? info.fractions[index].robust_ra
210+
: info.fractions[index].robust_rb;
211+
}
212+
}
213+
}
214+
182215
template <typename IntersectionInfo>
183216
static inline unsigned int non_opposite_to_index(IntersectionInfo const& info)
184217
{
@@ -344,7 +377,7 @@ struct touch_interior : public base_turn_handler
344377
SidePolicy const& side,
345378
UmbrellaStrategy const& umbrella_strategy)
346379
{
347-
assign_point(ti, method_touch_interior, intersection_info, 0);
380+
assign_point_and_correct(ti, method_touch_interior, intersection_info, dir_info);
348381

349382
// Both segments of q touch segment p somewhere in its interior
350383
// 1) We know: if q comes from LEFT or RIGHT
@@ -443,7 +476,6 @@ struct touch_interior : public base_turn_handler
443476
if (side_qk_q == side_qi_p)
444477
{
445478
both_collinear<index_p, index_q>(range_p, range_q, umbrella_strategy, 1, 2, ti);
446-
return;
447479
}
448480
else
449481
{
@@ -568,7 +600,7 @@ struct touch : public base_turn_handler
568600
SideCalculator const& side,
569601
UmbrellaStrategy const& umbrella_strategy)
570602
{
571-
assign_point(ti, method_touch, intersection_info, 0);
603+
assign_point_and_correct(ti, method_touch, intersection_info, dir_info);
572604

573605
bool const has_pk = ! range_p.is_last_segment();
574606
bool const has_qk = ! range_q.is_last_segment();
@@ -760,7 +792,7 @@ struct equal : public base_turn_handler
760792
UniqueSubRange2 const& range_q,
761793
TurnInfo& ti,
762794
IntersectionInfo const& info,
763-
DirInfo const& ,
795+
DirInfo const& ,
764796
SideCalculator const& side,
765797
UmbrellaStrategy const& umbrella_strategy)
766798
{
@@ -882,7 +914,7 @@ struct start : public base_turn_handler
882914
}
883915

884916
// Copy intersection point
885-
assign_point(ti, method_start, info, 0);
917+
assign_point_and_correct(ti, method_start, info, dir_info);
886918
return true;
887919
}
888920

@@ -1060,23 +1092,15 @@ private :
10601092
1 -1 -1 CXO3 ux
10611093
*/
10621094

1063-
template
1064-
<
1065-
unsigned int Index,
1066-
typename IntersectionInfo
1067-
>
1068-
static inline bool set_tp(int side_rk_r, bool handle_robustness,
1069-
int side_rk_s,
1070-
TurnInfo& tp, IntersectionInfo const& intersection_info)
1095+
template <unsigned int Index, typename IntersectionInfo>
1096+
static inline bool set_tp(int side_rk_r, TurnInfo& tp,
1097+
IntersectionInfo const& intersection_info)
10711098
{
10721099
BOOST_STATIC_ASSERT(Index <= 1);
10731100

1074-
boost::ignore_unused(handle_robustness, side_rk_s);
1075-
10761101
operation_type blocked = operation_blocked;
10771102
switch(side_rk_r)
10781103
{
1079-
10801104
case 1 :
10811105
// Turning left on opposite collinear: intersection
10821106
tp.operations[Index].operation = operation_intersection;
@@ -1168,7 +1192,7 @@ private :
11681192
// If P arrives within Q, there is a turn dependent on P
11691193
if ( p_arrival == 1
11701194
&& ! range_p.is_last_segment()
1171-
&& set_tp<0>(side.pk_wrt_p1(), true, side.pk_wrt_q1(), tp, info.i_info()) )
1195+
&& set_tp<0>(side.pk_wrt_p1(), tp, info.i_info()) )
11721196
{
11731197
turn_transformer(tp);
11741198

@@ -1178,7 +1202,7 @@ private :
11781202
// If Q arrives within P, there is a turn dependent on Q
11791203
if ( q_arrival == 1
11801204
&& ! range_q.is_last_segment()
1181-
&& set_tp<1>(side.qk_wrt_q1(), false, side.qk_wrt_p1(), tp, info.i_info()) )
1205+
&& set_tp<1>(side.qk_wrt_q1(), tp, info.i_info()) )
11821206
{
11831207
turn_transformer(tp);
11841208

@@ -1237,7 +1261,7 @@ struct only_convert : public base_turn_handler
12371261
template<typename TurnInfo, typename IntersectionInfo>
12381262
static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
12391263
{
1240-
assign_point(ti, method_none, intersection_info, 0); // was collinear
1264+
assign_point(ti, method_none, intersection_info, 0);
12411265
ti.operations[0].operation = operation_continue;
12421266
ti.operations[1].operation = operation_continue;
12431267
}

‎test/algorithms/buffer/buffer_linestring.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -418,7 +418,7 @@ int test_main(int, char* [])
418418
#endif
419419

420420
#if defined(BOOST_GEOMETRY_TEST_FAILURES)
421-
BoostGeometryWriteExpectedFailures(2, 2, 15, 2);
421+
BoostGeometryWriteExpectedFailures(2, 4, 17, 4);
422422
#endif
423423

424424
return 0;

‎test/algorithms/buffer/buffer_multi_polygon.cpp

Lines changed: 20 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -330,6 +330,11 @@ static std::string const nores_et_4
330330
static std::string const nores_et_5
331331
= "MULTIPOLYGON(((3 2,3 3,4 3,4 2,3 2)),((0 3,0 4,1 3,0 3)),((2 2,2 1,1 1,2 2)))";
332332

333+
static std::string const nores_et_6
334+
= "MULTIPOLYGON(((0 5,0 6,1 5,0 5)),((3 5,4 6,4 5,3 5)),((2 0,2 1,3 0,2 0)),((5 2,4 1,4 4,5 5,5 2)),((0 9,1 9,1 8,0 8,0 9)),((1 8,1 7,0 7,1 8)),((7 4,7 3,6 3,7 4)),((7 4,7 6,8 6,8 5,7 4)),((7 3,8 3,8 2,7 2,6 2,7 3)),((7 9,8 9,7.5 8.5,8 8,8 7,7 7,7 9)),((8 9,9 9,9 8,8 8,8 9)),((8 3,8 4,9 4,8 3)),((10 3,9 2,9 4,10 4,10 3)),((5 2,6 1,5 1,5 2)),((4 8,4.5 7.5,5 8,5 7,4 7,4 8)),((4 8,3 8,4 9,4 8)),((4 9,3 9,4 10,4 9)),((9 2,9 1,8 1,9 2)))";
335+
336+
static std::string const nores_et_7
337+
= "MULTIPOLYGON(((4 0,5 1,5 0,4 0)),((5 4,6 5,6 4,5 4)),((3 6,4 6,4 5,3 5,3 6)),((0 6,1 7,1 6,0 6)),((2 9,2 10,3 10,2 9)),((2 2,3 3,3 2,2 2)),((5 9,4 8,4 9,5 10,6 10,6 9,5 9)),((4 8,3 7,3 8,3 9,4 8)),((6 2,6 3,7 3,7 2,6 2)),((6 2,5 2,5 3,6 2)),((6 7,5 7,5 8,6 8,6 7)),((6 7,6 6,5 6,6 7)),((6 7,7 8,7 7,6 7)),((9 5,9 6,10 6,9.5 5.5,10 5,9 5)),((9 5,9 4,8 4,9 5)),((9 4,10 5,10 4,9 4)),((9 1,8 1,7 1,8 2,8 3,9 3,9 1)),((9 1,10 1,9 0,8 0,9 1)),((7 3,7 4,8 4,8 3,7 3)),((9 10,10 10,10 9,9 9,9 10)),((9 10,8 9,7 9,7 10,9 10)))";
333338

334339
// Cases having wrong next turn information, somehow, taking the "i" (intersection),
335340
// which is wrong for buffer (it should take the "u" like union)
@@ -338,6 +343,10 @@ static std::string const nores_wn_1
338343
static std::string const nores_wn_2
339344
= "MULTIPOLYGON(((9 5,9 6,10 5,9 5)),((8 8,8 7,7 7,7 8,8 8)),((8 8,9 9,9 8,8 8)))";
340345

346+
// Other cases with wrong turn information
347+
static std::string const nores_wt_1
348+
= "MULTIPOLYGON(((0 4,0 5,1 4,0 4)),((9 3,9 4,10 4,9 3)),((9 7,10 8,10 7,9 7)),((6 7,7 8,7 7,6 7)),((0 7,0 8,1 8,0 7)),((3 6,4 6,4 5,3 4,3 6)),((3 7,2 6,2 7,3 7)),((3 7,3 8,4 8,4 7,3 7)),((3 3,4 4,4 3,3 3)),((3 3,3 2,2 2,2 3,3 3)),((2 6,2 5,1 5,1 6,2 6)),((6 4,6 3,5 3,5 4,6 4)),((6 4,7 5,7 4,6 4)),((5 1,4 0,4 1,5 1)),((5 1,5 2,6 2,6 1,5 1)))";
349+
341350

342351
static std::string const neighbouring
343352
= "MULTIPOLYGON(((0 0,0 10,10 10,10 0,0 0)),((10 10,10 20,20 20,20 10,10 10)))";
@@ -533,10 +542,7 @@ void test_all()
533542
test_one<multi_polygon_type, polygon_type>("rt_u11_50", rt_u11, join_miter, end_flat, 0.04289, -0.50);
534543
test_one<multi_polygon_type, polygon_type>("rt_u11_25", rt_u11, join_miter, end_flat, 10.1449, -0.25);
535544

536-
#if defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
537-
// Failing because of a start turn
538545
test_one<multi_polygon_type, polygon_type>("rt_u12", rt_u12, join_miter, end_flat, 142.1348, 1.0);
539-
#endif
540546
test_one<multi_polygon_type, polygon_type>("rt_u13", rt_u13, join_miter, end_flat, 115.4853, 1.0);
541547

542548
test_one<multi_polygon_type, polygon_type>("rt_v1", rt_v1, join_round32, end_flat, 26.9994, 1.0);
@@ -551,14 +557,23 @@ void test_all()
551557
test_one<multi_polygon_type, polygon_type>("nores_mt_5", nores_mt_5, join_round32, end_flat, 26.4375, 1.0);
552558
test_one<multi_polygon_type, polygon_type>("nores_mt_6", nores_mt_6, join_round32, end_flat, 16.9018, 1.0);
553559

554-
#if defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
555560
test_one<multi_polygon_type, polygon_type>("nores_et_1", nores_et_1, join_round32, end_flat, 18.9866, 1.0);
561+
562+
#if defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
556563
test_one<multi_polygon_type, polygon_type>("nores_et_2", nores_et_2, join_round32, end_flat, 23.8389, 1.0);
557564
test_one<multi_polygon_type, polygon_type>("nores_et_3", nores_et_3, join_round32, end_flat, 26.9030, 1.0);
565+
#endif
566+
558567
test_one<multi_polygon_type, polygon_type>("nores_et_4", nores_et_4, join_round32, end_flat, 19.9626, 1.0);
559568
test_one<multi_polygon_type, polygon_type>("nores_et_5", nores_et_5, join_round32, end_flat, 19.9615, 1.0);
569+
560570
test_one<multi_polygon_type, polygon_type>("nores_wn_1", nores_wn_1, join_round32, end_flat, 23.7659, 1.0);
561571
test_one<multi_polygon_type, polygon_type>("nores_wn_2", nores_wn_2, join_round32, end_flat, 18.2669, 1.0);
572+
573+
#if defined(BOOST_GEOMETRY_USE_RESCALING) || defined(BOOST_GEOMETRY_TEST_FAILURES)
574+
test_one<multi_polygon_type, polygon_type>("nores_et_6", nores_et_6, join_round32, end_flat, 96.1795, 1.0);
575+
test_one<multi_polygon_type, polygon_type>("nores_et_7", nores_et_7, join_round32, end_flat, 105.9577, 1.0);
576+
test_one<multi_polygon_type, polygon_type>("nores_wt_1", nores_wt_1, join_round32, end_flat, 80.1609, 1.0);
562577
#endif
563578

564579
test_one<multi_polygon_type, polygon_type>("neighbouring_small",
@@ -604,7 +619,7 @@ int test_main(int, char* [])
604619
#endif
605620

606621
#if defined(BOOST_GEOMETRY_TEST_FAILURES)
607-
BoostGeometryWriteExpectedFailures(1, 14, 2, 11);
622+
BoostGeometryWriteExpectedFailures(1, 8, 2, 7);
608623
#endif
609624

610625
return 0;

‎test/algorithms/set_operations/difference/difference.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -624,7 +624,7 @@ int test_main(int, char* [])
624624
#if defined(BOOST_GEOMETRY_TEST_FAILURES)
625625
// Not yet fully tested for float and long double.
626626
// The difference algorithm can generate (additional) slivers
627-
BoostGeometryWriteExpectedFailures(10, 11, 24, 14);
627+
BoostGeometryWriteExpectedFailures(10, 11, 24, 15);
628628
#endif
629629

630630
return 0;

‎test/algorithms/set_operations/intersection/intersection.cpp

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -179,7 +179,7 @@ void test_areal()
179179

180180
TEST_INTERSECTION(isovist, 1, 19, expectation_limits(88.19202, 88.19206));
181181

182-
TEST_INTERSECTION_IGNORE(geos_1, 1, -1, expectation_limits(3455, 3462));
182+
TEST_INTERSECTION_IGNORE(geos_1, 1, -1, expectation_limits(3454, 3462));
183183

184184
// Can, in some cases, create small slivers
185185
// In some cases: 1.430511474609375e-05 (clang/gcc on Xubuntu using b2)
@@ -934,7 +934,7 @@ int test_main(int, char* [])
934934
#if defined(BOOST_GEOMETRY_TEST_FAILURES)
935935
// llb_touch generates a polygon with 1 point and is therefore invalid everywhere
936936
// TODO: this should be easy to fix
937-
BoostGeometryWriteExpectedFailures(4, 3, 3, 1);
937+
BoostGeometryWriteExpectedFailures(4, 2, 3, 1);
938938
#endif
939939

940940
return 0;

‎test/algorithms/set_operations/union/union.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -593,7 +593,7 @@ int test_main(int, char* [])
593593
#endif
594594

595595
#if defined(BOOST_GEOMETRY_TEST_FAILURES)
596-
BoostGeometryWriteExpectedFailures(3, 5, 1, 0);
596+
BoostGeometryWriteExpectedFailures(3, 3, 1, 0);
597597
#endif
598598

599599
return 0;

‎test/algorithms/set_operations/union/union_multi.cpp

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -489,7 +489,7 @@ int test_main(int, char* [])
489489
#endif
490490

491491
#if defined(BOOST_GEOMETRY_TEST_FAILURES)
492-
BoostGeometryWriteExpectedFailures(9, 2, 5, 0);
492+
BoostGeometryWriteExpectedFailures(9, 2, 1, 0);
493493
#endif
494494

495495
return 0;

0 commit comments

Comments
 (0)