algorithms/detail/partition.hpp

// Boost.Geometry (aka GGL, Generic Geometry Library)

// Copyright (c) 2011 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_PARTITION_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_PARTITION_HPP

#include <vector>
#include <boost/geometry/algorithms/assign.hpp>
#include <boost/range/algorithm/copy.hpp>
#include <boost/geometry/core/coordinate_type.hpp>

namespace boost { namespace geometry
{


namespace detail { namespace partition
{

typedef std::vector<std::size_t> index_vector_type;

template <int Dimension, typename Box>
inline void divide_box(Box const& box, Box& lower_box, Box& upper_box)
{
    typedef typename coordinate_type<Box>::type ctype;

    // Divide input box into two parts, e.g. left/right
    ctype two = 2;
    ctype mid = (geometry::get<min_corner, Dimension>(box)
            + geometry::get<max_corner, Dimension>(box)) / two;

    lower_box = box;
    upper_box = box;
    geometry::set<max_corner, Dimension>(lower_box, mid);
    geometry::set<min_corner, Dimension>(upper_box, mid);
}

// Divide collection into three subsets: lower, upper and oversized (not-fitting)
// (lower == left or bottom, upper == right or top)
template <typename OverlapsPolicy, typename InputCollection, typename Box>
static inline void divide_into_subsets(Box const& lower_box, Box const& upper_box,
        InputCollection const& collection,
        index_vector_type const& input,
        index_vector_type& lower,
        index_vector_type& upper,
        index_vector_type& exceeding)
{
    typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;

    for(index_iterator_type it = boost::begin(input);
        it != boost::end(input);
        ++it)
    {
        bool const lower_overlapping = OverlapsPolicy::apply(lower_box, collection[*it]);
        bool const upper_overlapping = OverlapsPolicy::apply(upper_box, collection[*it]);

        if (lower_overlapping && upper_overlapping)
        {
            exceeding.push_back(*it);
        }
        else if (lower_overlapping)
        {
            lower.push_back(*it);
        }
        else if (upper_overlapping)
        {
            upper.push_back(*it);
        }
        else
        {
            // Is nowhere! Should not occur!
            BOOST_ASSERT(true);
        }
    }
}


// Match collection with itself
template <typename InputCollection, typename Policy>
static inline void handle_one(InputCollection const& collection,
        index_vector_type const& input,
        Policy& policy)
{
    typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
    // Quadratic behaviour at lowest level (lowest quad, or all exceeding)
    for(index_iterator_type it1 = boost::begin(input); it1 != boost::end(input); ++it1)
    {
        index_iterator_type it2 = it1;
        for(++it2; it2 != boost::end(input); ++it2)
        {
            policy.apply(collection[*it1], collection[*it2]);
        }
    }
}

// Match collection 1 with collection 2
template <typename InputCollection, typename Policy>
static inline void handle_two(
        InputCollection const& collection1, index_vector_type const& input1,
        InputCollection const& collection2, index_vector_type const& input2,
        Policy& policy)
{
    typedef boost::range_iterator<index_vector_type const>::type index_iterator_type;
    for(index_iterator_type it1 = boost::begin(input1); it1 != boost::end(input1); ++it1)
    {
        for(index_iterator_type it2 = boost::begin(input2); it2 != boost::end(input2); ++it2)
        {
            policy.apply(collection1[*it1], collection2[*it2]);
        }
    }
}


template
<
    int Dimension,
    typename Box,
    typename OverlapsPolicy,
    typename VisitBoxPolicy
>
class partition_one_collection
{
    typedef std::vector<std::size_t> index_vector_type;
    typedef typename coordinate_type<Box>::type ctype;
    typedef partition_one_collection
            <
                1 - Dimension,
                Box,
                OverlapsPolicy,
                VisitBoxPolicy
            > sub_divide;

    template <typename InputCollection, typename Policy>
    static inline void next_level(Box const& box,
            InputCollection const& collection,
            index_vector_type const& input,
            int level, int min_elements,
            Policy& policy, VisitBoxPolicy& box_policy)
    {
        if (boost::size(input) > 0)
        {
            if (boost::size(input) > min_elements && level < 100)
            {
                sub_divide::apply(box, collection, input, level + 1, min_elements, policy, box_policy);
            }
            else
            {
                handle_one(collection, input, policy);
            }
        }
    }

public :
    template <typename InputCollection, typename Policy>
    static inline void apply(Box const& box,
            InputCollection const& collection,
            index_vector_type const& input,
            int level,
            int min_elements,
            Policy& policy, VisitBoxPolicy& box_policy)
    {
        box_policy.apply(box, level);

        Box lower_box, upper_box;
        divide_box<Dimension>(box, lower_box, upper_box);

        index_vector_type lower, upper, exceeding;
        divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection, input, lower, upper, exceeding);

        if (boost::size(exceeding) > 0)
        {
            // All what is not fitting a partition should be combined
            // with each other, and with all which is fitting.
            handle_one(collection, exceeding, policy);
            handle_two(collection, exceeding, collection, lower, policy);
            handle_two(collection, exceeding, collection, upper, policy);
        }

        // Recursively call operation both parts
        next_level(lower_box, collection, lower, level, min_elements, policy, box_policy);
        next_level(upper_box, collection, upper, level, min_elements, policy, box_policy);
    }
};


template
<
    int Dimension,
    typename Box,
    typename OverlapsPolicy,
    typename VisitBoxPolicy
>
class partition_two_collections
{
    typedef std::vector<std::size_t> index_vector_type;
    typedef typename coordinate_type<Box>::type ctype;
    typedef partition_two_collections
            <
                1 - Dimension,
                Box,
                OverlapsPolicy,
                VisitBoxPolicy
            > sub_divide;

