// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
// Use, modification and distribution is subject to the Boost Software License,
// Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP
#include <boost/assert.hpp>
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/strategies/intersection.hpp>
#include <boost/geometry/algorithms/convert.hpp>
#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
#include <boost/geometry/geometries/segment.hpp>
namespace boost { namespace geometry
{
#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
class turn_info_exception : public geometry::exception
{
std::string message;
public:
// NOTE: "char" will be replaced by enum in future version
inline turn_info_exception(char const method)
{
message = "Boost.Geometry Turn exception: ";
message += method;
}
virtual ~turn_info_exception() throw()
{}
virtual char const* what() const throw()
{
return message.c_str();
}
};
#endif
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace overlay
{
struct base_turn_handler
{
// Returns true if both sides are opposite
static inline bool opposite(int side1, int side2)
{
// We cannot state side1 == -side2, because 0 == -0
// So either side1*side2==-1 or side1==-side2 && side1 != 0
return side1 * side2 == -1;
}
// Same side of a segment (not being 0)
static inline bool same(int side1, int side2)
{
return side1 * side2 == 1;
}
// Both continue
template <typename TurnInfo>
static inline void both(TurnInfo& ti, operation_type const op)
{
ti.operations[0].operation = op;
ti.operations[1].operation = op;
}
// If condition, first union/second intersection, else vice versa
template <typename TurnInfo>
static inline void ui_else_iu(bool condition, TurnInfo& ti)
{
ti.operations[0].operation = condition
? operation_union : operation_intersection;
ti.operations[1].operation = condition
? operation_intersection : operation_union;
}
// If condition, both union, else both intersection
template <typename TurnInfo>
static inline void uu_else_ii(bool condition, TurnInfo& ti)
{
both(ti, condition ? operation_union : operation_intersection);
}
};
template
<
typename TurnInfo,
typename SideStrategy
>
struct touch_interior : public base_turn_handler
{
// Index: 0, P is the interior, Q is touching and vice versa
template
<
int Index,
typename Point1,
typename Point2,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(
Point1 const& pi, Point1 const& pj, Point1 const& ,
Point2 const& qi, Point2 const& qj, Point2 const& qk,
TurnInfo& ti,
IntersectionInfo const& intersection_info,
DirInfo const& dir_info)
{
ti.method = method_touch_interior;
geometry::convert(intersection_info.intersections[0], ti.point);
// Both segments of q touch segment p somewhere in its interior
// 1) We know: if q comes from LEFT or RIGHT
// (i.e. dir_info.sides.get<Index,0>() == 1 or -1)
// 2) Important is: if q_k goes to LEFT, RIGHT, COLLINEAR
// and, if LEFT/COLL, if it is lying LEFT or RIGHT w.r.t. q_i
static int const index_p = Index;
static int const index_q = 1 - Index;
int const side_qi_p = dir_info.sides.template get<index_q, 0>();
int const side_qk_p = SideStrategy::apply(pi, pj, qk);
if (side_qi_p == -side_qk_p)
{
// Q crosses P from left->right or from right->left (test "ML1")
// Union: folow P (left->right) or Q (right->left)
// Intersection: other turn
int index = side_qk_p == -1 ? index_p : index_q;
ti.operations[index].operation = operation_union;
ti.operations[1 - index].operation = operation_intersection;
return;
}
int const side_qk_q = SideStrategy::apply(qi, qj, qk);
if (side_qi_p == -1 && side_qk_p == -1 && side_qk_q == 1)
{
// Q turns left on the right side of P (test "MR3")
// Both directions for "intersection"
both(ti, operation_intersection);
}
else if (side_qi_p == 1 && side_qk_p == 1 && side_qk_q == -1)
{
// Q turns right on the left side of P (test "ML3")
// Union: take both operation
// Intersection: skip
both(ti, operation_union);
}
else if (side_qi_p == side_qk_p && side_qi_p == side_qk_q)
{
// Q turns left on the left side of P (test "ML2")
// or Q turns right on the right side of P (test "MR2")
// Union: take left turn (Q if Q turns left, P if Q turns right)
// Intersection: other turn
int index = side_qk_q == 1 ? index_q : index_p;
ti.operations[index].operation = operation_union;
ti.operations[1 - index].operation = operation_intersection;
}
else if (side_qk_p == 0)
{
// Q intersects on interior of P and continues collinearly
if (side_qk_q == side_qi_p)
{
// Collinearly in the same direction
// (Q comes from left of P and turns left,
// OR Q comes from right of P and turns right)
// Omit intersection point.
// Union: just continue
// Intersection: just continue
both(ti, operation_continue);
}
else
{
// Opposite direction, which is never travelled.
// If Q turns left, P continues for intersection
// If Q turns right, P continues for union
ti.operations[Index].operation = side_qk_q == 1
? operation_intersection
: operation_union;
ti.operations[1 - Index].operation = operation_blocked;
}
}
else
{
// Should not occur!
ti.method = method_error;
}
}
};
template
<
typename TurnInfo,
typename SideStrategy
>
struct touch : public base_turn_handler
{
static inline bool between(int side1, int side2, int turn)
{
return side1 == side2 && ! opposite(side1, turn);
}
/*static inline void block_second(bool block, TurnInfo& ti)
{
if (block)
{
ti.operations[1].operation = operation_blocked;
}
}*/
template
<
typename Point1,
typename Point2,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(
Point1 const& pi, Point1 const& pj, Point1 const& pk,
Point2 const& qi, Point2 const& qj, Point2 const& qk,
TurnInfo& ti,
IntersectionInfo const& intersection_info,
DirInfo const& dir_info)
{
ti.method = method_touch;
geometry::convert(intersection_info.intersections[0], ti.point);
int const side_qi_p1 = dir_info.sides.template get<1, 0>();
int const side_qk_p1 = SideStrategy::apply(pi, pj, qk);
// If Qi and Qk are both at same side of Pi-Pj,
// or collinear (so: not opposite sides)
if (! opposite(side_qi_p1, side_qk_p1))
{
int const side_pk_q2 = SideStrategy::apply(qj, qk, pk);
int const side_pk_p = SideStrategy::apply(pi, pj, pk);
int const side_qk_q = SideStrategy::apply(qi, qj, qk);
bool const both_continue = side_pk_p == 0 && side_qk_q == 0;
bool const robustness_issue_in_continue = both_continue && side_pk_q2 != 0;
bool const q_turns_left = side_qk_q == 1;
bool const block_q = side_qk_p1 == 0
&& ! same(side_qi_p1, side_qk_q)
&& ! robustness_issue_in_continue
;
// If Pk at same side as Qi/Qk
// (the "or" is for collinear case)
// or Q is fully collinear && P turns not to left
if (side_pk_p == side_qi_p1
|| side_pk_p == side_qk_p1
|| (side_qi_p1 == 0 && side_qk_p1 == 0 && side_pk_p != -1)
)
{
// Collinear -> lines join, continue
// (#BRL2)
if (side_pk_q2 == 0 && ! block_q)
{
both(ti, operation_continue);
return;
}
int const side_pk_q1 = SideStrategy::apply(qi, qj, pk);
// Collinear opposite case -> block P
// (#BRL4, #BLR8)
if (side_pk_q1 == 0)
{
ti.operations[0].operation = operation_blocked;
// Q turns right -> union (both independent),
// Q turns left -> intersection
ti.operations[1].operation = block_q ? operation_blocked
: q_turns_left ? operation_intersection
: operation_union;
return;
}
// Pk between Qi and Qk
// (#BRL3, #BRL7)
if (between(side_pk_q1, side_pk_q2, side_qk_q))
{
ui_else_iu(q_turns_left, ti);
if (block_q)
{
ti.operations[1].operation = operation_blocked;
}
//block_second(block_q, ti);
return;
}
// Pk between Qk and P, so left of Qk (if Q turns right) and vv
// (#BRL1)
if (side_pk_q2 == -side_qk_q)
{
ui_else_iu(! q_turns_left, ti);
return;
}
//
// (#BRL5, #BRL9)
if (side_pk_q1 == -side_qk_q)
{
uu_else_ii(! q_turns_left, ti);
if (block_q)
{
ti.operations[1].operation = operation_blocked;
}
//block_second(block_q, ti);
return;
}
}
else
{
// Pk at other side than Qi/Pk
int const side_qk_q = SideStrategy::apply(qi, qj, qk);
bool const q_turns_left = side_qk_q == 1;
ti.operations[0].operation = q_turns_left
? operation_intersection
: operation_union;
ti.operations[1].operation = block_q
? operation_blocked
: side_qi_p1 == 1 || side_qk_p1 == 1
? operation_union
: operation_intersection;
return;
}
}
else
{
// From left to right or from right to left
int const side_pk_p = SideStrategy::apply(pi, pj, pk);
bool const right_to_left = side_qk_p1 == 1;
// If p turns into direction of qi (1,2)
if (side_pk_p == side_qi_p1)
{
int const side_pk_q1 = SideStrategy::apply(qi, qj, pk);
// Collinear opposite case -> block P
if (side_pk_q1 == 0)
{
ti.operations[0].operation = operation_blocked;
ti.operations[1].operation = right_to_left
? operation_union : operation_intersection;
return;
}
if (side_pk_q1 == side_qk_p1)
{
uu_else_ii(right_to_left, ti);
return;
}
}
// If p turns into direction of qk (4,5)
if (side_pk_p == side_qk_p1)
{
int const side_pk_q2 = SideStrategy::apply(qj, qk, pk);
// Collinear case -> lines join, continue
if (side_pk_q2 == 0)
{
both(ti, operation_continue);
return;
}
if (side_pk_q2 == side_qk_p1)
{
ui_else_iu(right_to_left, ti);
return;
}
}
// otherwise (3)
ui_else_iu(! right_to_left, ti);
return;
}
#ifdef BOOST_GEOMETRY_DEBUG_GET_TURNS
// Normally a robustness issue.
// TODO: more research if still occuring
std::cout << "Not yet handled" << std::endl
<< "pi " << get<0>(pi) << " , " << get<1>(pi)
<< " pj " << get<0>(pj) << " , " << get<1>(pj)
<< " pk " << get<0>(pk) << " , " << get<1>(pk)
<< std::endl
<< "qi " << get<0>(qi) << " , " << get<1>(qi)
<< " qj " << get<0>(qj) << " , " << get<1>(qj)
<< " qk " << get<0>(qk) << " , " << get<1>(qk)
<< std::endl;
#endif
}
};
template
<
typename TurnInfo,
typename SideStrategy
>
struct equal : public base_turn_handler
{
template
<
typename Point1,
typename Point2,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(
Point1 const& pi, Point1 const& pj, Point1 const& pk,
Point2 const& , Point2 const& qj, Point2 const& qk,
TurnInfo& ti,
IntersectionInfo const& intersection_info,
DirInfo const& )
{
ti.method = method_equal;
// Copy the SECOND intersection point
geometry::convert(intersection_info.intersections[1], ti.point);
int const side_pk_q2 = SideStrategy::apply(qj, qk, pk);
int const side_pk_p = SideStrategy::apply(pi, pj, pk);
int const side_qk_p = SideStrategy::apply(pi, pj, qk);
// If pk is collinear with qj-qk, they continue collinearly.
// This can be on either side of p1 (== q1), or collinear
// The second condition checks if they do not continue
// oppositely
if (side_pk_q2 == 0 && side_pk_p == side_qk_p)
{
both(ti, operation_continue);
return;
}
// If they turn to same side (not opposite sides)
if (! opposite(side_pk_p, side_qk_p))
{
int const side_pk_q2 = SideStrategy::apply(qj, qk, pk);
// If pk is left of q2 or collinear: p: union, q: intersection
ui_else_iu(side_pk_q2 != -1, ti);
}
else
{
// They turn opposite sides. If p turns left (or collinear),
// p: union, q: intersection
ui_else_iu(side_pk_p != -1, ti);
}
}
};
template
<
typename TurnInfo,
typename AssignPolicy
>
struct equal_opposite : public base_turn_handler
{
template
<
typename Point1,
typename Point2,
typename OutputIterator,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(Point1 const& pi, Point2 const& qi,
/* by value: */ TurnInfo tp,
OutputIterator& out,
IntersectionInfo const& intersection_info,
DirInfo const& dir_info)
{
// For equal-opposite segments, normally don't do anything.
if (AssignPolicy::include_opposite)
{
tp.method = method_equal;
for (int i = 0; i < 2; i++)
{
tp.operations[i].operation = operation_opposite;
}
for (unsigned int i = 0; i < intersection_info.count; i++)
{
geometry::convert(intersection_info.intersections[i], tp.point);
AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
*out++ = tp;
}
}
}
};
template
<
typename TurnInfo,
typename SideStrategy
>
struct collinear : public base_turn_handler
{
/*
arrival P pk//p1 qk//q1 product* case result
1 1 1 CLL1 ui
-1 1 -1 CLL2 iu
1 1 1 CLR1 ui
-1 -1 1 CLR2 ui
1 -1 -1 CRL1 iu
-1 1 -1 CRL2 iu
1 -1 -1 CRR1 iu
-1 -1 1 CRR2 ui
1 0 0 CC1 cc
-1 0 0 CC2 cc
*product = arrival * (pk//p1 or qk//q1)
Stated otherwise:
- if P arrives: look at turn P
- if Q arrives: look at turn Q
- if P arrives and P turns left: union for P
- if P arrives and P turns right: intersection for P
- if Q arrives and Q turns left: union for Q (=intersection for P)
- if Q arrives and Q turns right: intersection for Q (=union for P)
ROBUSTNESS: p and q are collinear, so you would expect
that side qk//p1 == pk//q1. But that is not always the case
in near-epsilon ranges. Then decision logic is different.
If p arrives, q is further, so the angle qk//p1 is (normally)
more precise than pk//p1
*/
template
<
typename Point1,
typename Point2,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(
Point1 const& pi, Point1 const& pj, Point1 const& pk,
Point2 const& qi, Point2 const& qj, Point2 const& qk,
TurnInfo& ti,
IntersectionInfo const& intersection_info,
DirInfo const& dir_info)
{
ti.method = method_collinear;
geometry::convert(intersection_info.intersections[1], ti.point);
int const arrival = dir_info.arrival[0];
// Should not be 0, this is checked before
BOOST_ASSERT(arrival != 0);
int const side_p = SideStrategy::apply(pi, pj, pk);
int const side_q = SideStrategy::apply(qi, qj, qk);
// If p arrives, use p, else use q
int const side_p_or_q = arrival == 1
? side_p
: side_q
;
int const side_pk = SideStrategy::apply(qi, qj, pk);
int const side_qk = SideStrategy::apply(pi, pj, qk);
// See comments above,
// resulting in a strange sort of mathematic rule here:
// The arrival-info multiplied by the relevant side
// delivers a consistent result.
int const product = arrival * side_p_or_q;
// Robustness: side_p is supposed to be equal to side_pk (because p/q are collinear)
// and side_q to side_qk
bool const robustness_issue = side_pk != side_p || side_qk != side_q;
if (robustness_issue)
{
handle_robustness(ti, arrival, side_p, side_q, side_pk, side_qk);
}
else if(product == 0)
{
both(ti, operation_continue);
}
else
{
ui_else_iu(product == 1, ti);
}
}
static inline void handle_robustness(TurnInfo& ti, int arrival,
int side_p, int side_q, int side_pk, int side_qk)
{
// We take the longer one, i.e. if q arrives in p (arrival == -1),
// then p exceeds q and we should take p for a union...
bool use_p_for_union = arrival == -1;
// ... unless one of the sides consistently directs to the other side
int const consistent_side_p = side_p == side_pk ? side_p : 0;
int const consistent_side_q = side_q == side_qk ? side_q : 0;
if (arrival == -1 && (consistent_side_p == -1 || consistent_side_q == 1))
{
use_p_for_union = false;
}
if (arrival == 1 && (consistent_side_p == 1 || consistent_side_q == -1))
{
use_p_for_union = true;
}
//std::cout << "ROBUSTNESS -> Collinear "
// << " arr: " << arrival
// << " dir: " << side_p << " " << side_q
// << " rev: " << side_pk << " " << side_qk
// << " cst: " << cside_p << " " << cside_q
// << std::boolalpha << " " << use_p_for_union
// << std::endl;
ui_else_iu(use_p_for_union, ti);
}
};
template
<
typename TurnInfo,
typename SideStrategy,
typename AssignPolicy
>
struct collinear_opposite : public base_turn_handler
{
private :
/*
arrival P arrival Q pk//p1 qk//q1 case result2 result
--------------------------------------------------------------
1 1 1 -1 CLO1 ix xu
1 1 1 0 CLO2 ix (xx)
1 1 1 1 CLO3 ix xi
1 1 0 -1 CCO1 (xx) xu
1 1 0 0 CCO2 (xx) (xx)
1 1 0 1 CCO3 (xx) xi
1 1 -1 -1 CRO1 ux xu
1 1 -1 0 CRO2 ux (xx)
1 1 -1 1 CRO3 ux xi
-1 1 -1 CXO1 xu
-1 1 0 CXO2 (xx)
-1 1 1 CXO3 xi
1 -1 1 CXO1 ix
1 -1 0 CXO2 (xx)
1 -1 -1 CXO3 ux
*/
template
<
int Index,
typename Point,
typename IntersectionInfo
>
static inline bool set_tp(Point const& ri, Point const& rj, Point const& rk,
TurnInfo& tp, IntersectionInfo const& intersection_info)
{
int const side_rk_r = SideStrategy::apply(ri, rj, rk);
operation_type blocked = operation_blocked;
switch(side_rk_r)
{
case 1 :
// Turning left on opposite collinear: intersection
tp.operations[Index].operation = operation_intersection;
break;
case -1 :
// Turning right on opposite collinear: union
tp.operations[Index].operation = operation_union;
break;
case 0 :
// No turn on opposite collinear: block, do not traverse
// But this "xx" is usually ignored, it is useless to include
// two operations blocked, so the whole point does not need
// to be generated.
// So return false to indicate nothing is to be done.
if (AssignPolicy::include_opposite)
{
tp.operations[Index].operation = operation_opposite;
blocked = operation_opposite;
}
else
{
return false;
}
break;
}
// The other direction is always blocked when collinear opposite
tp.operations[1 - Index].operation = blocked;
// If P arrives within Q, set info on P (which is done above, index=0),
// this turn-info belongs to the second intersection point, index=1
// (see e.g. figure CLO1)
geometry::convert(intersection_info.intersections[1 - Index], tp.point);
return true;
}
public:
template
<
typename Point1,
typename Point2,
typename OutputIterator,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(
Point1 const& pi, Point1 const& pj, Point1 const& pk,
Point2 const& qi, Point2 const& qj, Point2 const& qk,
// Opposite collinear can deliver 2 intersection points,
TurnInfo const& tp_model,
OutputIterator& out,
IntersectionInfo const& intersection_info,
DirInfo const& dir_info)
{
TurnInfo tp = tp_model;
tp.method = method_collinear;
// If P arrives within Q, there is a turn dependent on P
if (dir_info.arrival[0] == 1
&& set_tp<0>(pi, pj, pk, tp, intersection_info))
{
AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
*out++ = tp;
}
// If Q arrives within P, there is a turn dependent on Q
if (dir_info.arrival[1] == 1
&& set_tp<1>(qi, qj, qk, tp, intersection_info))
{
AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
*out++ = tp;
}
if (AssignPolicy::include_opposite)
{
// Handle cases not yet handled above
if ((dir_info.arrival[1] == -1 && dir_info.arrival[0] == 0)
|| (dir_info.arrival[0] == -1 && dir_info.arrival[1] == 0))
{
for (int i = 0; i < 2; i++)
{
tp.operations[i].operation = operation_opposite;
}
for (unsigned int i = 0; i < intersection_info.count; i++)
{
geometry::convert(intersection_info.intersections[i], tp.point);
AssignPolicy::apply(tp, pi, qi, intersection_info, dir_info);
*out++ = tp;
}
}
}
}
};
template
<
typename TurnInfo,
typename SideStrategy
>
struct crosses : public base_turn_handler
{
template
<
typename Point1,
typename Point2,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(
Point1 const& , Point1 const& , Point1 const& ,
Point2 const& , Point2 const& , Point2 const& ,
TurnInfo& ti,
IntersectionInfo const& intersection_info,
DirInfo const& dir_info)
{
ti.method = method_crosses;
geometry::convert(intersection_info.intersections[0], ti.point);
// In all casees:
// If Q crosses P from left to right
// Union: take P
// Intersection: take Q
// Otherwise: vice versa
int const side_qi_p1 = dir_info.sides.template get<1, 0>();
int const index = side_qi_p1 == 1 ? 0 : 1;
ti.operations[index].operation = operation_union;
ti.operations[1 - index].operation = operation_intersection;
}
};
template<typename TurnInfo>
struct only_convert
{
template<typename IntersectionInfo>
static inline void apply(TurnInfo& ti, IntersectionInfo const& intersection_info)
{
ti.method = method_collinear;
geometry::convert(intersection_info.intersections[0], ti.point);
ti.operations[0].operation = operation_continue;
ti.operations[1].operation = operation_continue;
}
};
/*!
\brief Policy doing nothing
\details get_turn_info can have an optional policy to get/assign some
extra information. By default it does not, and this class
is that default.
*/
struct assign_null_policy
{
static bool const include_no_turn = false;
static bool const include_degenerate = false;
static bool const include_opposite = false;
template
<
typename Info,
typename Point1,
typename Point2,
typename IntersectionInfo,
typename DirInfo
>
static inline void apply(Info& , Point1 const& , Point2 const&, IntersectionInfo const&, DirInfo const&)
{}
};
/*!
\brief Turn information: intersection point, method, and turn information
\details Information necessary for traversal phase (a phase
of the overlay process). The information is gathered during the
get_turns (segment intersection) phase.
\tparam Point1 point type of first segment
\tparam Point2 point type of second segment
\tparam TurnInfo type of class getting intersection and turn info
\tparam AssignPolicy policy to assign extra info,
e.g. to calculate distance from segment's first points
to intersection points.
It also defines if a certain class of points
(degenerate, non-turns) should be included.
*/
template
<
typename Point1,
typename Point2,
typename TurnInfo,
typename AssignPolicy
>
struct get_turn_info
{
typedef strategy_intersection
<
typename cs_tag<typename TurnInfo::point_type>::type,
Point1,
Point2,
typename TurnInfo::point_type
> si;
typedef typename si::segment_intersection_strategy_type strategy;
// Intersect pi-pj with qi-qj
// The points pk and qk are only used do determine more information
// about the turn.
template <typename OutputIterator>
static inline OutputIterator apply(
Point1 const& pi, Point1 const& pj, Point1 const& pk,
Point2 const& qi, Point2 const& qj, Point2 const& qk,
TurnInfo const& tp_model,
OutputIterator out)
{
typedef model::referring_segment<Point1 const> segment_type1;
typedef model::referring_segment<Point1 const> segment_type2;
segment_type1 p1(pi, pj), p2(pj, pk);
segment_type2 q1(qi, qj), q2(qj, qk);
typename strategy::return_type result = strategy::apply(p1, q1);
char const method = result.template get<1>().how;
// Copy, to copy possibly extended fields
TurnInfo tp = tp_model;
// Select method and apply
switch(method)
{
case 'a' : // collinear, "at"
case 'f' : // collinear, "from"
case 's' : // starts from the middle
if (AssignPolicy::include_no_turn
&& result.template get<0>().count > 0)
{
only_convert<TurnInfo>::apply(tp,
result.template get<0>());
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
case 'd' : // disjoint: never do anything
break;
case 'm' :
{
typedef touch_interior
<
TurnInfo,
typename si::side_strategy_type
> policy;
// If Q (1) arrives (1)
if (result.template get<1>().arrival[1] == 1)
{
policy::template apply<0>(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
}
else
{
// Swap p/q
policy::template apply<1>(qi, qj, qk, pi, pj, pk,
tp, result.template get<0>(), result.template get<1>());
}
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
case 'i' :
{
typedef crosses
<
TurnInfo,
typename si::side_strategy_type
> policy;
policy::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
case 't' :
{
// Both touch (both arrive there)
typedef touch
<
TurnInfo,
typename si::side_strategy_type
> policy;
policy::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
break;
case 'e':
{
if (! result.template get<1>().opposite)
{
// Both equal
// or collinear-and-ending at intersection point
typedef equal
<
TurnInfo,
typename si::side_strategy_type
> policy;
policy::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
else
{
equal_opposite
<
TurnInfo,
AssignPolicy
>::apply(pi, qi,
tp, out, result.template get<0>(), result.template get<1>());
}
}
break;
case 'c' :
{
// Collinear
if (! result.template get<1>().opposite)
{
if (result.template get<1>().arrival[0] == 0)
{
// Collinear, but similar thus handled as equal
equal
<
TurnInfo,
typename si::side_strategy_type
>::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
// override assigned method
tp.method = method_collinear;
}
else
{
collinear
<
TurnInfo,
typename si::side_strategy_type
>::apply(pi, pj, pk, qi, qj, qk,
tp, result.template get<0>(), result.template get<1>());
}
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
else
{
collinear_opposite
<
TurnInfo,
typename si::side_strategy_type,
AssignPolicy
>::apply(pi, pj, pk, qi, qj, qk,
tp, out, result.template get<0>(), result.template get<1>());
}
}
break;
case '0' :
{
// degenerate points
if (AssignPolicy::include_degenerate)
{
only_convert<TurnInfo>::apply(tp, result.template get<0>());
AssignPolicy::apply(tp, pi, qi, result.template get<0>(), result.template get<1>());
*out++ = tp;
}
}
break;
default :
{
#if ! defined(BOOST_GEOMETRY_OVERLAY_NO_THROW)
throw turn_info_exception(method);
#endif
}
break;
}
return out;
}
};
}} // namespace detail::overlay
#endif //DOXYGEN_NO_DETAIL
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_OVERLAY_GET_TURN_INFO_HPP