view release on metacpan or  search on metacpan

src/boost/geometry/algorithms/detail/overlay/assign_parents.hpp  view on Meta::CPAN

        if (first && outer.real_area < 0)
        {
            // Reverse arguments
            apply(inner, outer, false);
            return;
        }

        if (math::larger(outer.real_area, 0))
        {
            if (inner.real_area < 0 || m_check_for_orientation)
            {
                ring_info_type& inner_in_map = m_ring_map[inner.id];

                if (geometry::within(inner_in_map.point, outer.envelope)
                   && within_selected_input(inner_in_map, outer.id, m_geometry1, m_geometry2, m_collection)
                   )
                {
                    // Only assign parent if that parent is smaller (or if it is the first)
                    if (inner_in_map.parent.source_index == -1
                        || outer.abs_area < inner_in_map.parent_area)
                    {
                        inner_in_map.parent = outer.id;
                        inner_in_map.parent_area = outer.abs_area;
                    }
                }
            }
        }
    }
};




template
<
    typename Geometry1, typename Geometry2,
    typename RingCollection,
    typename RingMap
>
inline void assign_parents(Geometry1 const& geometry1,
            Geometry2 const& geometry2,
            RingCollection const& collection,
            RingMap& ring_map,
            bool check_for_orientation = false)
{
    typedef typename geometry::tag<Geometry1>::type tag1;
    typedef typename geometry::tag<Geometry2>::type tag2;

    typedef typename RingMap::mapped_type ring_info_type;
    typedef typename ring_info_type::point_type point_type;
    typedef model::box<point_type> box_type;

    typedef typename RingMap::iterator map_iterator_type;

    {
        typedef ring_info_helper<point_type> helper;
        typedef std::vector<helper> vector_type;
        typedef typename boost::range_iterator<vector_type const>::type vector_iterator_type;

#ifdef BOOST_GEOMETRY_TIME_OVERLAY
        boost::timer timer;
#endif


        std::size_t count_total = ring_map.size();
        std::size_t count_positive = 0;
        std::size_t index_positive = 0; // only used if count_positive>0
        std::size_t index = 0;

        // Copy to vector (with new approach this might be obsolete as well, using the map directly)
        vector_type vector(count_total);

        for (map_iterator_type it = boost::begin(ring_map);
            it != boost::end(ring_map); ++it, ++index)
        {
            vector[index] = helper(it->first, it->second.get_area());
            helper& item = vector[index];
            switch(it->first.source_index)
            {
                case 0 :
                    geometry::envelope(get_ring<tag1>::apply(it->first, geometry1),
                            item.envelope);
                    break;
                case 1 :
                    geometry::envelope(get_ring<tag2>::apply(it->first, geometry2),
                            item.envelope);
                    break;
                case 2 :
                    geometry::envelope(get_ring<void>::apply(it->first, collection),
                            item.envelope);
                    break;
            }
            if (item.real_area > 0)
            {
                count_positive++;
                index_positive = index;
            }
        }

#ifdef BOOST_GEOMETRY_TIME_OVERLAY
        std::cout << " ap: created helper vector: " << timer.elapsed() << std::endl;
#endif

        if (! check_for_orientation)
        {
            if (count_positive == count_total)
            {
                // Optimization for only positive rings
                // -> no assignment of parents or reversal necessary, ready here.
                return;
            }

            if (count_positive == 1)
            {
                // Optimization for one outer ring
                // -> assign this as parent to all others (all interior rings)
                // In unions, this is probably the most occuring case and gives
                //    a dramatic improvement (factor 5 for star_comb testcase)
                ring_identifier id_of_positive = vector[index_positive].id;
                ring_info_type& outer = ring_map[id_of_positive];
                std::size_t index = 0;
                for (vector_iterator_type it = boost::begin(vector);
                    it != boost::end(vector); ++it, ++index)
                {
                    if (index != index_positive)
                    {
                        ring_info_type& inner = ring_map[it->id];
                        inner.parent = id_of_positive;
                        outer.children.push_back(it->id);
                    }
                }
                return;
            }
        }

        assign_visitor
            <
                Geometry1, Geometry2,
                RingCollection, RingMap
            > visitor(geometry1, geometry2, collection, ring_map, check_for_orientation);

        geometry::partition
            <
                box_type, ring_info_helper_get_box, ring_info_helper_ovelaps_box
            >::apply(vector, visitor);

#ifdef BOOST_GEOMETRY_TIME_OVERLAY
        std::cout << " ap: quadradic loop: " << timer.elapsed() << std::endl;
        std::cout << " ap: check_for_orientation " << check_for_orientation << std::endl;
#endif
    }

    if (check_for_orientation)
    {
        for (map_iterator_type it = boost::begin(ring_map);
            it != boost::end(ring_map); ++it)
        {
            if (geometry::math::equals(it->second.get_area(), 0))
            {
                it->second.discarded = true;
            }
            else if (it->second.parent.source_index >= 0 && it->second.get_area() > 0)
            {
                // Discard positive inner ring with parent
                it->second.discarded = true;
                it->second.parent.source_index = -1;
            }
            else if (it->second.parent.source_index < 0 && it->second.get_area() < 0)
            {
                // Reverse negative ring without parent
                it->second.reversed = true;
            }
        }
    }

    // Assign childlist
    for (map_iterator_type it = boost::begin(ring_map);
        it != boost::end(ring_map); ++it)
    {
        if (it->second.parent.source_index >= 0)
        {
            ring_map[it->second.parent].children.push_back(it->first);
        }
    }
}

template
<
    typename Geometry,
    typename RingCollection,
    typename RingMap
>
inline void assign_parents(Geometry const& geometry,
            RingCollection const& collection,
            RingMap& ring_map,
            bool check_for_orientation)
{
    // Call it with an empty geometry
    // (ring_map should be empty for source_id==1)

    Geometry empty;
    assign_parents(geometry, empty, collection, ring_map, check_for_orientation);
}


}} // namespace detail::overlay
#endif // DOXYGEN_NO_DETAIL