Subject: [Boost-commit] svn:boost r76710 - in trunk: boost/geometry/extensions/algorithms/buffer boost/geometry/extensions/strategies libs/geometry/test_extensions/algorithms/buffer
From: barend.gehrels_at_[hidden]
Date: 2012-01-26 15:54:21
Author: barendgehrels
Date: 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
New Revision: 76710
URL: http://svn.boost.org/trac/boost/changeset/76710
Log:
Milestone, buffer is basically working now. That's to say, convex polygons, or some concavities are buffered correctly. Still to do:
- concavities in starting point
- intersections beyond hooklets
- concavities-only (as in triangular holes)
- internal overlaps (with dissolve)
Text files modified:
trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp | 125 +++++++++++++++++++++++++++++++++++++--
trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp | 16 +++-
trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp | 20 +++++
trunk/boost/geometry/extensions/strategies/buffer.hpp | 16 ++--
trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp | 70 ++++++++++++++++------
trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp | 62 +++++++++++++++++++
6 files changed, 261 insertions(+), 48 deletions(-)
Modified: trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/buffer_appender.hpp 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
@@ -26,31 +26,138 @@
{
// Appends points to an output range (always a ring).
-// This is only the first phase, on the way specific points will be "marked"
-// as a begin-point, and some segments will be intersected with all previous segments
-// up to the "marked" point. If there is an intersection then points in between will
-// be deleted and the intersection point will be added instead.
-
-// This file is renamed from "intersecting_inserter" but we choose "append" now
-// because that is also how the algorithm geometry::append is called. And it appends at the back (push_back)
-template<typename Range>
+// On the way, special points can be marked, and marked points
+// forming a hooklet, loop, curve, curl, or how you call it are checked on intersections.
+template
+ <
+ typename Range
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , typename Mapper
+#endif
+ >
struct buffer_appender
{
typedef Range range_type;
typedef typename geometry::point_type<Range>::type point_type;
-
+ typedef model::referring_segment<const point_type> segment_type;
+ typedef strategy::intersection::relate_cartesian_segments
+ <
+ policies::relate::segments_intersection_points
+ <
+ segment_type,
+ segment_type,
+ segment_intersection_points<point_type>
+ >
+ > policy;
+
+
+ int m_index_begin_join;
+ int m_index_end_hooklet;
+ int m_index_begin_hooklet;
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ Mapper const& m_mapper;
+ inline buffer_appender(Range& r, Mapper const& mapper)
+ : m_range(r)
+ , m_mapper(mapper)
+#else
inline buffer_appender(Range& r)
: m_range(r)
+#endif
+
+ , m_index_begin_join(-1)
+ , m_index_end_hooklet(-1)
+ , m_index_begin_hooklet(-1)
{}
inline void append(point_type const& point)
{
m_range.push_back(point);
+ m_index_end_hooklet = -1;
+ m_index_begin_hooklet = -1;
+ }
+
+ inline void append_end_hooklet(point_type const& point)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,0,255);", 4);
+#endif
+
+ m_index_end_hooklet = boost::size(m_range);
+ m_range.push_back(point);
+ }
+
+ inline void append_begin_hooklet(point_type const& point)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,0,192);", 3);
+#endif
+ if (m_index_begin_hooklet > 0)
+ {
+ calculate(point, m_index_begin_hooklet - 1, boost::size(m_range) - 1);
+ }
+
+ m_index_begin_hooklet = boost::size(m_range);
+ m_range.push_back(point);
}
+ inline void append_begin_join(point_type const& point)
+ {
+ if (m_index_begin_join >= 0 && m_index_end_hooklet >= 0)
+ {
+ calculate(point, m_index_begin_join, m_index_end_hooklet);
+ }
+ else
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(0,255,0);", 5);
+#endif
+ }
+
+ m_index_begin_join = boost::size(m_range);
+ m_range.push_back(point);
+ }
+
+
private :
Range& m_range;
+
+ inline bool calculate(point_type const& point, int begin, int end)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ const_cast<Mapper&>(m_mapper).map(point, "fill:rgb(255,0,0);", 4);
+ for (int i = begin; i < end; i++)
+ {
+ //const_cast<Mapper&>(m_mapper).map(m_range[i], "fill:rgb(0,255,255);", 3);
+ }
+#endif
+
+ segment_type segment1(m_range[end], point);
+
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ //const_cast<Mapper&>(m_mapper).map(segment1, "stroke:rgb(0,255,255);stroke-width:4");
+#endif
+
+ for (int i = begin; i < end - 1; i++)
+ {
+ segment_type segment2(m_range[i], m_range[i + 1]);
+ segment_intersection_points<point_type> is = policy::apply(segment1, segment2);
+ if (is.count > 0)
+ {
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ const_cast<Mapper&>(m_mapper).map(is.intersections[0], "fill:rgb(255,0,255);", 4);
+#endif
+
+ // Remove all points until this point, and add intersection point.
+ m_range.resize(i + 1);
+ m_range.push_back(is.intersections[0]);
+ m_index_end_hooklet = -1;
+ return true;
+ }
+ }
+ return false;
+ }
};
Modified: trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/linestring_buffer.hpp 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
@@ -46,12 +46,9 @@
>
{
- template
- <
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
- typename Mapper
+ template<typename Mapper>
#endif
- >
static inline void apply(Linestring const& linestring, Polygon& buffered,
DistanceStrategy const& distance,
JoinStrategy const& join_strategy
@@ -60,9 +57,18 @@
#endif
)
{
- buffer_appender<typename geometry::ring_type<Polygon>::type> appender
+ buffer_appender
+ <
+ typename geometry::ring_type<Polygon>::type
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , Mapper
+#endif
+ > appender
(
geometry::exterior_ring(buffered)
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , mapper
+#endif
);
iterate(appender, boost::begin(linestring), boost::end(linestring),
Modified: trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp (original)
+++ trunk/boost/geometry/extensions/algorithms/buffer/polygon_buffer.hpp 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
@@ -103,12 +103,22 @@
typedef typename ring_type<PolygonInput>::type input_ring_type;
typedef typename ring_type<PolygonOutput>::type output_ring_type;
- typedef buffer_appender<output_ring_type> appender_type;
+ typedef buffer_appender
+ <
+ output_ring_type
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , Mapper
+#endif
+ > appender_type;
typedef ring_buffer<input_ring_type, output_ring_type, DistanceStrategy, JoinStrategy> policy;
{
- appender_type appender(geometry::exterior_ring(buffered));
+ appender_type appender(geometry::exterior_ring(buffered)
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , mapper
+#endif
+ );
policy::apply(exterior_ring(polygon), appender,
distance, join_strategy
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
@@ -123,7 +133,11 @@
{
output_ring_type ring;
- appender_type appender(ring);
+ appender_type appender(ring
+#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
+ , mapper
+#endif
+ );
policy::apply(*it, appender, distance, join_strategy
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
Modified: trunk/boost/geometry/extensions/strategies/buffer.hpp
==============================================================================
--- trunk/boost/geometry/extensions/strategies/buffer.hpp (original)
+++ trunk/boost/geometry/extensions/strategies/buffer.hpp 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
@@ -128,8 +128,8 @@
// If it is concave (corner to left), add helperline
// The helper-line IS essential for buffering holes. Without,
// holes might be generated, while they should NOT be there.
- appender.append(perp1);
- appender.append(perp2);
+ appender.append_begin_hooklet(perp1);
+ appender.append_end_hooklet(perp2);
}
else
{
@@ -160,7 +160,7 @@
#endif
}
- appender.append(p);
+ appender.append_begin_join(p);
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
map<BufferAppender>(ip, vertex, perp1, perp2);
@@ -291,8 +291,8 @@
if (side::apply(perp1, ip, perp2) == signum)
{
// If it is concave (corner to left), add helperline
- appender.append(perp1);
- appender.append(perp2);
+ appender.append_begin_hooklet(perp1);
+ appender.append_end_hooklet(perp2);
}
else
{
@@ -310,22 +310,20 @@
set<0>(bp, get<0>(vertex) + vix * prop);
set<1>(bp, get<1>(vertex) + viy * prop);
+ appender.append_begin_join(perp1);
if (m_max_level <= 1)
{
- appender.append(perp1);
if (m_max_level == 1)
{
appender.append(bp);
}
- appender.append(perp2);
}
else
{
- appender.append(perp1);
mid_points(vertex, perp1, bp, bd, appender);
mid_points(vertex, bp, perp2, bd, appender);
- appender.append(perp2);
}
+ appender.append(perp2);
#ifdef BOOST_GEOMETRY_DEBUG_WITH_MAPPER
map<BufferAppender>(bp, vertex, perp1, perp2);
Modified: trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp
==============================================================================
--- trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp (original)
+++ trunk/libs/geometry/test_extensions/algorithms/buffer/polygon_buffer.cpp 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
@@ -54,12 +54,12 @@
typedef bg::model::polygon<P> polygon_type;
- test_one<polygon_type, buf::join_miter, polygon_type>("L", letter_L, 'm', 14, 0.5);
- test_one<polygon_type, buf::join_round, polygon_type>("L", letter_L, 'r', 13.7254516100806, 0.5);
- test_one<polygon_type, buf::join_miter, polygon_type>("simplex", simplex, 'm', 52.8733092508931, 1.5);
- test_one<polygon_type, buf::join_round, polygon_type>("simplex", simplex, 'r', 47.9004943967109, 1.5);
- test_one<polygon_type, buf::join_miter, polygon_type>("concave_simplex", concave_simplex, 'm', 16.3861105439862, 0.5);
- test_one<polygon_type, buf::join_round, polygon_type>("concave_simplex", concave_simplex, 'r', 14.5563908986706, 0.5);
+ test_one<polygon_type, buf::join_miter, polygon_type>(true, "L", letter_L, 'm', 12.875, 0.5);
+ test_one<polygon_type, buf::join_round, polygon_type>(true, "L", letter_L, 'r', 12.73128, 0.5);
+ test_one<polygon_type, buf::join_miter, polygon_type>(true, "simplex", simplex, 'm', 47.2, 1.5);
+ test_one<polygon_type, buf::join_round, polygon_type>(true, "simplex", simplex, 'r', 44.1156, 1.5);
+ test_one<polygon_type, buf::join_miter, polygon_type>(true, "concave_simplex", concave_simplex, 'm', 14.47708, 0.5);
+ test_one<polygon_type, buf::join_round, polygon_type>(true, "concave_simplex", concave_simplex, 'r', 13.10366, 0.5);
test_one<polygon_type, buf::join_miter, polygon_type>("indentation4", indentation, 'm', 25.7741125496954, 0.4);
test_one<polygon_type, buf::join_round, polygon_type>("indentation4", indentation, 'r', 25.5641980024698, 0.4);
@@ -95,11 +95,11 @@
test_one<polygon_type, buf::join_miter, polygon_type>("arrow6", arrow, 'm', 34.9025533178038, 0.6);
test_one<polygon_type, buf::join_round, polygon_type>("arrow6", arrow, 'r', 32.2572740033805, 0.6);
- test_one<polygon_type, buf::join_miter, polygon_type>("tipped_aitch3", tipped_aitch, 'm', 55.36, 0.3);
+ test_one<polygon_type, buf::join_miter, polygon_type>(true, "tipped_aitch3", tipped_aitch, 'm', 54.865, 0.3);
test_one<polygon_type, buf::join_miter, polygon_type>("tipped_aitch9", tipped_aitch, 'm', 77.44, 0.9);
test_one<polygon_type, buf::join_miter, polygon_type>("tipped_aitch13", tipped_aitch, 'm', 92.16, 1.3);
- test_one<polygon_type, buf::join_miter, polygon_type>("snake4", snake, 'm', 64.44, 0.4);
+ test_one<polygon_type, buf::join_miter, polygon_type>(true, "snake4", snake, 'm', 63.76, 0.4);
test_one<polygon_type, buf::join_miter, polygon_type>("snake5", snake, 'm', 72, 0.5);
test_one<polygon_type, buf::join_miter, polygon_type>("snake6", snake, 'm', 75.44, 0.6);
test_one<polygon_type, buf::join_miter, polygon_type>("snake16", snake, 'm', 114.24, 1.6);
@@ -107,7 +107,7 @@
//return;
- test_one<polygon_type, buf::join_round, polygon_type>("flower1", flower, 'r', 67.48584413272776, 0.1);
+ test_one<polygon_type, buf::join_round, polygon_type>(true, "flower1", flower, 'r', 71.986, 0.1);
test_one<polygon_type, buf::join_miter, polygon_type>("flower25", flower, 'm', 78.225583936485492, 0.25);
test_one<polygon_type, buf::join_miter, polygon_type>("flower30", flower, 'm', 81.492494146177947, 0.30);
//test_one<polygon_type, buf::join_miter, polygon_type>("flower35", flower, 'm', 84.694183819917185, 0.35);
@@ -128,20 +128,50 @@
test_one<polygon_type, buf::join_round, polygon_type>("flower60", flower, 'r', 99.4081550761828, 0.60);
//test_one<polygon_type, buf::join_miter, polygon_type>("flower35", flower, 'm', 84.694183819917185, 0.35);
-
- for (int i = 1; i < 12; i++)
+ // Saw
{
- std::ostringstream out;
- out << "saw_" << i;
- test_one<polygon_type, buf::join_round, polygon_type>(out.str(), saw, 'r', 99.4081550761828, double(i) / 2.0);
- test_one<polygon_type, buf::join_miter, polygon_type>(out. str(), saw, 'm', 99.4081550761828, double(i) / 2.0);
+ int const n = 12;
+ double expected_round[n] =
+ {
+ 69.87495, 90.22175, 111.5404, 133.87848, 157.452972, 182.397264,
+ 208.773, -1, -1, -1, -1, -1
+ };
+ double expected_miter[n] =
+ {
+ 73.03597, 98.80428, 127.8049, 160.0379, 195.5032, 234.2009,
+ 276.1309,-1, -1, -1, -1, -1
+ };
+
+ for (int i = 1; i <= n; i++)
+ {
+ std::ostringstream out;
+ out << "saw_" << i;
+ test_one<polygon_type, buf::join_round, polygon_type>(i <= 7, out.str(), saw, 'r', expected_round[i - 1], double(i) / 2.0);
+ test_one<polygon_type, buf::join_miter, polygon_type>(i <= 7, out.str(), saw, 'm', expected_miter[i - 1], double(i) / 2.0);
+ }
}
- for (int i = 1; i < 12; i++)
+
+ // Bowl
{
- std::ostringstream out;
- out << "bowl_" << i;
- test_one<polygon_type, buf::join_round, polygon_type>(out.str(), bowl, 'r', 99.4081550761828, double(i) / 2.0);
- test_one<polygon_type, buf::join_miter, polygon_type>(out. str(), bowl, 'm', 99.4081550761828, double(i) / 2.0);
+ int const n = 12;
+ double expected_round[n] =
+ {
+ 44.49221, 60.02458, 77.09711, 95.70980, 115.8626, 137.4720,
+ -1, -1, -1, -1, -1, -1
+ };
+ double expected_miter[n] =
+ {
+ 44.86448, 61.01367, 78.94756, 98.66614, 120.1694, 143.3738,
+ 167.9742, 193.9427, 221.2792, -1, -1, -1
+ };
+
+ for (int i = 1; i <= n; i++)
+ {
+ std::ostringstream out;
+ out << "bowl_" << i;
+ test_one<polygon_type, buf::join_round, polygon_type>(i <= 6, out.str(), bowl, 'r', expected_round[i - 1], double(i) / 2.0);
+ test_one<polygon_type, buf::join_miter, polygon_type>(i <= 9, out.str(), bowl, 'm', expected_miter[i - 1], double(i) / 2.0);
+ }
}
test_one<polygon_type, buf::join_round, polygon_type>("county1", county1, 'r', 99.4081550761828, 0.01);
test_one<polygon_type, buf::join_miter, polygon_type>("county1", county1, 'm', 99.4081550761828, 0.01);
Modified: trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp
==============================================================================
--- trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp (original)
+++ trunk/libs/geometry/test_extensions/algorithms/buffer/test_buffer.hpp 2012-01-26 15:54:17 EST (Thu, 26 Jan 2012)
@@ -93,7 +93,7 @@
>
void test_buffer(std::string const& caseid, Geometry const& geometry,
char join,
- double expected_area,
+ bool check, double expected_area,
double distance_left, double distance_right)
{
namespace bg = boost::geometry;
@@ -188,6 +188,17 @@
// std::cout << bg::wkt(polygon) << std::endl;
//}
+ if (check)
+ {
+ double area = 0;
+ BOOST_FOREACH(GeometryOut const& polygon, buffered)
+ {
+ area += bg::area(polygon);
+ }
+ BOOST_CHECK_CLOSE(area, expected_area, 0.01);
+ }
+
+
// Map input geometry in green
mapper.map(geometry, "opacity:0.5;fill:rgb(0,128,0);stroke:rgb(0,128,0);stroke-width:1");
@@ -248,8 +259,55 @@
#endif
test_buffer<GeometryOut, JoinStrategy>
- (caseid, g, join, expected_area, distance_left, distance_right);
+ (caseid, g, join, false, expected_area, distance_left, distance_right);
}
+template
+<
+ typename Geometry,
+ template
+ <
+ typename
+ , typename
+#if defined(BOOST_GEOMETRY_DEBUG_WITH_MAPPER)
+ , typename
+#endif
+ > class JoinStrategy,
+ typename GeometryOut
+>
+void test_one(bool check, std::string const& caseid, std::string const& wkt,
+ char join, double expected_area,
+ double distance_left, double distance_right = -999)
+{
+ namespace bg = boost::geometry;
+ Geometry g;
+ bg::read_wkt(wkt, g);
+
+ typedef typename bg::point_type<Geometry>::type point_type;
+
+ //std::cout << caseid << std::endl;
+ if (join == 'm')
+ {
+ //return;
+ }
+
+
+
+#ifdef BOOST_GEOMETRY_CHECK_WITH_POSTGIS
+ std::cout
+ << (counter > 0 ? "union " : "")
+ << "select " << counter++
+ << ", '" << caseid << "' as caseid"
+ << ", ST_Area(ST_Buffer(ST_GeomFromText('" << wkt << "'), "
+ << distance_left
+ << ", 'endcap=flat join=" << (join == 'm' ? "miter" : "round") << "'))"
+ << ", " << expected_area
+ << std::endl;
+#endif
+
+ test_buffer<GeometryOut, JoinStrategy>
+ (caseid, g, join, check, expected_area, distance_left, distance_right);
+}
+
#endif