Subject: [Boost-commit] svn:boost r60591 - in sandbox/geometry/boost/geometry/algorithms: . detail/equals
From: barend.gehrels_at_[hidden]
Date: 2010-03-14 18:21:49
Author: barendgehrels
Date: 2010-03-14 18:21:49 EDT (Sun, 14 Mar 2010)
New Revision: 60591
URL: http://svn.boost.org/trac/boost/changeset/60591
Log:
Reworked equals
Added:
sandbox/geometry/boost/geometry/algorithms/detail/equals/
sandbox/geometry/boost/geometry/algorithms/detail/equals/collect_vectors.hpp (contents, props changed)
Text files modified:
sandbox/geometry/boost/geometry/algorithms/equals.hpp | 346 +++++++++++----------------------------
1 files changed, 100 insertions(+), 246 deletions(-)
Added: sandbox/geometry/boost/geometry/algorithms/detail/equals/collect_vectors.hpp
==============================================================================
--- (empty file)
+++ sandbox/geometry/boost/geometry/algorithms/detail/equals/collect_vectors.hpp 2010-03-14 18:21:49 EDT (Sun, 14 Mar 2010)
@@ -0,0 +1,299 @@
+// Boost.Geometry (aka GGL, Generic Geometry Library)
+//
+// Copyright Barend Gehrels 2010, Geodan, 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_EQUALS_COLLECT_VECTORS_HPP
+#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
+
+#include <algorithm>
+#include <deque>
+
+#include <boost/numeric/conversion/cast.hpp>
+#include <boost/range.hpp>
+#include <boost/range/functions.hpp>
+#include <boost/range/metafunctions.hpp>
+
+
+#include <boost/geometry/multi/core/tags.hpp>
+
+#include <boost/geometry/core/cs.hpp>
+#include <boost/geometry/core/interior_rings.hpp>
+#include <boost/geometry/geometries/concepts/check.hpp>
+#include <boost/geometry/strategies/side.hpp>
+
+#include <boost/geometry/util/select_most_precise.hpp>
+
+
+
+namespace boost { namespace geometry
+{
+
+// TODO: if Boost.LA of Emil Dotchevski is accepted, adapt this
+template <typename T>
+struct collected_vector
+{
+ typedef T type;
+
+ collected_vector()
+ {}
+
+ collected_vector(T const& px, T const& py,
+ T const& pdx, T const& pdy)
+ : x(px)
+ , y(py)
+ , dx(pdx)
+ , dy(pdy)
+ {}
+
+ T x, y;
+ T dx, dy;
+ bool collinear;
+
+ bool operator<(collected_vector<T> const& other) const
+ {
+ if (math::equals(x, other.x))
+ {
+ if (math::equals(y, other.y))
+ {
+ if (math::equals(dx, other.dx))
+ {
+ return dy < other.dy;
+ }
+ return dx < other.dx;
+ }
+ return y < other.y;
+ }
+ return x < other.x;
+ }
+
+ inline bool same_direction(collected_vector<T> const& other) const
+ {
+ return math::equals(dx, other.dx)
+ && math::equals(dy, other.dy);
+ }
+
+ inline bool operator==(collected_vector<T> const& other) const
+ {
+ return math::equals(x, other.x)
+ && math::equals(y, other.y)
+ && same_direction(other);
+ }
+};
+
+
+#ifndef DOXYGEN_NO_DETAIL
+namespace detail { namespace collect_vectors
+{
+
+
+template <typename Range, typename Collection>
+struct range_collect_vectors
+{
+ typedef typename boost::range_value<Collection>::type item_type;
+ typedef typename item_type::type calculation_type;
+
+ static inline void apply(Collection& collection, Range const& range)
+ {
+ if (boost::size(range) < 2)
+ {
+ return;
+ }
+
+ typedef typename boost::range_iterator<Range const>::type iterator;
+
+ bool first = true;
+ iterator it = boost::begin(range);
+
+ for (iterator prev = it++;
+ it != boost::end(range);
+ prev = it++)
+ {
+ typename boost::range_value<Collection>::type v;
+
+ v.x = get<0>(*prev);
+ v.y = get<1>(*prev);
+ v.dx = get<0>(*it) - v.x;
+ v.dy = get<1>(*it) - v.y;
+
+ // Normalize the vector -> this results in points+direction
+ // and is comparible between geometries
+ calculation_type magnitude = sqrt(
+ boost::numeric_cast<calculation_type>(v.dx * v.dx + v.dy * v.dy));
+
+ // Avoid non-duplicate points (AND division by zero)
+ if (magnitude > 0)
+ {
+ v.dx /= magnitude;
+ v.dy /= magnitude;
+
+ // Avoid non-direction changing points
+ if (first || ! v.same_direction(collection.back()))
+ {
+ collection.push_back(v);
+ }
+ first = false;
+ }
+ }
+ // TODO: if first one has same direction as last one, remove first one...
+ }
+};
+
+
+template <typename Box, typename Collection>
+struct box_collect_vectors
+{
+ // Calculate on coordinate type, but if it is integer,
+ // then use double
+ typedef typename boost::range_value<Collection>::type item_type;
+ typedef typename item_type::type calculation_type;
+
+ static inline void apply(Collection& collection, Box const& box)
+ {
+ typename point_type<Box>::type lower_left, lower_right,
+ upper_left, upper_right;
+ assign_box_corners(box, lower_left, lower_right,
+ upper_left, upper_right);
+
+ typedef typename boost::range_value<Collection>::type item;
+
+ collection.push_back(item(get<0>(lower_left), get<1>(lower_left), 0, 1));
+ collection.push_back(item(get<0>(upper_left), get<1>(upper_left), 1, 0));
+ collection.push_back(item(get<0>(upper_right), get<1>(upper_right), 0, -1));
+ collection.push_back(item(get<0>(lower_right), get<1>(lower_right), -1, 0));
+ }
+};
+
+
+template <typename Polygon, typename Collection>
+struct polygon_collect_vectors
+{
+ static inline void apply(Collection& collection, Polygon const& polygon)
+ {
+ typedef typename geometry::ring_type<Polygon>::type ring_type;
+
+ typedef range_collect_vectors<ring_type, Collection> per_range;
+ per_range::apply(collection, exterior_ring(polygon));
+
+ for (typename boost::range_iterator
+ <
+ typename interior_type<Polygon>::type const
+ >::type it = boost::begin(interior_rings(polygon));
+ it != boost::end(interior_rings(polygon));
+ ++it)
+ {
+ per_range::apply(collection, *it);
+ }
+ }
+};
+
+
+template <typename MultiGeometry, typename Collection, typename SinglePolicy>
+struct multi_collect_vectors
+{
+ static inline void apply(Collection& collection, MultiGeometry const& multi)
+ {
+ for (typename boost::range_iterator<MultiGeometry const>::type
+ it = boost::begin(multi);
+ it != boost::end(multi);
+ ++it)
+ {
+ SinglePolicy::apply(collection, *it);
+ }
+ }
+};
+
+
+}} // namespace detail::collect_vectors
+#endif // DOXYGEN_NO_DETAIL
+
+
+
+#ifndef DOXYGEN_NO_DISPATCH
+namespace dispatch
+{
+
+
+template
+<
+ typename Tag,
+ typename Collection,
+ typename Geometry
+>
+struct collect_vectors
+{
+ static inline void apply(Collection&, Geometry const&)
+ {}
+};
+
+
+template <typename Collection, typename Box>
+struct collect_vectors<box_tag, Collection, Box>
+ : detail::collect_vectors::box_collect_vectors<Box, Collection>
+{};
+
+
+
+template <typename Collection, typename Ring>
+struct collect_vectors<ring_tag, Collection, Ring>
+ : detail::collect_vectors::range_collect_vectors<Ring, Collection>
+{};
+
+
+template <typename Collection, typename LineString>
+struct collect_vectors<linestring_tag, Collection, LineString>
+ : detail::collect_vectors::range_collect_vectors<LineString, Collection>
+{};
+
+
+template <typename Collection, typename Polygon>
+struct collect_vectors<polygon_tag, Collection, Polygon>
+ : detail::collect_vectors::polygon_collect_vectors<Polygon, Collection>
+{};
+
+
+template <typename Collection, typename MultiPolygon>
+struct collect_vectors<multi_polygon_tag, Collection, MultiPolygon>
+ : detail::collect_vectors::multi_collect_vectors
+ <
+ MultiPolygon,
+ Collection,
+ detail::collect_vectors::polygon_collect_vectors
+ <
+ typename boost::range_value<MultiPolygon>::type,
+ Collection
+ >
+ >
+{};
+
+
+
+} // namespace dispatch
+#endif
+
+
+/*!
+ \ingroup collect_vectors
+ \tparam Geometry geometry type
+ \param geometry the geometry to make collect_vectors
+*/
+template <typename Collection, typename Geometry>
+inline void collect_vectors(Collection& collection, Geometry const& geometry)
+{
+ concept::check<Geometry const>();
+
+ dispatch::collect_vectors
+ <
+ typename tag<Geometry>::type,
+ Collection,
+ Geometry
+ >::apply(collection, geometry);
+}
+
+
+}} // namespace boost::geometry
+
+
+#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_EQUALS_COLLECT_VECTORS_HPP
Modified: sandbox/geometry/boost/geometry/algorithms/equals.hpp
==============================================================================
--- sandbox/geometry/boost/geometry/algorithms/equals.hpp (original)
+++ sandbox/geometry/boost/geometry/algorithms/equals.hpp 2010-03-14 18:21:49 EDT (Sun, 14 Mar 2010)
@@ -38,20 +38,19 @@
#include <boost/geometry/core/access.hpp>
#include <boost/geometry/core/coordinate_dimension.hpp>
#include <boost/geometry/core/is_multi.hpp>
-#include <boost/geometry/core/interior_rings.hpp>
#include <boost/geometry/core/reverse_dispatch.hpp>
+#include <boost/geometry/geometries/concepts/check.hpp>
+
#include <boost/geometry/algorithms/detail/disjoint.hpp>
#include <boost/geometry/algorithms/detail/not.hpp>
-#include <boost/geometry/algorithms/detail/overlay/turn_info.hpp>
-#include <boost/geometry/algorithms/detail/overlay/traversal_info.hpp>
-
+// For trivial checks
#include <boost/geometry/algorithms/area.hpp>
-#include <boost/geometry/algorithms/overlay/get_turns.hpp>
-#include <boost/geometry/geometries/concepts/check.hpp>
+#include <boost/geometry/algorithms/length.hpp>
#include <boost/geometry/util/math.hpp>
+#include <boost/geometry/algorithms/detail/equals/collect_vectors.hpp>
namespace boost { namespace geometry
@@ -91,261 +90,74 @@
}
};
-class equals_interrupt_policy
-{
-
- // As soon as a turn is detected, this flag is set to true
- // and the process of getting turns (intersection points)
- // is interrupted
- bool turns_inside_or_outside;
- bool has_collinear;
-
-
-public:
- static bool const enabled = true;
-
- inline equals_interrupt_policy()
- : turns_inside_or_outside(false)
- , has_collinear(false)
- {}
-
- bool equals() const
- {
- return has_collinear && ! turns_inside_or_outside;
- }
-
- template <typename Range>
- inline bool apply(Range const& range)
- {
- for (typename boost::range_iterator<Range const>::type
- it = boost::begin(range);
- it != boost::end(range);
- ++it)
- {
- if (! it->ignore)
- {
- if (it->method == detail::overlay::method_collinear
- || it->method == detail::overlay::method_equal)
- {
- typedef typename boost::range_value<Range>::type turn_type;
- // If it is not such that both turns are collinear, the rings are not equal
- for (typename boost::range_iterator
- <
- typename turn_type::container_type const
- >::type oit = boost::begin(it->operations);
- oit != boost::end(it->operations);
- oit++)
- {
- if (oit->operation != detail::overlay::operation_continue)
- {
- turns_inside_or_outside = true;
- return true;
- }
- else
- {
- has_collinear = true;
- }
- }
- }
- else
- {
- turns_inside_or_outside = true;
- return true;
- }
- }
- }
- // It is not yet known, so don't interrupt
- return false;
- }
-
-};
-
-
-template <typename Ring1, typename Ring2>
-struct ring_ring
+struct area_check
{
-
-
- static inline bool apply(Ring1 const& ring1, Ring2 const& ring2, bool check_area = true)
+ template <typename Geometry1, typename Geometry2>
+ static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
{
- // Note: this implementation makes use of getting interections (turns)
- // and merge them. If all IP's disappear, the ring should be the same
- // (because merging removes collinear or non-collinear
- // IP's following the same path)
-
- // However, this implementation should be re-done using
- // a linear time algorithm (getting left-most points of both
- // and follow them using circular iterator and distance/side)
-
- // obvious check, area's should be the same.
- if (check_area && geometry::area(ring1) != geometry::area(ring2))
- {
- return false;
- }
- // We could check more (perimeter,centroid,envelope)
- // For now we go directly to intersection points
-
- typedef typename geometry::point_type<Ring1>::type point_type;
- typedef detail::overlay::traversal_turn_info<point_type> turn_info;
- std::vector<turn_info> turns;
-
- equals_interrupt_policy policy;
-
- boost::geometry::get_turns
- <
- detail::overlay::assign_null_policy
- >(ring1, ring2, turns, policy);
-
- return policy.equals();
- }
+ return geometry::math::equals(
+ geometry::area(geometry1),
+ geometry::area(geometry1));
+ }
};
-template <typename T>
-struct equal_sortable
+struct length_check
{
- int index;
- T area;
- bool counterpart_found;
- inline equal_sortable(int i, T const& a)
- : index(i)
- , area(a)
- , counterpart_found(false)
- {}
-
- inline bool operator<(equal_sortable<T> const& other) const
+ template <typename Geometry1, typename Geometry2>
+ static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
{
- return area < other.area;
- }
+ return geometry::math::equals(
+ geometry::length(geometry1),
+ geometry::length(geometry1));
+ }
};
-template <typename Range, typename Collection>
-inline void fill_equal_sortable(Range const& range,
- Collection& v)
+template <typename Geometry1, typename Geometry2, typename TrivialCheck>
+struct equals_by_collection
{
- typedef typename boost::range_value<Collection>::type item_type;
- int i = 0;
- for (typename boost::range_iterator<Range const>::type
- it = boost::begin(range);
- it != boost::end(range);
- ++it, ++i)
+ static inline bool apply(Geometry1 const& geometry1, Geometry2 const& geometry2)
{
- v.push_back(item_type(i, geometry::area(*it)));
- }
- std::sort(v.begin(), v.end());
- /***
- for (typename std::vector<sortable>::iterator it = v.begin();
- it != v.end();
- ++it)
- {
- std::cout << "Ring: " << it->index << " area: " << it->area << std::endl;
- }
- ***/
-}
-
-
-template
-<
- typename Policy,
- typename Range1,
- typename Range2
->
-inline bool range_range(Range1 const& range1, Range2 const& range2)
-{
- typedef typename boost::range_value<Range1>::type geometry1;
- // Check interior rings -> first sort them on area ,
- // for performance reasons (area is not re-calculated in ring-compare)
- typedef std::vector
- <
- equal_sortable<typename geometry::area_result<geometry1>::type>
- > collection;
-
- collection sorted1, sorted2;
-
- fill_equal_sortable(range1, sorted1);
- fill_equal_sortable(range2, sorted2);
-
- typedef typename boost::range_iterator<collection>::type iterator;
-
- // Compare all items (e.g. rings having equal area)
- for (iterator it1 = sorted1.begin(); it1 != sorted1.end(); ++it1)
- {
- for (iterator it2 = sorted2.begin();
- ! it1->counterpart_found
- && it2 != sorted2.end()
- && it2->area <= it1->area; //+epsilon
- ++it2)
- {
- if (! it2->counterpart_found
- && geometry::math::equals(it1->area, it2->area))
- {
- // Call policy, without checking area
- if (Policy::apply(range1[it1->index], range2[it2->index], false))
- {
- it1->counterpart_found = true;
- it2->counterpart_found = true;
- }
- }
- }
-
- if (! it1->counterpart_found)
- {
- return false;
- }
- }
- return true;
-}
-
-
-template <typename Polygon1, typename Polygon2>
-struct polygon_polygon
-{
- static inline bool apply(Polygon1 const& polygon1, Polygon2 const& polygon2,
- bool compare_area = false)
- {
- // Check number of rings (area check is done in exterior ring check)
- if (geometry::num_interior_rings(polygon1) != geometry::num_interior_rings(polygon2))
- {
- return false;
- }
-
- typedef typename geometry::ring_type<Polygon1>::type ring_type1;
- typedef typename geometry::ring_type<Polygon2>::type ring_type2;
- typedef ring_ring<ring_type1, ring_type2> compare;
-
- // Check exterior ring
- if (! compare::apply(exterior_ring(polygon1), exterior_ring(polygon2)))
- {
- return false;
- }
-
- return range_range<compare>(
- interior_rings(polygon1),
- interior_rings(polygon2));
+ if (! TrivialCheck::apply(geometry1, geometry2))
+ {
+ return false;
+ }
+
+ typedef typename geometry::select_most_precise
+ <
+ typedef select_coordinate_type
+ <
+ Geometry1, Geometry2
+ >::type,
+ double
+ >::type calculation_type;
+
+ typedef std::vector<collected_vector<calculation_type> > v;
+ v c1, c2;
+
+ geometry::collect_vectors(c1, geometry1);
+ geometry::collect_vectors(c2, geometry2);
+
+ if (boost::size(c1) != boost::size(c2))
+ {
+ return false;
+ }
+
+ // Check where direction is NOT changing
+
+ std::sort(c1.begin(), c1.end());
+ std::sort(c2.begin(), c2.end());
+
+ // Just check if these vectors are equal.
+ return c1.size() == c2.size()
+ && std::equal(c1.begin(), c1.end(), c2.begin());
}
};
-template <typename Polygon, typename Ring>
-struct polygon_ring
-{
- static inline bool apply(Polygon const& polygon, Ring const& ring)
- {
- // A polygon can be equal to a ring if there are no interior rings
- return boost::size(interior_rings(polygon)) == 0
- ? ring_ring
- <
- typename geometry::ring_type<Polygon>::type,
- Ring
- >::apply(exterior_ring(polygon), ring)
- : false;
- }
-};
-
-
}} // namespace detail::equals
#endif // DOXYGEN_NO_DETAIL
@@ -385,19 +197,61 @@
template <typename Ring1, typename Ring2>
struct equals<ring_tag, ring_tag, false, false, Ring1, Ring2, 2>
- : detail::equals::ring_ring<Ring1, Ring2>
+ : detail::equals::equals_by_collection
+ <
+ Ring1, Ring2,
+ detail::equals::area_check
+ >
{};
template <typename Polygon1, typename Polygon2>
struct equals<polygon_tag, polygon_tag, false, false, Polygon1, Polygon2, 2>
- : detail::equals::polygon_polygon<Polygon1, Polygon2>
+ : detail::equals::equals_by_collection
+ <
+ Polygon1, Polygon2,
+ detail::equals::area_check
+ >
+{};
+
+
+template <typename LineString1, typename LineString2>
+struct equals<linestring_tag, linestring_tag, false, false, LineString1, LineString2, 2>
+ : detail::equals::equals_by_collection
+ <
+ LineString1, LineString2,
+ detail::equals::length_check
+ >
{};
template <typename Polygon, typename Ring>
struct equals<polygon_tag, ring_tag, false, false, Polygon, Ring, 2>
- : detail::equals::polygon_ring<Polygon, Ring>
+ : detail::equals::equals_by_collection
+ <
+ Polygon, Ring,
+ detail::equals::area_check
+ >
+{};
+
+
+template <typename Ring, typename Box>
+struct equals<ring_tag, box_tag, false, false, Ring, Box, 2>
+ : detail::equals::equals_by_collection
+ <
+ Ring, Box,
+ detail::equals::area_check
+ >
+{};
+
+
+template <typename Polygon, typename Box>
+struct equals<polygon_tag, box_tag, false, false, Polygon, Box, 2>
+ : detail::equals::equals_by_collection
+ <
+ Polygon, Box,
+ detail::equals::area_check
+ >
{};