// Boost.Geometry (aka GGL, Generic Geometry Library)
// Copyright (c) 2007-2012 Barend Gehrels, Amsterdam, the Netherlands.
// This file was modified by Oracle on 2013-2022.
// Modifications copyright (c) 2013-2022 Oracle and/or its affiliates.
// Contributed and/or modified by Adam Wulkiewicz, on behalf of Oracle
// 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_RELATE_LINEAR_LINEAR_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP
#include <algorithm>
#include <boost/core/ignore_unused.hpp>
#include <boost/range/size.hpp>
#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/util/condition.hpp>
#include <boost/geometry/util/range.hpp>
#include <boost/geometry/algorithms/detail/sub_range.hpp>
#include <boost/geometry/algorithms/detail/single_geometry.hpp>
#include <boost/geometry/algorithms/detail/relate/point_geometry.hpp>
#include <boost/geometry/algorithms/detail/relate/result.hpp>
#include <boost/geometry/algorithms/detail/relate/turns.hpp>
#include <boost/geometry/algorithms/detail/relate/boundary_checker.hpp>
#include <boost/geometry/algorithms/detail/relate/follow_helpers.hpp>
#include <boost/geometry/geometries/helper_geometry.hpp>
namespace boost { namespace geometry
{
#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace relate {
template <typename Result, typename BoundaryChecker, bool TransposeResult>
class disjoint_linestring_pred
{
public:
disjoint_linestring_pred(Result & res,
BoundaryChecker const& boundary_checker)
: m_result(res)
, m_boundary_checker(boundary_checker)
, m_flags(0)
{
if ( ! may_update<interior, exterior, '1', TransposeResult>(m_result) )
{
m_flags |= 1;
}
if ( ! may_update<boundary, exterior, '0', TransposeResult>(m_result) )
{
m_flags |= 2;
}
}
template <typename Linestring>
bool operator()(Linestring const& linestring)
{
if ( m_flags == 3 )
{
return false;
}
std::size_t const count = boost::size(linestring);
// invalid input
if ( count < 2 )
{
// ignore
// TODO: throw an exception?
return true;
}
// point-like linestring
if ( count == 2
&& equals::equals_point_point(range::front(linestring),
range::back(linestring),
m_boundary_checker.strategy()) )
{
update<interior, exterior, '0', TransposeResult>(m_result);
}
else
{
update<interior, exterior, '1', TransposeResult>(m_result);
m_flags |= 1;
// check if there is a boundary
if (m_flags < 2
&& (m_boundary_checker.is_endpoint_boundary(range::front(linestring))
|| m_boundary_checker.is_endpoint_boundary(range::back(linestring))))
{
update<boundary, exterior, '0', TransposeResult>(m_result);
m_flags |= 2;
}
}
return m_flags != 3
&& ! m_result.interrupt;
}
private:
Result & m_result;
BoundaryChecker const& m_boundary_checker;
unsigned m_flags;
};
template <typename Geometry1, typename Geometry2>
struct linear_linear
{
static const bool interruption_enabled = true;
template <typename Result, typename Strategy>
static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
Result & result,
Strategy const& strategy)
{
boundary_checker<Geometry1, Strategy> boundary_checker1(geometry1, strategy);
boundary_checker<Geometry2, Strategy> boundary_checker2(geometry2, strategy);
apply(geometry1, geometry2, boundary_checker1, boundary_checker2, result, strategy);
}
template <typename BoundaryChecker1, typename BoundaryChecker2, typename Result, typename Strategy>
static inline void apply(Geometry1 const& geometry1, Geometry2 const& geometry2,
BoundaryChecker1 const& boundary_checker1,
BoundaryChecker2 const& boundary_checker2,
Result & result,
Strategy const& strategy)
{
// The result should be FFFFFFFFF
update<exterior, exterior, result_dimension<Geometry1>::value>(result);// FFFFFFFFd, d in [1,9] or T
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
return;
// get and analyse turns
using turn_type = typename turns::get_turns
<
Geometry1, Geometry2
>::template turn_info_type<Strategy>::type;
std::vector<turn_type> turns;
interrupt_policy_linear_linear<Result> interrupt_policy(result);
turns::get_turns
<
Geometry1,
Geometry2,
detail::get_turns::get_turn_info_type<Geometry1, Geometry2, turns::assign_policy<true> >
>::apply(turns, geometry1, geometry2, interrupt_policy, strategy);
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
return;
disjoint_linestring_pred<Result, BoundaryChecker1, false> pred1(result, boundary_checker1);
for_each_disjoint_geometry_if<0, Geometry1>::apply(turns.begin(), turns.end(), geometry1, pred1);
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
return;
disjoint_linestring_pred<Result, BoundaryChecker2, true> pred2(result, boundary_checker2);
for_each_disjoint_geometry_if<1, Geometry2>::apply(turns.begin(), turns.end(), geometry2, pred2);
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
return;
if ( turns.empty() )
return;
// TODO: turns must be sorted and followed only if it's possible to go out and in on the same point
// for linear geometries union operation must be detected which I guess would be quite often
if ( may_update<interior, interior, '1'>(result)
|| may_update<interior, boundary, '0'>(result)
|| may_update<interior, exterior, '1'>(result)
|| may_update<boundary, interior, '0'>(result)
|| may_update<boundary, boundary, '0'>(result)
|| may_update<boundary, exterior, '0'>(result) )
{
using less_t = turns::less<0, turns::less_op_linear_linear<0>, Strategy>;
std::sort(turns.begin(), turns.end(), less_t());
turns_analyser<turn_type, 0> analyser;
analyse_each_turn(result, analyser,
turns.begin(), turns.end(),
geometry1, geometry2,
boundary_checker1, boundary_checker2);
}
if ( BOOST_GEOMETRY_CONDITION( result.interrupt ) )
return;
if ( may_update<interior, interior, '1', true>(result)
|| may_update<interior, boundary, '0', true>(result)
|| may_update<interior, exterior, '1', true>(result)
|| may_update<boundary, interior, '0', true>(result)
|| may_update<boundary, boundary, '0', true>(result)
|| may_update<boundary, exterior, '0', true>(result) )
{
using less_t = turns::less<1, turns::less_op_linear_linear<1>, Strategy>;
std::sort(turns.begin(), turns.end(), less_t());
turns_analyser<turn_type, 1> analyser;
analyse_each_turn(result, analyser,
turns.begin(), turns.end(),
geometry2, geometry1,
boundary_checker2, boundary_checker1);
}
}
template <typename Result>
class interrupt_policy_linear_linear
{
public:
static bool const enabled = true;
explicit interrupt_policy_linear_linear(Result & result)
: m_result(result)
{}
// TODO: since we update result for some operations here, we may not do it in the analyser!
template <typename Range>
inline bool apply(Range const& turns)
{
for (auto it = boost::begin(turns) ; it != boost::end(turns) ; ++it)
{
if ( it->operations[0].operation == overlay::operation_intersection
|| it->operations[1].operation == overlay::operation_intersection )
{
update<interior, interior, '1'>(m_result);
}
else if ( ( it->operations[0].operation == overlay::operation_union
|| it->operations[0].operation == overlay::operation_blocked
|| it->operations[1].operation == overlay::operation_union
|| it->operations[1].operation == overlay::operation_blocked )
&& it->operations[0].position == overlay::position_middle
&& it->operations[1].position == overlay::position_middle )
{
// TODO: here we could also check the boundaries and set IB,BI,BB at this point
update<interior, interior, '0'>(m_result);
}
}
return m_result.interrupt;
}
private:
Result & m_result;
};
// This analyser should be used like Input or SinglePass Iterator
template <typename TurnInfo, std::size_t OpId>
class turns_analyser
{
typedef typename TurnInfo::point_type turn_point_type;
static const std::size_t op_id = OpId;
static const std::size_t other_op_id = (OpId + 1) % 2;
static const bool transpose_result = OpId != 0;
public:
turns_analyser()
: m_previous_turn_ptr(NULL)
, m_previous_operation(overlay::operation_none)
, m_degenerated_turn_ptr(NULL)
, m_collinear_spike_exit(false)
{}
template <typename Result,
typename TurnIt,
typename Geometry,
typename OtherGeometry,
typename BoundaryChecker,
typename OtherBoundaryChecker>
void apply(Result & res, TurnIt it,
Geometry const& geometry,
OtherGeometry const& other_geometry,
BoundaryChecker const& boundary_checker,
OtherBoundaryChecker const& other_boundary_checker)
{
overlay::operation_type const op = it->operations[op_id].operation;
segment_identifier const& seg_id = it->operations[op_id].seg_id;
bool const first_in_range = m_seg_watcher.update(seg_id);
if ( op != overlay::operation_union
&& op != overlay::operation_intersection
&& op != overlay::operation_blocked )
{
// degenerated turn
if ( op == overlay::operation_continue
&& it->method == overlay::method_none
&& m_exit_watcher.is_outside(*it)
/*&& ( m_exit_watcher.get_exit_operation() == overlay::operation_none
|| ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(), *it) )*/ )
{
// TODO: rewrite the above condition
// WARNING! For spikes the above condition may be TRUE
// When degenerated turns are be marked in a different way than c,c/c
// different condition will be checked
handle_degenerated(res, *it,
geometry, other_geometry,
boundary_checker, other_boundary_checker,
first_in_range);
// TODO: not elegant solution! should be rewritten.
if ( it->operations[op_id].position == overlay::position_back )
{
m_previous_operation = overlay::operation_blocked;
m_exit_watcher.reset_detected_exit();
}
}
return;
}
// reset
m_degenerated_turn_ptr = NULL;
// handle possible exit
bool fake_enter_detected = false;
if ( m_exit_watcher.get_exit_operation() == overlay::operation_union )
{
// real exit point - may be multiple
// we know that we entered and now we exit
if ( ! turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(),
*it,
boundary_checker.strategy()) )
{
m_exit_watcher.reset_detected_exit();
// not the last IP
update<interior, exterior, '1', transpose_result>(res);
}
// fake exit point, reset state
else if ( op == overlay::operation_intersection )
{
m_exit_watcher.reset_detected_exit();
fake_enter_detected = true;
}
}
else if ( m_exit_watcher.get_exit_operation() == overlay::operation_blocked )
{
// ignore multiple BLOCKs
if ( op == overlay::operation_blocked )
return;
if ( op == overlay::operation_intersection
&& turn_on_the_same_ip<op_id>(m_exit_watcher.get_exit_turn(),
*it,
boundary_checker.strategy()) )
{
fake_enter_detected = true;
}
m_exit_watcher.reset_detected_exit();
}
// i/i, i/x, i/u
if ( op == overlay::operation_intersection )
{
bool const was_outside = m_exit_watcher.is_outside();
m_exit_watcher.enter(*it);
// interiors overlaps
update<interior, interior, '1', transpose_result>(res);
bool const this_b = it->operations[op_id].position == overlay::position_front // ignore spikes!
&& is_ip_on_boundary(it->point, it->operations[op_id],
boundary_checker);
// going inside on boundary point
// may be front only
if ( this_b )
{
// may be front and back
bool const other_b = is_ip_on_boundary(it->point, it->operations[other_op_id],
other_boundary_checker);
// it's also the boundary of the other geometry
if ( other_b )
{
update<boundary, boundary, '0', transpose_result>(res);
}
else
{
update<boundary, interior, '0', transpose_result>(res);
}
}
// going inside on non-boundary point
else
{
// if we didn't enter in the past, we were outside
if ( was_outside
&& ! fake_enter_detected
&& it->operations[op_id].position != overlay::position_front
&& ! m_collinear_spike_exit )
{
update<interior, exterior, '1', transpose_result>(res);
// if it's the first IP then the first point is outside
if ( first_in_range )
{
bool const front_b = boundary_checker.is_endpoint_boundary(
range::front(sub_range(geometry, seg_id)));
// if there is a boundary on the first point
if ( front_b )
{
update<boundary, exterior, '0', transpose_result>(res);
}
}
}
}
m_collinear_spike_exit = false;
}
// u/i, u/u, u/x, x/i, x/u, x/x
else if ( op == overlay::operation_union || op == overlay::operation_blocked )
{
// TODO: is exit watcher still needed?
// couldn't is_collinear and some going inside counter be used instead?
bool const is_collinear = it->operations[op_id].is_collinear;
bool const was_outside = m_exit_watcher.is_outside()
&& m_exit_watcher.get_exit_operation() == overlay::operation_none;
// TODO: move the above condition into the exit_watcher?
// to exit we must be currently inside and the current segment must be collinear
if ( !was_outside && is_collinear )
{
m_exit_watcher.exit(*it, false);
// if the position is not set to back it must be a spike
if ( it->operations[op_id].position != overlay::position_back )
{
m_collinear_spike_exit = true;
}
}
bool const op_blocked = op == overlay::operation_blocked;
// we're inside and going out from inside
// possibly going out right now
if ( ! was_outside && is_collinear )
{
if ( op_blocked
&& it->operations[op_id].position == overlay::position_back ) // ignore spikes!
{
// check if this is indeed the boundary point
// NOTE: is_ip_on_boundary<>() should be called here but the result will be the same
if (boundary_checker.is_endpoint_boundary(it->point))
{
// may be front and back
bool const other_b = is_ip_on_boundary(it->point,
it->operations[other_op_id],
other_boundary_checker);
// it's also the boundary of the other geometry
if ( other_b )
{
update<boundary, boundary, '0', transpose_result>(res);
}
else
{
update<boundary, interior, '0', transpose_result>(res);
}
}
}
}
// we're outside or intersects some segment from the outside
else
{
// if we are truly outside
if ( was_outside
&& it->operations[op_id].position != overlay::position_front
&& ! m_collinear_spike_exit
/*&& !is_collinear*/ )
{
update<interior, exterior, '1', transpose_result>(res);
}
// boundaries don't overlap - just an optimization
if ( it->method == overlay::method_crosses )
{
// the L1 is going from one side of the L2 to the other through the point
update<interior, interior, '0', transpose_result>(res);
// it's the first point in range
if ( first_in_range )
{
bool const front_b = boundary_checker.is_endpoint_boundary(
range::front(sub_range(geometry, seg_id)));
// if there is a boundary on the first point
if ( front_b )
{
update<boundary, exterior, '0', transpose_result>(res);
}
}
}
// method other than crosses, check more conditions
else
{
bool const this_b = is_ip_on_boundary(it->point,
it->operations[op_id],
boundary_checker);
bool const other_b = is_ip_on_boundary(it->point,
it->operations[other_op_id],
other_boundary_checker);
// if current IP is on boundary of the geometry
if ( this_b )
{
// it's also the boundary of the other geometry
if ( other_b )
{
update<boundary, boundary, '0', transpose_result>(res);
}
else
{
update<boundary, interior, '0', transpose_result>(res);
}
}
// if current IP is not on boundary of the geometry
else
{
// it's also the boundary of the other geometry
if ( other_b )
{
update<interior, boundary, '0', transpose_result>(res);
}
else
{
update<interior, interior, '0', transpose_result>(res);
}
}
// first IP on the last segment point - this means that the first point is outside
if ( first_in_range
&& ( !this_b || op_blocked )
&& was_outside
&& it->operations[op_id].position != overlay::position_front
&& ! m_collinear_spike_exit
/*&& !is_collinear*/ )
{
bool const front_b = boundary_checker.is_endpoint_boundary(
range::front(sub_range(geometry, seg_id)));
// if there is a boundary on the first point
if ( front_b )
{
update<boundary, exterior, '0', transpose_result>(res);
}
}
}
}
}
// store ref to previously analysed (valid) turn
m_previous_turn_ptr = boost::addressof(*it);
// and previously analysed (valid) operation
m_previous_operation = op;
}
// Called for last
template <typename Result,
typename TurnIt,
typename Geometry,
typename OtherGeometry,
typename BoundaryChecker,
typename OtherBoundaryChecker>
void apply(Result & res,
TurnIt first, TurnIt last,
Geometry const& geometry,
OtherGeometry const& /*other_geometry*/,
BoundaryChecker const& boundary_checker,
OtherBoundaryChecker const& /*other_boundary_checker*/)
{
boost::ignore_unused(first, last);
//BOOST_GEOMETRY_ASSERT( first != last );
// here, the possible exit is the real one
// we know that we entered and now we exit
if ( /*m_exit_watcher.get_exit_operation() == overlay::operation_union // THIS CHECK IS REDUNDANT
||*/ m_previous_operation == overlay::operation_union
|| m_degenerated_turn_ptr )
{
update<interior, exterior, '1', transpose_result>(res);
BOOST_GEOMETRY_ASSERT(first != last);
const TurnInfo * turn_ptr = NULL;
if ( m_degenerated_turn_ptr )
turn_ptr = m_degenerated_turn_ptr;
else if ( m_previous_turn_ptr )
turn_ptr = m_previous_turn_ptr;
if ( turn_ptr )
{
segment_identifier const& prev_seg_id = turn_ptr->operations[op_id].seg_id;
//BOOST_GEOMETRY_ASSERT(!boost::empty(sub_range(geometry, prev_seg_id)));
bool const prev_back_b = boundary_checker.is_endpoint_boundary(
range::back(sub_range(geometry, prev_seg_id)));
// if there is a boundary on the last point
if ( prev_back_b )
{
update<boundary, exterior, '0', transpose_result>(res);
}
}
}
// Just in case,
// reset exit watcher before the analysis of the next Linestring
// note that if there are some enters stored there may be some error above
m_exit_watcher.reset();
m_previous_turn_ptr = NULL;
m_previous_operation = overlay::operation_none;
m_degenerated_turn_ptr = NULL;
// actually if this is set to true here there is some error
// in get_turns_ll or relate_ll, an assert could be checked here
m_collinear_spike_exit = false;
}
template <typename Result,
typename Turn,
typename Geometry,
typename OtherGeometry,
typename BoundaryChecker,
typename OtherBoundaryChecker>
void handle_degenerated(Result & res,
Turn const& turn,
Geometry const& geometry,
OtherGeometry const& other_geometry,
BoundaryChecker const& boundary_checker,
OtherBoundaryChecker const& other_boundary_checker,
bool first_in_range)
{
auto const& ls1 = detail::single_geometry(geometry, turn.operations[op_id].seg_id);
auto const& ls2 = detail::single_geometry(other_geometry, turn.operations[other_op_id].seg_id);
// only one of those should be true:
if ( turn.operations[op_id].position == overlay::position_front )
{
// valid, point-sized
if ( boost::size(ls2) == 2 )
{
bool const front_b = boundary_checker.is_endpoint_boundary(turn.point);
if ( front_b )
{
update<boundary, interior, '0', transpose_result>(res);
}
else
{
update<interior, interior, '0', transpose_result>(res);
}
// operation 'c' should be last for the same IP so we know that the next point won't be the same
update<interior, exterior, '1', transpose_result>(res);
m_degenerated_turn_ptr = boost::addressof(turn);
}
}
else if ( turn.operations[op_id].position == overlay::position_back )
{
// valid, point-sized
if ( boost::size(ls2) == 2 )
{
update<interior, exterior, '1', transpose_result>(res);
bool const back_b = boundary_checker.is_endpoint_boundary(turn.point);
if ( back_b )
{
update<boundary, interior, '0', transpose_result>(res);
}
else
{
update<interior, interior, '0', transpose_result>(res);
}
if ( first_in_range )
{
//BOOST_GEOMETRY_ASSERT(!boost::empty(ls1));
bool const front_b = boundary_checker.is_endpoint_boundary(
range::front(ls1));
if ( front_b )
{
update<boundary, exterior, '0', transpose_result>(res);
}
}
}
}
else if ( turn.operations[op_id].position == overlay::position_middle
&& turn.operations[other_op_id].position == overlay::position_middle )
{
update<interior, interior, '0', transpose_result>(res);
// here we don't know which one is degenerated
bool const is_point1 = boost::size(ls1) == 2
&& equals::equals_point_point(range::front(ls1),
range::back(ls1),
boundary_checker.strategy());
bool const is_point2 = boost::size(ls2) == 2
&& equals::equals_point_point(range::front(ls2),
range::back(ls2),
other_boundary_checker.strategy());
// if the second one is degenerated
if ( !is_point1 && is_point2 )
{
update<interior, exterior, '1', transpose_result>(res);
if ( first_in_range )
{
//BOOST_GEOMETRY_ASSERT(!boost::empty(ls1));
bool const front_b = boundary_checker.is_endpoint_boundary(
range::front(ls1));
if ( front_b )
{
update<boundary, exterior, '0', transpose_result>(res);
}
}
m_degenerated_turn_ptr = boost::addressof(turn);
}
}
// NOTE: other.position == front and other.position == back
// will be handled later, for the other geometry
}
private:
exit_watcher<TurnInfo, OpId> m_exit_watcher;
segment_watcher<same_single> m_seg_watcher;
const TurnInfo * m_previous_turn_ptr;
overlay::operation_type m_previous_operation;
const TurnInfo * m_degenerated_turn_ptr;
bool m_collinear_spike_exit;
};
template <typename Result,
typename TurnIt,
typename Analyser,
typename Geometry,
typename OtherGeometry,
typename BoundaryChecker,
typename OtherBoundaryChecker>
static inline void analyse_each_turn(Result & res,
Analyser & analyser,
TurnIt first, TurnIt last,
Geometry const& geometry,
OtherGeometry const& other_geometry,
BoundaryChecker const& boundary_checker,
OtherBoundaryChecker const& other_boundary_checker)
{
if ( first == last )
return;
for ( TurnIt it = first ; it != last ; ++it )
{
analyser.apply(res, it,
geometry, other_geometry,
boundary_checker, other_boundary_checker);
if ( BOOST_GEOMETRY_CONDITION( res.interrupt ) )
return;
}
analyser.apply(res, first, last,
geometry, other_geometry,
boundary_checker, other_boundary_checker);
}
};
}} // namespace detail::relate
#endif // DOXYGEN_NO_DETAIL
}} // namespace boost::geometry
#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RELATE_LINEAR_LINEAR_HPP