    template <typename InputCollection, typename Policy>
    static inline void next_level(Box const& box,
            InputCollection const& collection1, index_vector_type const& input1,
            InputCollection const& collection2, index_vector_type const& input2,
            int level, int min_elements,
            Policy& policy, VisitBoxPolicy& box_policy)
    {
        if (boost::size(input1) > 0 && boost::size(input2) > 0)
        {
            if (boost::size(input1) > min_elements
                && boost::size(input2) > min_elements
                && level < 100)
            {
                sub_divide::apply(box, collection1, input1, collection2, input2, level + 1, min_elements, policy, box_policy);
            }
            else
            {
                box_policy.apply(box, level + 1);
                handle_two(collection1, input1, collection2, input2, policy);
            }
        }
    }

public :
    template <typename InputCollection, typename Policy>
    static inline void apply(Box const& box,
            InputCollection const& collection1, index_vector_type const& input1,
            InputCollection const& collection2, index_vector_type const& input2,
            int level,
            int min_elements,
            Policy& policy, VisitBoxPolicy& box_policy)
    {
        box_policy.apply(box, level);

        Box lower_box, upper_box;
        divide_box<Dimension>(box, lower_box, upper_box);

        index_vector_type lower1, upper1, exceeding1;
        index_vector_type lower2, upper2, exceeding2;
        divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection1, input1, lower1, upper1, exceeding1);
        divide_into_subsets<OverlapsPolicy>(lower_box, upper_box, collection2, input2, lower2, upper2, exceeding2);

        if (boost::size(exceeding1) > 0)
        {
            // All exceeding from 1 with 2:
            handle_two(collection1, exceeding1, collection2, exceeding2, policy);

            // All exceeding from 1 with lower and upper of 2:
            handle_two(collection1, exceeding1, collection2, lower2, policy);
            handle_two(collection1, exceeding1, collection2, upper2, policy);
        }
        if (boost::size(exceeding2) > 0)
        {
            // All exceeding from 2 with lower and upper of 1:
            handle_two(collection1, lower1, collection2, exceeding2, policy);
            handle_two(collection1, upper1, collection2, exceeding2, policy);
        }

        next_level(lower_box, collection1, lower1, collection2, lower2, level, min_elements, policy, box_policy);
        next_level(upper_box, collection1, upper1, collection2, upper2, level, min_elements, policy, box_policy);
    }
};


}} // namespace detail::partition

struct visit_no_policy
{
    template <typename Box>
    static inline void apply(Box const&, int )
    {}
};


template
<
    typename Box,
    typename ExpandPolicy,
    typename OverlapsPolicy,
    typename VisitBoxPolicy = visit_no_policy
>
class partition
{
    typedef std::vector<std::size_t> index_vector_type;

    template <typename InputCollection>
    static inline void expand_to_collection(InputCollection const& collection, Box& total, index_vector_type& index_vector)
    {
        std::size_t index = 0;
        for(typename boost::range_iterator<InputCollection const>::type it
            = boost::begin(collection);
            it != boost::end(collection);
            ++it, ++index)
        {
            ExpandPolicy::apply(total, *it);
            index_vector.push_back(index);
        }
    }


public :
    template <typename InputCollection, typename VisitPolicy>
    static inline void apply(InputCollection const& collection,
            VisitPolicy& visitor,
            int min_elements = 16,
            VisitBoxPolicy box_visitor = visit_no_policy()
            )
    {
        if (boost::size(collection) > min_elements)
        {
            index_vector_type index_vector;
            Box total;
            assign_inverse(total);
            expand_to_collection(collection, total, index_vector);

            detail::partition::partition_one_collection
                <
                    0, Box,
                    OverlapsPolicy,
                    VisitBoxPolicy
                >::apply(total, collection, index_vector, 0, min_elements, visitor, box_visitor);
        }
        else
        {
            typedef typename boost::range_iterator<InputCollection const>::type iterator_type;
            for(iterator_type it1 = boost::begin(collection); it1 != boost::end(collection); ++it1)
            {
                iterator_type it2 = it1;
                for(++it2; it2 != boost::end(collection); ++it2)
                {
                    visitor.apply(*it1, *it2);
                }
            }
        }
    }

    template <typename InputCollection, typename VisitPolicy>
    static inline void apply(InputCollection const& collection1,
                InputCollection const& collection2,
                VisitPolicy& visitor,
                int min_elements = 16,
                VisitBoxPolicy box_visitor = visit_no_policy()
                )
    {
        if (boost::size(collection1) > min_elements && boost::size(collection2) > min_elements)
        {
            index_vector_type index_vector1, index_vector2;
            Box total;
            assign_inverse(total);
            expand_to_collection(collection1, total, index_vector1);
            expand_to_collection(collection2, total, index_vector2);

            detail::partition::partition_two_collections
                <
                    0, Box, OverlapsPolicy, VisitBoxPolicy
                >::apply(total,
                    collection1, index_vector1,
                    collection2, index_vector2,
                    0, min_elements, visitor, box_visitor);
        }
        else
        {
            typedef typename boost::range_iterator<InputCollection const>::type iterator_type;
            for(iterator_type it1 = boost::begin(collection1); it1 != boost::end(collection1); ++it1)
            {
                for(iterator_type it2 = boost::begin(collection2); it2 != boost::end(collection2); ++it2)
                {
                    visitor.apply(*it1, *it2);
                }
            }
        }
    }

};


}} // namespace boost::geometry


#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_RING_IDENTIFIER_HPP