intersection_insert.hpp 48 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613
  1. // Boost.Geometry (aka GGL, Generic Geometry Library)
  2. // Copyright (c) 2007-2015 Barend Gehrels, Amsterdam, the Netherlands.
  3. // This file was modified by Oracle on 2014, 2015, 2017, 2019, 2020.
  4. // Modifications copyright (c) 2014-2020 Oracle and/or its affiliates.
  5. // Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle
  6. // Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
  7. // Use, modification and distribution is subject to the Boost Software License,
  8. // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
  9. // http://www.boost.org/LICENSE_1_0.txt)
  10. #ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
  11. #define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP
  12. #include <cstddef>
  13. #include <boost/mpl/if.hpp>
  14. #include <boost/mpl/assert.hpp>
  15. #include <boost/range/metafunctions.hpp>
  16. #include <boost/geometry/core/is_areal.hpp>
  17. #include <boost/geometry/core/point_order.hpp>
  18. #include <boost/geometry/core/reverse_dispatch.hpp>
  19. #include <boost/geometry/geometries/concepts/check.hpp>
  20. #include <boost/geometry/algorithms/convert.hpp>
  21. #include <boost/geometry/algorithms/detail/point_on_border.hpp>
  22. #include <boost/geometry/algorithms/detail/overlay/clip_linestring.hpp>
  23. #include <boost/geometry/algorithms/detail/overlay/follow.hpp>
  24. #include <boost/geometry/algorithms/detail/overlay/get_intersection_points.hpp>
  25. #include <boost/geometry/algorithms/detail/overlay/overlay.hpp>
  26. #include <boost/geometry/algorithms/detail/overlay/overlay_type.hpp>
  27. #include <boost/geometry/algorithms/detail/overlay/range_in_geometry.hpp>
  28. #include <boost/geometry/algorithms/detail/overlay/segment_as_subrange.hpp>
  29. #include <boost/geometry/policies/robustness/rescale_policy_tags.hpp>
  30. #include <boost/geometry/policies/robustness/segment_ratio_type.hpp>
  31. #include <boost/geometry/policies/robustness/get_rescale_policy.hpp>
  32. #include <boost/geometry/views/segment_view.hpp>
  33. #include <boost/geometry/views/detail/boundary_view.hpp>
  34. #include <boost/geometry/algorithms/detail/check_iterator_range.hpp>
  35. #include <boost/geometry/algorithms/detail/overlay/linear_linear.hpp>
  36. #include <boost/geometry/algorithms/detail/overlay/pointlike_areal.hpp>
  37. #include <boost/geometry/algorithms/detail/overlay/pointlike_linear.hpp>
  38. #include <boost/geometry/algorithms/detail/overlay/pointlike_pointlike.hpp>
  39. #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
  40. #include <boost/geometry/algorithms/detail/overlay/debug_turn_info.hpp>
  41. #include <boost/geometry/io/wkt/wkt.hpp>
  42. #endif
  43. namespace boost { namespace geometry
  44. {
  45. #ifndef DOXYGEN_NO_DETAIL
  46. namespace detail { namespace intersection
  47. {
  48. template <typename PointOut>
  49. struct intersection_segment_segment_point
  50. {
  51. template
  52. <
  53. typename Segment1, typename Segment2,
  54. typename RobustPolicy,
  55. typename OutputIterator, typename Strategy
  56. >
  57. static inline OutputIterator apply(Segment1 const& segment1,
  58. Segment2 const& segment2,
  59. RobustPolicy const& ,
  60. OutputIterator out,
  61. Strategy const& strategy)
  62. {
  63. // Make sure this is only called with no rescaling
  64. BOOST_STATIC_ASSERT((boost::is_same
  65. <
  66. no_rescale_policy_tag,
  67. typename rescale_policy_type<RobustPolicy>::type
  68. >::value));
  69. typedef typename point_type<PointOut>::type point_type;
  70. // Get the intersection point (or two points)
  71. typedef segment_intersection_points<point_type> intersection_return_type;
  72. typedef policies::relate::segments_intersection_points
  73. <
  74. intersection_return_type
  75. > policy_type;
  76. detail::segment_as_subrange<Segment1> sub_range1(segment1);
  77. detail::segment_as_subrange<Segment2> sub_range2(segment2);
  78. intersection_return_type
  79. is = strategy.apply(sub_range1, sub_range2, policy_type());
  80. for (std::size_t i = 0; i < is.count; i++)
  81. {
  82. PointOut p;
  83. geometry::convert(is.intersections[i], p);
  84. *out++ = p;
  85. }
  86. return out;
  87. }
  88. };
  89. template <typename PointOut>
  90. struct intersection_linestring_linestring_point
  91. {
  92. template
  93. <
  94. typename Linestring1, typename Linestring2,
  95. typename RobustPolicy,
  96. typename OutputIterator,
  97. typename Strategy
  98. >
  99. static inline OutputIterator apply(Linestring1 const& linestring1,
  100. Linestring2 const& linestring2,
  101. RobustPolicy const& robust_policy,
  102. OutputIterator out,
  103. Strategy const& strategy)
  104. {
  105. // Make sure this is only called with no rescaling
  106. BOOST_STATIC_ASSERT((boost::is_same
  107. <
  108. no_rescale_policy_tag,
  109. typename rescale_policy_type<RobustPolicy>::type
  110. >::value));
  111. typedef detail::overlay::turn_info<PointOut> turn_info;
  112. std::deque<turn_info> turns;
  113. geometry::get_intersection_points(linestring1, linestring2,
  114. robust_policy, turns, strategy);
  115. for (typename boost::range_iterator<std::deque<turn_info> const>::type
  116. it = boost::begin(turns); it != boost::end(turns); ++it)
  117. {
  118. PointOut p;
  119. geometry::convert(it->point, p);
  120. *out++ = p;
  121. }
  122. return out;
  123. }
  124. };
  125. /*!
  126. \brief Version of linestring with an areal feature (polygon or multipolygon)
  127. */
  128. template
  129. <
  130. bool ReverseAreal,
  131. typename GeometryOut,
  132. overlay_type OverlayType,
  133. bool FollowIsolatedPoints
  134. >
  135. struct intersection_of_linestring_with_areal
  136. {
  137. #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
  138. template <typename Turn, typename Operation>
  139. static inline void debug_follow(Turn const& turn, Operation op,
  140. int index)
  141. {
  142. std::cout << index
  143. << " at " << op.seg_id
  144. << " meth: " << method_char(turn.method)
  145. << " op: " << operation_char(op.operation)
  146. << " vis: " << visited_char(op.visited)
  147. << " of: " << operation_char(turn.operations[0].operation)
  148. << operation_char(turn.operations[1].operation)
  149. << " " << geometry::wkt(turn.point)
  150. << std::endl;
  151. }
  152. template <typename Turn>
  153. static inline void debug_turn(Turn const& t, bool non_crossing)
  154. {
  155. std::cout << "checking turn @"
  156. << geometry::wkt(t.point)
  157. << "; " << method_char(t.method)
  158. << ":" << operation_char(t.operations[0].operation)
  159. << "/" << operation_char(t.operations[1].operation)
  160. << "; non-crossing? "
  161. << std::boolalpha << non_crossing << std::noboolalpha
  162. << std::endl;
  163. }
  164. #endif
  165. template <typename Linestring, typename Areal, typename Strategy, typename Turns>
  166. static inline bool simple_turns_analysis(Linestring const& linestring,
  167. Areal const& areal,
  168. Strategy const& strategy,
  169. Turns const& turns,
  170. int & inside_value)
  171. {
  172. using namespace overlay;
  173. bool found_continue = false;
  174. bool found_intersection = false;
  175. bool found_union = false;
  176. bool found_front = false;
  177. for (typename Turns::const_iterator it = turns.begin();
  178. it != turns.end(); ++it)
  179. {
  180. method_type const method = it->method;
  181. operation_type const op = it->operations[0].operation;
  182. if (method == method_crosses)
  183. {
  184. return false;
  185. }
  186. else if (op == operation_intersection)
  187. {
  188. found_intersection = true;
  189. }
  190. else if (op == operation_union)
  191. {
  192. found_union = true;
  193. }
  194. else if (op == operation_continue)
  195. {
  196. found_continue = true;
  197. }
  198. if ((found_intersection || found_continue) && found_union)
  199. {
  200. return false;
  201. }
  202. if (it->operations[0].position == position_front)
  203. {
  204. found_front = true;
  205. }
  206. }
  207. if (found_front)
  208. {
  209. if (found_intersection)
  210. {
  211. inside_value = 1; // inside
  212. }
  213. else if (found_union)
  214. {
  215. inside_value = -1; // outside
  216. }
  217. else // continue and blocked
  218. {
  219. inside_value = 0;
  220. }
  221. return true;
  222. }
  223. // if needed analyse points of a linestring
  224. // NOTE: range_in_geometry checks points of a linestring
  225. // until a point inside/outside areal is found
  226. // TODO: Could be replaced with point_in_geometry() because found_front is false
  227. inside_value = range_in_geometry(linestring, areal, strategy);
  228. if ( (found_intersection && inside_value == -1) // going in from outside
  229. || (found_continue && inside_value == -1) // going on boundary from outside
  230. || (found_union && inside_value == 1) ) // going out from inside
  231. {
  232. return false;
  233. }
  234. return true;
  235. }
  236. template
  237. <
  238. typename LineString, typename Areal,
  239. typename RobustPolicy,
  240. typename OutputIterator, typename Strategy
  241. >
  242. static inline OutputIterator apply(LineString const& linestring, Areal const& areal,
  243. RobustPolicy const& robust_policy,
  244. OutputIterator out,
  245. Strategy const& strategy)
  246. {
  247. // Make sure this is only called with no rescaling
  248. BOOST_STATIC_ASSERT((boost::is_same
  249. <
  250. no_rescale_policy_tag,
  251. typename rescale_policy_type<RobustPolicy>::type
  252. >::value));
  253. if (boost::size(linestring) == 0)
  254. {
  255. return out;
  256. }
  257. typedef detail::overlay::follow
  258. <
  259. GeometryOut,
  260. LineString,
  261. Areal,
  262. OverlayType,
  263. false, // do not remove spikes for linear geometries
  264. FollowIsolatedPoints
  265. > follower;
  266. typedef typename geometry::detail::output_geometry_access
  267. <
  268. GeometryOut, linestring_tag, linestring_tag
  269. > linear;
  270. typedef typename point_type
  271. <
  272. typename linear::type
  273. >::type point_type;
  274. typedef geometry::segment_ratio
  275. <
  276. typename coordinate_type<point_type>::type
  277. > ratio_type;
  278. typedef detail::overlay::turn_info
  279. <
  280. point_type,
  281. ratio_type,
  282. detail::overlay::turn_operation_linear
  283. <
  284. point_type,
  285. ratio_type
  286. >
  287. > turn_info;
  288. std::deque<turn_info> turns;
  289. detail::get_turns::no_interrupt_policy policy;
  290. typedef detail::overlay::get_turn_info_linear_areal
  291. <
  292. detail::overlay::assign_null_policy
  293. > turn_policy;
  294. dispatch::get_turns
  295. <
  296. typename geometry::tag<LineString>::type,
  297. typename geometry::tag<Areal>::type,
  298. LineString,
  299. Areal,
  300. false,
  301. (OverlayType == overlay_intersection ? ReverseAreal : !ReverseAreal),
  302. turn_policy
  303. >::apply(0, linestring, 1, areal,
  304. strategy, robust_policy,
  305. turns, policy);
  306. int inside_value = 0;
  307. if (simple_turns_analysis(linestring, areal, strategy, turns, inside_value))
  308. {
  309. // No crossing the boundary, it is either
  310. // inside (interior + borders)
  311. // or outside (exterior + borders)
  312. // or on boundary
  313. // add linestring to the output if conditions are met
  314. if (follower::included(inside_value))
  315. {
  316. typename linear::type copy;
  317. geometry::convert(linestring, copy);
  318. *linear::get(out)++ = copy;
  319. }
  320. return out;
  321. }
  322. #if defined(BOOST_GEOMETRY_DEBUG_FOLLOW)
  323. int index = 0;
  324. for(typename std::deque<turn_info>::const_iterator
  325. it = turns.begin(); it != turns.end(); ++it)
  326. {
  327. debug_follow(*it, it->operations[0], index++);
  328. }
  329. #endif
  330. return follower::apply
  331. (
  332. linestring, areal,
  333. geometry::detail::overlay::operation_intersection,
  334. turns, robust_policy, out, strategy
  335. );
  336. }
  337. };
  338. template <typename Turns, typename OutputIterator>
  339. inline OutputIterator intersection_output_turn_points(Turns const& turns,
  340. OutputIterator out)
  341. {
  342. for (typename Turns::const_iterator
  343. it = turns.begin(); it != turns.end(); ++it)
  344. {
  345. *out++ = it->point;
  346. }
  347. return out;
  348. }
  349. template <typename PointOut>
  350. struct intersection_areal_areal_point
  351. {
  352. template
  353. <
  354. typename Geometry1, typename Geometry2,
  355. typename RobustPolicy,
  356. typename OutputIterator,
  357. typename Strategy
  358. >
  359. static inline OutputIterator apply(Geometry1 const& geometry1,
  360. Geometry2 const& geometry2,
  361. RobustPolicy const& robust_policy,
  362. OutputIterator out,
  363. Strategy const& strategy)
  364. {
  365. typedef detail::overlay::turn_info
  366. <
  367. PointOut,
  368. typename segment_ratio_type<PointOut, RobustPolicy>::type
  369. > turn_info;
  370. std::vector<turn_info> turns;
  371. detail::get_turns::no_interrupt_policy policy;
  372. geometry::get_turns
  373. <
  374. false, false, detail::overlay::assign_null_policy
  375. >(geometry1, geometry2, strategy, robust_policy, turns, policy);
  376. return intersection_output_turn_points(turns, out);
  377. }
  378. };
  379. template <typename PointOut>
  380. struct intersection_linear_areal_point
  381. {
  382. template
  383. <
  384. typename Geometry1, typename Geometry2,
  385. typename RobustPolicy,
  386. typename OutputIterator,
  387. typename Strategy
  388. >
  389. static inline OutputIterator apply(Geometry1 const& geometry1,
  390. Geometry2 const& geometry2,
  391. RobustPolicy const& robust_policy,
  392. OutputIterator out,
  393. Strategy const& strategy)
  394. {
  395. // Make sure this is only called with no rescaling
  396. BOOST_STATIC_ASSERT((boost::is_same
  397. <
  398. no_rescale_policy_tag,
  399. typename rescale_policy_type<RobustPolicy>::type
  400. >::value));
  401. typedef geometry::segment_ratio<typename geometry::coordinate_type<PointOut>::type> ratio_type;
  402. typedef detail::overlay::turn_info
  403. <
  404. PointOut,
  405. ratio_type,
  406. detail::overlay::turn_operation_linear
  407. <
  408. PointOut,
  409. ratio_type
  410. >
  411. > turn_info;
  412. typedef detail::overlay::get_turn_info_linear_areal
  413. <
  414. detail::overlay::assign_null_policy
  415. > turn_policy;
  416. std::vector<turn_info> turns;
  417. detail::get_turns::no_interrupt_policy interrupt_policy;
  418. dispatch::get_turns
  419. <
  420. typename geometry::tag<Geometry1>::type,
  421. typename geometry::tag<Geometry2>::type,
  422. Geometry1,
  423. Geometry2,
  424. false,
  425. false,
  426. turn_policy
  427. >::apply(0, geometry1, 1, geometry2,
  428. strategy, robust_policy,
  429. turns, interrupt_policy);
  430. return intersection_output_turn_points(turns, out);
  431. }
  432. };
  433. template <typename PointOut>
  434. struct intersection_areal_linear_point
  435. {
  436. template
  437. <
  438. typename Geometry1, typename Geometry2,
  439. typename RobustPolicy,
  440. typename OutputIterator,
  441. typename Strategy
  442. >
  443. static inline OutputIterator apply(Geometry1 const& geometry1,
  444. Geometry2 const& geometry2,
  445. RobustPolicy const& robust_policy,
  446. OutputIterator out,
  447. Strategy const& strategy)
  448. {
  449. return intersection_linear_areal_point
  450. <
  451. PointOut
  452. >::apply(geometry2, geometry1, robust_policy, out, strategy);
  453. }
  454. };
  455. struct tupled_output_tag {};
  456. template
  457. <
  458. typename GeometryOut,
  459. bool IsTupled = geometry::detail::is_tupled_range_values<GeometryOut>::value
  460. >
  461. struct tag
  462. : geometry::tag<GeometryOut>
  463. {};
  464. template <typename GeometryOut>
  465. struct tag<GeometryOut, true>
  466. {
  467. typedef tupled_output_tag type;
  468. };
  469. template <typename Geometry1, typename Geometry2, typename TupledOut>
  470. struct expect_output_p
  471. {
  472. static const bool is_point_found = geometry::tuples::exists_if
  473. <
  474. TupledOut, geometry::detail::is_tag_same_as_pred<point_tag>::template pred
  475. >::value;
  476. BOOST_MPL_ASSERT_MSG
  477. (
  478. is_point_found, POINTLIKE_GEOMETRY_EXPECTED_IN_TUPLED_OUTPUT,
  479. (types<Geometry1, Geometry2, TupledOut>)
  480. );
  481. };
  482. template <typename Geometry1, typename Geometry2, typename TupledOut>
  483. struct expect_output_pl
  484. : expect_output_p<Geometry1, Geometry2, TupledOut>
  485. {
  486. static const bool is_linestring_found = geometry::tuples::exists_if
  487. <
  488. TupledOut, geometry::detail::is_tag_same_as_pred<linestring_tag>::template pred
  489. >::value;
  490. BOOST_MPL_ASSERT_MSG
  491. (
  492. is_linestring_found, LINEAR_GEOMETRY_EXPECTED_IN_TUPLED_OUTPUT,
  493. (types<Geometry1, Geometry2, TupledOut>)
  494. );
  495. };
  496. template <typename Geometry1, typename Geometry2, typename TupledOut>
  497. struct expect_output_pla
  498. : expect_output_pl<Geometry1, Geometry2, TupledOut>
  499. {
  500. static const bool is_polygon_found = geometry::tuples::exists_if
  501. <
  502. TupledOut, geometry::detail::is_tag_same_as_pred<polygon_tag>::template pred
  503. >::value;
  504. BOOST_MPL_ASSERT_MSG
  505. (
  506. is_polygon_found, AREAL_GEOMETRY_EXPECTED_IN_TUPLED_OUTPUT,
  507. (types<Geometry1, Geometry2, TupledOut>)
  508. );
  509. };
  510. }} // namespace detail::intersection
  511. #endif // DOXYGEN_NO_DETAIL
  512. #ifndef DOXYGEN_NO_DISPATCH
  513. namespace dispatch
  514. {
  515. template
  516. <
  517. // real types
  518. typename Geometry1,
  519. typename Geometry2,
  520. typename GeometryOut,
  521. overlay_type OverlayType,
  522. // orientation
  523. bool Reverse1 = detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
  524. bool Reverse2 = detail::overlay::do_reverse<geometry::point_order<Geometry2>::value>::value,
  525. // tag dispatching:
  526. typename TagIn1 = typename geometry::tag<Geometry1>::type,
  527. typename TagIn2 = typename geometry::tag<Geometry2>::type,
  528. typename TagOut = typename detail::intersection::tag<GeometryOut>::type,
  529. // metafunction finetuning helpers:
  530. typename CastedTagIn1 = typename geometry::tag_cast<TagIn1, areal_tag, linear_tag, pointlike_tag>::type,
  531. typename CastedTagIn2 = typename geometry::tag_cast<TagIn2, areal_tag, linear_tag, pointlike_tag>::type,
  532. typename CastedTagOut = typename geometry::tag_cast<TagOut, areal_tag, linear_tag, pointlike_tag>::type
  533. >
  534. struct intersection_insert
  535. {
  536. BOOST_MPL_ASSERT_MSG
  537. (
  538. false, NOT_OR_NOT_YET_IMPLEMENTED_FOR_THIS_GEOMETRY_TYPES_OR_ORIENTATIONS
  539. , (types<Geometry1, Geometry2, GeometryOut>)
  540. );
  541. };
  542. template
  543. <
  544. typename Geometry1, typename Geometry2,
  545. typename GeometryOut,
  546. overlay_type OverlayType,
  547. bool Reverse1, bool Reverse2,
  548. typename TagIn1, typename TagIn2, typename TagOut
  549. >
  550. struct intersection_insert
  551. <
  552. Geometry1, Geometry2,
  553. GeometryOut,
  554. OverlayType,
  555. Reverse1, Reverse2,
  556. TagIn1, TagIn2, TagOut,
  557. areal_tag, areal_tag, areal_tag
  558. > : detail::overlay::overlay
  559. <
  560. Geometry1, Geometry2, Reverse1, Reverse2,
  561. detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
  562. GeometryOut, OverlayType
  563. >
  564. {};
  565. // Any areal type with box:
  566. template
  567. <
  568. typename Geometry, typename Box,
  569. typename GeometryOut,
  570. overlay_type OverlayType,
  571. bool Reverse1, bool Reverse2,
  572. typename TagIn, typename TagOut
  573. >
  574. struct intersection_insert
  575. <
  576. Geometry, Box,
  577. GeometryOut,
  578. OverlayType,
  579. Reverse1, Reverse2,
  580. TagIn, box_tag, TagOut,
  581. areal_tag, areal_tag, areal_tag
  582. > : detail::overlay::overlay
  583. <
  584. Geometry, Box, Reverse1, Reverse2,
  585. detail::overlay::do_reverse<geometry::point_order<GeometryOut>::value>::value,
  586. GeometryOut, OverlayType
  587. >
  588. {};
  589. template
  590. <
  591. typename Segment1, typename Segment2,
  592. typename GeometryOut,
  593. overlay_type OverlayType,
  594. bool Reverse1, bool Reverse2
  595. >
  596. struct intersection_insert
  597. <
  598. Segment1, Segment2,
  599. GeometryOut,
  600. OverlayType,
  601. Reverse1, Reverse2,
  602. segment_tag, segment_tag, point_tag,
  603. linear_tag, linear_tag, pointlike_tag
  604. > : detail::intersection::intersection_segment_segment_point<GeometryOut>
  605. {};
  606. template
  607. <
  608. typename Linestring1, typename Linestring2,
  609. typename GeometryOut,
  610. overlay_type OverlayType,
  611. bool Reverse1, bool Reverse2
  612. >
  613. struct intersection_insert
  614. <
  615. Linestring1, Linestring2,
  616. GeometryOut,
  617. OverlayType,
  618. Reverse1, Reverse2,
  619. linestring_tag, linestring_tag, point_tag,
  620. linear_tag, linear_tag, pointlike_tag
  621. > : detail::intersection::intersection_linestring_linestring_point<GeometryOut>
  622. {};
  623. template
  624. <
  625. typename Linestring, typename Box,
  626. typename GeometryOut,
  627. bool Reverse1, bool Reverse2
  628. >
  629. struct intersection_insert
  630. <
  631. Linestring, Box,
  632. GeometryOut,
  633. overlay_intersection,
  634. Reverse1, Reverse2,
  635. linestring_tag, box_tag, linestring_tag,
  636. linear_tag, areal_tag, linear_tag
  637. >
  638. {
  639. template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  640. static inline OutputIterator apply(Linestring const& linestring,
  641. Box const& box,
  642. RobustPolicy const& robust_policy,
  643. OutputIterator out, Strategy const& )
  644. {
  645. typedef typename point_type<GeometryOut>::type point_type;
  646. strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
  647. return detail::intersection::clip_range_with_box
  648. <GeometryOut>(box, linestring, robust_policy, out, lb_strategy);
  649. }
  650. };
  651. template
  652. <
  653. typename Linestring, typename Polygon,
  654. typename GeometryOut,
  655. overlay_type OverlayType,
  656. bool ReverseLinestring, bool ReversePolygon
  657. >
  658. struct intersection_insert
  659. <
  660. Linestring, Polygon,
  661. GeometryOut,
  662. OverlayType,
  663. ReverseLinestring, ReversePolygon,
  664. linestring_tag, polygon_tag, linestring_tag,
  665. linear_tag, areal_tag, linear_tag
  666. > : detail::intersection::intersection_of_linestring_with_areal
  667. <
  668. ReversePolygon,
  669. GeometryOut,
  670. OverlayType,
  671. false
  672. >
  673. {};
  674. template
  675. <
  676. typename Linestring, typename Ring,
  677. typename GeometryOut,
  678. overlay_type OverlayType,
  679. bool ReverseLinestring, bool ReverseRing
  680. >
  681. struct intersection_insert
  682. <
  683. Linestring, Ring,
  684. GeometryOut,
  685. OverlayType,
  686. ReverseLinestring, ReverseRing,
  687. linestring_tag, ring_tag, linestring_tag,
  688. linear_tag, areal_tag, linear_tag
  689. > : detail::intersection::intersection_of_linestring_with_areal
  690. <
  691. ReverseRing,
  692. GeometryOut,
  693. OverlayType,
  694. false
  695. >
  696. {};
  697. template
  698. <
  699. typename Segment, typename Box,
  700. typename GeometryOut,
  701. overlay_type OverlayType,
  702. bool Reverse1, bool Reverse2
  703. >
  704. struct intersection_insert
  705. <
  706. Segment, Box,
  707. GeometryOut,
  708. OverlayType,
  709. Reverse1, Reverse2,
  710. segment_tag, box_tag, linestring_tag,
  711. linear_tag, areal_tag, linear_tag
  712. >
  713. {
  714. template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  715. static inline OutputIterator apply(Segment const& segment,
  716. Box const& box,
  717. RobustPolicy const& robust_policy,
  718. OutputIterator out, Strategy const& )
  719. {
  720. geometry::segment_view<Segment> range(segment);
  721. typedef typename point_type<GeometryOut>::type point_type;
  722. strategy::intersection::liang_barsky<Box, point_type> lb_strategy;
  723. return detail::intersection::clip_range_with_box
  724. <GeometryOut>(box, range, robust_policy, out, lb_strategy);
  725. }
  726. };
  727. template
  728. <
  729. typename Geometry1, typename Geometry2,
  730. typename PointOut,
  731. overlay_type OverlayType,
  732. bool Reverse1, bool Reverse2,
  733. typename Tag1, typename Tag2
  734. >
  735. struct intersection_insert
  736. <
  737. Geometry1, Geometry2,
  738. PointOut,
  739. OverlayType,
  740. Reverse1, Reverse2,
  741. Tag1, Tag2, point_tag,
  742. areal_tag, areal_tag, pointlike_tag
  743. >
  744. : public detail::intersection::intersection_areal_areal_point
  745. <
  746. PointOut
  747. >
  748. {};
  749. template
  750. <
  751. typename Geometry1, typename Geometry2,
  752. typename PointOut,
  753. overlay_type OverlayType,
  754. bool Reverse1, bool Reverse2,
  755. typename Tag1, typename Tag2
  756. >
  757. struct intersection_insert
  758. <
  759. Geometry1, Geometry2,
  760. PointOut,
  761. OverlayType,
  762. Reverse1, Reverse2,
  763. Tag1, Tag2, point_tag,
  764. linear_tag, areal_tag, pointlike_tag
  765. >
  766. : public detail::intersection::intersection_linear_areal_point
  767. <
  768. PointOut
  769. >
  770. {};
  771. template
  772. <
  773. typename Geometry1, typename Geometry2,
  774. typename PointOut,
  775. overlay_type OverlayType,
  776. bool Reverse1, bool Reverse2,
  777. typename Tag1, typename Tag2
  778. >
  779. struct intersection_insert
  780. <
  781. Geometry1, Geometry2,
  782. PointOut,
  783. OverlayType,
  784. Reverse1, Reverse2,
  785. Tag1, Tag2, point_tag,
  786. areal_tag, linear_tag, pointlike_tag
  787. >
  788. : public detail::intersection::intersection_areal_linear_point
  789. <
  790. PointOut
  791. >
  792. {};
  793. template
  794. <
  795. typename Geometry1, typename Geometry2, typename GeometryOut,
  796. overlay_type OverlayType,
  797. bool Reverse1, bool Reverse2
  798. >
  799. struct intersection_insert_reversed
  800. {
  801. template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  802. static inline OutputIterator apply(Geometry1 const& g1,
  803. Geometry2 const& g2,
  804. RobustPolicy const& robust_policy,
  805. OutputIterator out,
  806. Strategy const& strategy)
  807. {
  808. return intersection_insert
  809. <
  810. Geometry2, Geometry1, GeometryOut,
  811. OverlayType,
  812. Reverse2, Reverse1
  813. >::apply(g2, g1, robust_policy, out, strategy);
  814. }
  815. };
  816. // dispatch for intersection(areal, areal, linear)
  817. template
  818. <
  819. typename Geometry1, typename Geometry2,
  820. typename LinestringOut,
  821. bool Reverse1, bool Reverse2,
  822. typename Tag1, typename Tag2
  823. >
  824. struct intersection_insert
  825. <
  826. Geometry1, Geometry2,
  827. LinestringOut,
  828. overlay_intersection,
  829. Reverse1, Reverse2,
  830. Tag1, Tag2, linestring_tag,
  831. areal_tag, areal_tag, linear_tag
  832. >
  833. {
  834. template
  835. <
  836. typename RobustPolicy, typename OutputIterator, typename Strategy
  837. >
  838. static inline OutputIterator apply(Geometry1 const& geometry1,
  839. Geometry2 const& geometry2,
  840. RobustPolicy const& robust_policy,
  841. OutputIterator oit,
  842. Strategy const& strategy)
  843. {
  844. detail::boundary_view<Geometry1 const> view1(geometry1);
  845. detail::boundary_view<Geometry2 const> view2(geometry2);
  846. return detail::overlay::linear_linear_linestring
  847. <
  848. detail::boundary_view<Geometry1 const>,
  849. detail::boundary_view<Geometry2 const>,
  850. LinestringOut,
  851. overlay_intersection
  852. >::apply(view1, view2, robust_policy, oit, strategy);
  853. }
  854. };
  855. // dispatch for difference/intersection of linear geometries
  856. template
  857. <
  858. typename Linear1, typename Linear2, typename LineStringOut,
  859. overlay_type OverlayType,
  860. bool Reverse1, bool Reverse2,
  861. typename TagIn1, typename TagIn2
  862. >
  863. struct intersection_insert
  864. <
  865. Linear1, Linear2, LineStringOut, OverlayType,
  866. Reverse1, Reverse2,
  867. TagIn1, TagIn2, linestring_tag,
  868. linear_tag, linear_tag, linear_tag
  869. > : detail::overlay::linear_linear_linestring
  870. <
  871. Linear1, Linear2, LineStringOut, OverlayType
  872. >
  873. {};
  874. template
  875. <
  876. typename Linear1, typename Linear2, typename TupledOut,
  877. overlay_type OverlayType,
  878. bool Reverse1, bool Reverse2,
  879. typename TagIn1, typename TagIn2
  880. >
  881. struct intersection_insert
  882. <
  883. Linear1, Linear2, TupledOut, OverlayType,
  884. Reverse1, Reverse2,
  885. TagIn1, TagIn2, detail::intersection::tupled_output_tag,
  886. linear_tag, linear_tag, detail::intersection::tupled_output_tag
  887. >
  888. // NOTE: This is not fully correct because points can be the result only in
  889. // case of intersection but intersection_insert is called also by difference.
  890. // So this requirement could be relaxed in the future.
  891. : detail::intersection::expect_output_pl<Linear1, Linear2, TupledOut>
  892. {
  893. // NOTE: The order of geometries in TupledOut tuple/pair must correspond to the order
  894. // iterators in OutputIterators tuple/pair.
  895. template
  896. <
  897. typename RobustPolicy, typename OutputIterators, typename Strategy
  898. >
  899. static inline OutputIterators apply(Linear1 const& linear1,
  900. Linear2 const& linear2,
  901. RobustPolicy const& robust_policy,
  902. OutputIterators oit,
  903. Strategy const& strategy)
  904. {
  905. return detail::overlay::linear_linear_linestring
  906. <
  907. Linear1, Linear2, TupledOut, OverlayType
  908. >::apply(linear1, linear2, robust_policy, oit, strategy);
  909. }
  910. };
  911. // dispatch for difference/intersection of point-like geometries
  912. template
  913. <
  914. typename Point1, typename Point2, typename PointOut,
  915. overlay_type OverlayType,
  916. bool Reverse1, bool Reverse2
  917. >
  918. struct intersection_insert
  919. <
  920. Point1, Point2, PointOut, OverlayType,
  921. Reverse1, Reverse2,
  922. point_tag, point_tag, point_tag,
  923. pointlike_tag, pointlike_tag, pointlike_tag
  924. > : detail::overlay::point_point_point
  925. <
  926. Point1, Point2, PointOut, OverlayType
  927. >
  928. {};
  929. template
  930. <
  931. typename MultiPoint, typename Point, typename PointOut,
  932. overlay_type OverlayType,
  933. bool Reverse1, bool Reverse2
  934. >
  935. struct intersection_insert
  936. <
  937. MultiPoint, Point, PointOut, OverlayType,
  938. Reverse1, Reverse2,
  939. multi_point_tag, point_tag, point_tag,
  940. pointlike_tag, pointlike_tag, pointlike_tag
  941. > : detail::overlay::multipoint_point_point
  942. <
  943. MultiPoint, Point, PointOut, OverlayType
  944. >
  945. {};
  946. template
  947. <
  948. typename Point, typename MultiPoint, typename PointOut,
  949. overlay_type OverlayType,
  950. bool Reverse1, bool Reverse2
  951. >
  952. struct intersection_insert
  953. <
  954. Point, MultiPoint, PointOut, OverlayType,
  955. Reverse1, Reverse2,
  956. point_tag, multi_point_tag, point_tag,
  957. pointlike_tag, pointlike_tag, pointlike_tag
  958. > : detail::overlay::point_multipoint_point
  959. <
  960. Point, MultiPoint, PointOut, OverlayType
  961. >
  962. {};
  963. template
  964. <
  965. typename MultiPoint1, typename MultiPoint2, typename PointOut,
  966. overlay_type OverlayType,
  967. bool Reverse1, bool Reverse2
  968. >
  969. struct intersection_insert
  970. <
  971. MultiPoint1, MultiPoint2, PointOut, OverlayType,
  972. Reverse1, Reverse2,
  973. multi_point_tag, multi_point_tag, point_tag,
  974. pointlike_tag, pointlike_tag, pointlike_tag
  975. > : detail::overlay::multipoint_multipoint_point
  976. <
  977. MultiPoint1, MultiPoint2, PointOut, OverlayType
  978. >
  979. {};
  980. template
  981. <
  982. typename PointLike1, typename PointLike2, typename TupledOut,
  983. overlay_type OverlayType,
  984. bool Reverse1, bool Reverse2,
  985. typename TagIn1, typename TagIn2
  986. >
  987. struct intersection_insert
  988. <
  989. PointLike1, PointLike2, TupledOut, OverlayType,
  990. Reverse1, Reverse2,
  991. TagIn1, TagIn2, detail::intersection::tupled_output_tag,
  992. pointlike_tag, pointlike_tag, detail::intersection::tupled_output_tag
  993. >
  994. : detail::intersection::expect_output_p<PointLike1, PointLike2, TupledOut>
  995. {
  996. // NOTE: The order of geometries in TupledOut tuple/pair must correspond to the order
  997. // of iterators in OutputIterators tuple/pair.
  998. template
  999. <
  1000. typename RobustPolicy, typename OutputIterators, typename Strategy
  1001. >
  1002. static inline OutputIterators apply(PointLike1 const& pointlike1,
  1003. PointLike2 const& pointlike2,
  1004. RobustPolicy const& robust_policy,
  1005. OutputIterators oits,
  1006. Strategy const& strategy)
  1007. {
  1008. namespace bgt = boost::geometry::tuples;
  1009. static const bool out_point_index = bgt::find_index_if
  1010. <
  1011. TupledOut, geometry::detail::is_tag_same_as_pred<point_tag>::template pred
  1012. >::value;
  1013. bgt::get<out_point_index>(oits) = intersection_insert
  1014. <
  1015. PointLike1, PointLike2,
  1016. typename bgt::element
  1017. <
  1018. out_point_index, TupledOut
  1019. >::type,
  1020. OverlayType
  1021. >::apply(pointlike1, pointlike2, robust_policy,
  1022. bgt::get<out_point_index>(oits),
  1023. strategy);
  1024. return oits;
  1025. }
  1026. };
  1027. // dispatch for difference/intersection of pointlike-linear geometries
  1028. template
  1029. <
  1030. typename Point, typename Linear, typename PointOut,
  1031. overlay_type OverlayType,
  1032. bool Reverse1, bool Reverse2,
  1033. typename Tag
  1034. >
  1035. struct intersection_insert
  1036. <
  1037. Point, Linear, PointOut, OverlayType,
  1038. Reverse1, Reverse2,
  1039. point_tag, Tag, point_tag,
  1040. pointlike_tag, linear_tag, pointlike_tag
  1041. > : detail_dispatch::overlay::pointlike_linear_point
  1042. <
  1043. Point, Linear, PointOut, OverlayType,
  1044. point_tag, typename tag_cast<Tag, segment_tag, linear_tag>::type
  1045. >
  1046. {};
  1047. template
  1048. <
  1049. typename MultiPoint, typename Linear, typename PointOut,
  1050. overlay_type OverlayType,
  1051. bool Reverse1, bool Reverse2,
  1052. typename Tag
  1053. >
  1054. struct intersection_insert
  1055. <
  1056. MultiPoint, Linear, PointOut, OverlayType,
  1057. Reverse1, Reverse2,
  1058. multi_point_tag, Tag, point_tag,
  1059. pointlike_tag, linear_tag, pointlike_tag
  1060. > : detail_dispatch::overlay::pointlike_linear_point
  1061. <
  1062. MultiPoint, Linear, PointOut, OverlayType,
  1063. multi_point_tag,
  1064. typename tag_cast<Tag, segment_tag, linear_tag>::type
  1065. >
  1066. {};
  1067. // This specialization is needed because intersection() reverses the arguments
  1068. // for MultiPoint/Linestring combination.
  1069. template
  1070. <
  1071. typename Linestring, typename MultiPoint, typename PointOut,
  1072. bool Reverse1, bool Reverse2
  1073. >
  1074. struct intersection_insert
  1075. <
  1076. Linestring, MultiPoint, PointOut, overlay_intersection,
  1077. Reverse1, Reverse2,
  1078. linestring_tag, multi_point_tag, point_tag,
  1079. linear_tag, pointlike_tag, pointlike_tag
  1080. >
  1081. {
  1082. template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  1083. static inline OutputIterator apply(Linestring const& linestring,
  1084. MultiPoint const& multipoint,
  1085. RobustPolicy const& robust_policy,
  1086. OutputIterator out,
  1087. Strategy const& strategy)
  1088. {
  1089. return detail_dispatch::overlay::pointlike_linear_point
  1090. <
  1091. MultiPoint, Linestring, PointOut, overlay_intersection,
  1092. multi_point_tag, linear_tag
  1093. >::apply(multipoint, linestring, robust_policy, out, strategy);
  1094. }
  1095. };
  1096. template
  1097. <
  1098. typename PointLike, typename Linear, typename TupledOut,
  1099. overlay_type OverlayType,
  1100. bool Reverse1, bool Reverse2,
  1101. typename TagIn1, typename TagIn2
  1102. >
  1103. struct intersection_insert
  1104. <
  1105. PointLike, Linear, TupledOut, OverlayType,
  1106. Reverse1, Reverse2,
  1107. TagIn1, TagIn2, detail::intersection::tupled_output_tag,
  1108. pointlike_tag, linear_tag, detail::intersection::tupled_output_tag
  1109. >
  1110. // Reuse the implementation for PointLike/PointLike.
  1111. : intersection_insert
  1112. <
  1113. PointLike, Linear, TupledOut, OverlayType,
  1114. Reverse1, Reverse2,
  1115. TagIn1, TagIn2, detail::intersection::tupled_output_tag,
  1116. pointlike_tag, pointlike_tag, detail::intersection::tupled_output_tag
  1117. >
  1118. {};
  1119. // This specialization is needed because intersection() reverses the arguments
  1120. // for MultiPoint/Linestring combination.
  1121. template
  1122. <
  1123. typename Linestring, typename MultiPoint, typename TupledOut,
  1124. bool Reverse1, bool Reverse2
  1125. >
  1126. struct intersection_insert
  1127. <
  1128. Linestring, MultiPoint, TupledOut, overlay_intersection,
  1129. Reverse1, Reverse2,
  1130. linestring_tag, multi_point_tag, detail::intersection::tupled_output_tag,
  1131. linear_tag, pointlike_tag, detail::intersection::tupled_output_tag
  1132. >
  1133. {
  1134. template <typename RobustPolicy, typename OutputIterators, typename Strategy>
  1135. static inline OutputIterators apply(Linestring const& linestring,
  1136. MultiPoint const& multipoint,
  1137. RobustPolicy const& robust_policy,
  1138. OutputIterators out,
  1139. Strategy const& strategy)
  1140. {
  1141. return intersection_insert
  1142. <
  1143. MultiPoint, Linestring, TupledOut, overlay_intersection
  1144. >::apply(multipoint, linestring, robust_policy, out, strategy);
  1145. }
  1146. };
  1147. // dispatch for difference/intersection of pointlike-areal geometries
  1148. template
  1149. <
  1150. typename Point, typename Areal, typename PointOut,
  1151. overlay_type OverlayType,
  1152. bool Reverse1, bool Reverse2,
  1153. typename ArealTag
  1154. >
  1155. struct intersection_insert
  1156. <
  1157. Point, Areal, PointOut, OverlayType,
  1158. Reverse1, Reverse2,
  1159. point_tag, ArealTag, point_tag,
  1160. pointlike_tag, areal_tag, pointlike_tag
  1161. > : detail_dispatch::overlay::pointlike_areal_point
  1162. <
  1163. Point, Areal, PointOut, OverlayType,
  1164. point_tag, ArealTag
  1165. >
  1166. {};
  1167. template
  1168. <
  1169. typename MultiPoint, typename Areal, typename PointOut,
  1170. overlay_type OverlayType,
  1171. bool Reverse1, bool Reverse2,
  1172. typename ArealTag
  1173. >
  1174. struct intersection_insert
  1175. <
  1176. MultiPoint, Areal, PointOut, OverlayType,
  1177. Reverse1, Reverse2,
  1178. multi_point_tag, ArealTag, point_tag,
  1179. pointlike_tag, areal_tag, pointlike_tag
  1180. > : detail_dispatch::overlay::pointlike_areal_point
  1181. <
  1182. MultiPoint, Areal, PointOut, OverlayType,
  1183. multi_point_tag, ArealTag
  1184. >
  1185. {};
  1186. // This specialization is needed because intersection() reverses the arguments
  1187. // for MultiPoint/Ring and MultiPoint/Polygon combinations.
  1188. template
  1189. <
  1190. typename Areal, typename MultiPoint, typename PointOut,
  1191. bool Reverse1, bool Reverse2,
  1192. typename ArealTag
  1193. >
  1194. struct intersection_insert
  1195. <
  1196. Areal, MultiPoint, PointOut, overlay_intersection,
  1197. Reverse1, Reverse2,
  1198. ArealTag, multi_point_tag, point_tag,
  1199. areal_tag, pointlike_tag, pointlike_tag
  1200. >
  1201. {
  1202. template <typename RobustPolicy, typename OutputIterator, typename Strategy>
  1203. static inline OutputIterator apply(Areal const& areal,
  1204. MultiPoint const& multipoint,
  1205. RobustPolicy const& robust_policy,
  1206. OutputIterator out,
  1207. Strategy const& strategy)
  1208. {
  1209. return detail_dispatch::overlay::pointlike_areal_point
  1210. <
  1211. MultiPoint, Areal, PointOut, overlay_intersection,
  1212. multi_point_tag, ArealTag
  1213. >::apply(multipoint, areal, robust_policy, out, strategy);
  1214. }
  1215. };
  1216. template
  1217. <
  1218. typename PointLike, typename Areal, typename TupledOut,
  1219. overlay_type OverlayType,
  1220. bool Reverse1, bool Reverse2,
  1221. typename TagIn1, typename TagIn2
  1222. >
  1223. struct intersection_insert
  1224. <
  1225. PointLike, Areal, TupledOut, OverlayType,
  1226. Reverse1, Reverse2,
  1227. TagIn1, TagIn2, detail::intersection::tupled_output_tag,
  1228. pointlike_tag, areal_tag, detail::intersection::tupled_output_tag
  1229. >
  1230. // Reuse the implementation for PointLike/PointLike.
  1231. : intersection_insert
  1232. <
  1233. PointLike, Areal, TupledOut, OverlayType,
  1234. Reverse1, Reverse2,
  1235. TagIn1, TagIn2, detail::intersection::tupled_output_tag,
  1236. pointlike_tag, pointlike_tag, detail::intersection::tupled_output_tag
  1237. >
  1238. {};
  1239. // This specialization is needed because intersection() reverses the arguments
  1240. // for MultiPoint/Ring and MultiPoint/Polygon combinations.
  1241. template
  1242. <
  1243. typename Areal, typename MultiPoint, typename TupledOut,
  1244. bool Reverse1, bool Reverse2,
  1245. typename TagIn1
  1246. >
  1247. struct intersection_insert
  1248. <
  1249. Areal, MultiPoint, TupledOut, overlay_intersection,
  1250. Reverse1, Reverse2,
  1251. TagIn1, multi_point_tag, detail::intersection::tupled_output_tag,
  1252. areal_tag, pointlike_tag, detail::intersection::tupled_output_tag
  1253. >
  1254. {
  1255. template <typename RobustPolicy, typename OutputIterators, typename Strategy>
  1256. static inline OutputIterators apply(Areal const& areal,
  1257. MultiPoint const& multipoint,
  1258. RobustPolicy const& robust_policy,
  1259. OutputIterators out,
  1260. Strategy const& strategy)
  1261. {
  1262. return intersection_insert
  1263. <
  1264. MultiPoint, Areal, TupledOut, overlay_intersection
  1265. >::apply(multipoint, areal, robust_policy, out, strategy);
  1266. }
  1267. };
  1268. template
  1269. <
  1270. typename Linestring, typename Polygon,
  1271. typename TupledOut,
  1272. overlay_type OverlayType,
  1273. bool ReverseLinestring, bool ReversePolygon
  1274. >
  1275. struct intersection_insert
  1276. <
  1277. Linestring, Polygon,
  1278. TupledOut,
  1279. OverlayType,
  1280. ReverseLinestring, ReversePolygon,
  1281. linestring_tag, polygon_tag, detail::intersection::tupled_output_tag,
  1282. linear_tag, areal_tag, detail::intersection::tupled_output_tag
  1283. > : detail::intersection::intersection_of_linestring_with_areal
  1284. <
  1285. ReversePolygon,
  1286. TupledOut,
  1287. OverlayType,
  1288. true
  1289. >
  1290. {};
  1291. template
  1292. <
  1293. typename Linestring, typename Ring,
  1294. typename TupledOut,
  1295. overlay_type OverlayType,
  1296. bool ReverseLinestring, bool ReverseRing
  1297. >
  1298. struct intersection_insert
  1299. <
  1300. Linestring, Ring,
  1301. TupledOut,
  1302. OverlayType,
  1303. ReverseLinestring, ReverseRing,
  1304. linestring_tag, ring_tag, detail::intersection::tupled_output_tag,
  1305. linear_tag, areal_tag, detail::intersection::tupled_output_tag
  1306. > : detail::intersection::intersection_of_linestring_with_areal
  1307. <
  1308. ReverseRing,
  1309. TupledOut,
  1310. OverlayType,
  1311. true
  1312. >
  1313. {};
  1314. } // namespace dispatch
  1315. #endif // DOXYGEN_NO_DISPATCH
  1316. #ifndef DOXYGEN_NO_DETAIL
  1317. namespace detail { namespace intersection
  1318. {
  1319. template
  1320. <
  1321. typename GeometryOut,
  1322. bool ReverseSecond,
  1323. overlay_type OverlayType,
  1324. typename Geometry1, typename Geometry2,
  1325. typename RobustPolicy,
  1326. typename OutputIterator,
  1327. typename Strategy
  1328. >
  1329. inline OutputIterator insert(Geometry1 const& geometry1,
  1330. Geometry2 const& geometry2,
  1331. RobustPolicy robust_policy,
  1332. OutputIterator out,
  1333. Strategy const& strategy)
  1334. {
  1335. return boost::mpl::if_c
  1336. <
  1337. geometry::reverse_dispatch<Geometry1, Geometry2>::type::value,
  1338. geometry::dispatch::intersection_insert_reversed
  1339. <
  1340. Geometry1, Geometry2,
  1341. GeometryOut,
  1342. OverlayType,
  1343. overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
  1344. overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value
  1345. >,
  1346. geometry::dispatch::intersection_insert
  1347. <
  1348. Geometry1, Geometry2,
  1349. GeometryOut,
  1350. OverlayType,
  1351. geometry::detail::overlay::do_reverse<geometry::point_order<Geometry1>::value>::value,
  1352. geometry::detail::overlay::do_reverse<geometry::point_order<Geometry2>::value, ReverseSecond>::value
  1353. >
  1354. >::type::apply(geometry1, geometry2, robust_policy, out, strategy);
  1355. }
  1356. /*!
  1357. \brief \brief_calc2{intersection} \brief_strategy
  1358. \ingroup intersection
  1359. \details \details_calc2{intersection_insert, spatial set theoretic intersection}
  1360. \brief_strategy. \details_insert{intersection}
  1361. \tparam GeometryOut \tparam_geometry{\p_l_or_c}
  1362. \tparam Geometry1 \tparam_geometry
  1363. \tparam Geometry2 \tparam_geometry
  1364. \tparam OutputIterator \tparam_out{\p_l_or_c}
  1365. \tparam Strategy \tparam_strategy_overlay
  1366. \param geometry1 \param_geometry
  1367. \param geometry2 \param_geometry
  1368. \param out \param_out{intersection}
  1369. \param strategy \param_strategy{intersection}
  1370. \return \return_out
  1371. \qbk{distinguish,with strategy}
  1372. \qbk{[include reference/algorithms/intersection.qbk]}
  1373. */
  1374. template
  1375. <
  1376. typename GeometryOut,
  1377. typename Geometry1,
  1378. typename Geometry2,
  1379. typename OutputIterator,
  1380. typename Strategy
  1381. >
  1382. inline OutputIterator intersection_insert(Geometry1 const& geometry1,
  1383. Geometry2 const& geometry2,
  1384. OutputIterator out,
  1385. Strategy const& strategy)
  1386. {
  1387. concepts::check<Geometry1 const>();
  1388. concepts::check<Geometry2 const>();
  1389. typedef typename geometry::rescale_overlay_policy_type
  1390. <
  1391. Geometry1,
  1392. Geometry2,
  1393. typename Strategy::cs_tag
  1394. >::type rescale_policy_type;
  1395. rescale_policy_type robust_policy
  1396. = geometry::get_rescale_policy<rescale_policy_type>(
  1397. geometry1, geometry2, strategy);
  1398. return detail::intersection::insert
  1399. <
  1400. GeometryOut, false, overlay_intersection
  1401. >(geometry1, geometry2, robust_policy, out, strategy);
  1402. }
  1403. /*!
  1404. \brief \brief_calc2{intersection}
  1405. \ingroup intersection
  1406. \details \details_calc2{intersection_insert, spatial set theoretic intersection}.
  1407. \details_insert{intersection}
  1408. \tparam GeometryOut \tparam_geometry{\p_l_or_c}
  1409. \tparam Geometry1 \tparam_geometry
  1410. \tparam Geometry2 \tparam_geometry
  1411. \tparam OutputIterator \tparam_out{\p_l_or_c}
  1412. \param geometry1 \param_geometry
  1413. \param geometry2 \param_geometry
  1414. \param out \param_out{intersection}
  1415. \return \return_out
  1416. \qbk{[include reference/algorithms/intersection.qbk]}
  1417. */
  1418. template
  1419. <
  1420. typename GeometryOut,
  1421. typename Geometry1,
  1422. typename Geometry2,
  1423. typename OutputIterator
  1424. >
  1425. inline OutputIterator intersection_insert(Geometry1 const& geometry1,
  1426. Geometry2 const& geometry2,
  1427. OutputIterator out)
  1428. {
  1429. concepts::check<Geometry1 const>();
  1430. concepts::check<Geometry2 const>();
  1431. typedef typename strategy::intersection::services::default_strategy
  1432. <
  1433. typename cs_tag<GeometryOut>::type
  1434. >::type strategy_type;
  1435. return intersection_insert<GeometryOut>(geometry1, geometry2, out,
  1436. strategy_type());
  1437. }
  1438. }} // namespace detail::intersection
  1439. #endif // DOXYGEN_NO_DETAIL
  1440. }} // namespace boost::geometry
  1441. #endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_INTERSECTION_INSERT_HPP