diff options
Diffstat (limited to 'libs/polygon')
| -rw-r--r-- | libs/polygon/doc/voronoi_main.htm | 211 | ||||
| -rw-r--r-- | libs/polygon/meta/libraries.json | 18 | ||||
| -rw-r--r-- | libs/polygon/test/Jamfile.v2 | 2 | ||||
| -rw-r--r-- | libs/polygon/test/gtl_boost_unit_test.cpp | 2 | ||||
| -rw-r--r-- | libs/polygon/test/polygon_90_data_test.cpp | 51 | ||||
| -rw-r--r-- | libs/polygon/test/polygon_set_data_test.cpp | 111 |
6 files changed, 245 insertions, 150 deletions
diff --git a/libs/polygon/doc/voronoi_main.htm b/libs/polygon/doc/voronoi_main.htm index c98134a99..458fc2cd9 100644 --- a/libs/polygon/doc/voronoi_main.htm +++ b/libs/polygon/doc/voronoi_main.htm @@ -1,12 +1,7 @@ <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <html><head> - - - - <meta http-equiv="Content-Language" content="en-us"> <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Main</title> - <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> <meta http-equiv="content-type" content="text/html; charset=utf-8"> @@ -28,25 +23,17 @@ <li><a href="gtl_segment_concept.htm">Segment Concept</a></li> <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> - <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 -With Holes Concept</a></li> + <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 With Holes Concept</a></li> <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> - <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 -With Holes Concept</a></li> + <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 With Holes Concept</a></li> <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> - <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With -Holes Concept</a></li> - <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set -Concept</a></li> - <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set -Concept</a></li> + <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept</a></li> + <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set Concept</a></li> + <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set Concept</a></li> <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> - <li><a href="gtl_connectivity_extraction_90.htm">Connectivity -Extraction 90</a></li> - <li><a href="gtl_connectivity_extraction_45.htm">Connectivity -Extraction 45</a></li> - <li><a href="gtl_connectivity_extraction.htm">Connectivity -Extraction</a></li> + <li><a href="gtl_connectivity_extraction_90.htm">Connectivity Extraction 90</a></li> + <li><a href="gtl_connectivity_extraction_45.htm">Connectivity Extraction 45</a></li> + <li><a href="gtl_connectivity_extraction.htm">Connectivity Extraction</a></li> <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> <li><a href="gtl_property_merge.htm">Property Merge</a></li> @@ -58,47 +45,39 @@ Extraction</a></li> <h3 class="navbar">Other Resources</h3> <ul> <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> - <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 -Presentation</a></li> + <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 Presentation</a></li> <li><a href="analysis.htm">Performance Analysis</a></li> <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li> - <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced -Tutorial</a></li> + <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced Tutorial</a></li> </ul> </div> <h3 class="navbar">Polygon Sponsor</h3> <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div> </td> <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br> - <h1>THE BOOST.POLYGON VORONOI LIBRARY </h1> + <h1>THE BOOST POLYGON VORONOI EXTENSIONS</h1> <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br> -The Voronoi extension of the Boost.Polygon library provides -functionality to construct a <a href="voronoi_diagram.htm">Voronoi -diagram</a> -of a set of points and linear segments in 2D space with the following -set of -limitations:<br> +The Voronoi extensions of the Boost Polygon library provide functionality to +construct a <a href="voronoi_diagram.htm">Voronoi diagram</a> of a set of points +and linear segments in 2D space with the following set of limitations:<br> <ul> - <li>coordinates of the input points and endpoints of the -input segments -should be of the integer type;</li> - <li>input segments should not overlap -except their endpoints.</li> + <li>Coordinates of the input points and endpoints of the input segments should have integral type. The int32 data type is supported by the default implementation. Support for the other data types (e.g. int64) could be achieved through the configuration of the coordinate type traits (<a href="voronoi_advanced_tutorial.htm">Voronoi Advanced tutorial</a>).</li> + <li>Input points and segments should not overlap except their endpoints. This means that input point should not lie inside the input segment and input segments should not intersect except their endpoints.</li> </ul> While the first restriction is permanent (it allows to give the exact warranties about the output precision and algorithm execution flow), the second one may be resolved using the Boost.Polygon <a href="gtl_segment_concept.htm">segment utils</a>. The strong sides of the -library and main benefits comparing to the other implementations are +library and the main benefits comparing to the other implementations are discussed in the following paragraphs.<br> <h2>Fully Functional with Segments</h2> There are just a few implementations of the Voronoi diagram construction algorithm that can -handle input data sets that contain linear segment, even considering +handle input data sets that contain linear segments, even considering the commercial libraries. Support of the @@ -120,10 +99,10 @@ the problems is resolved using the multiprecision geometric predicates. Even for the commercial libraries, usage of such predicates -results in a vast performance slowdown. The Voronoi implementation +results in a vast performance slowdown. The library implementation overcomes this by avoiding the multiprecision -computations in the 95% of the cases and -uses the efficient, floating-point based predicates. Such preciates +computations in the 95% of the cases by +using the efficient, floating-point based predicates. Such predicates don't produce the correct result always, however the library embeds the relative @@ -133,7 +112,7 @@ higher precision predicates when appropriate. As the result, the implementation has a solid performance comparing to the other known libraries (more details in the <a href="voronoi_benchmark.htm">benchmarks</a>).<br> <h2>Precision of the Output Structures </h2> -The Voronoi implementation guaranties, that the relative error of the +The implementation guaranties, that the relative error of the coordinates of the output geometries is at most 64 machine epsilons (6 bits of mantissa, for the IEEE-754 floating-point type), while on @@ -186,15 +165,12 @@ Detailed description of the absolute and relative errors evaluation can be found in the article: <a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">"What Every Computer Scientist Should Know About Floating-Point Arithmetic"</a><a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html"></a>.<br> <br> -During the finalization step the implementation unites the Voronoi -vertices -whose both -coordinates are situated within the relative error range equal to 128 +During the finalization step the implementation unites Voronoi vertices whose both +coordinates are located within the relative error range equal to 128 machine epsilons and removes any Voronoi edges between those. This is -the only case, that might cause differences between the algorithm -output +the only case, that might cause differences between the algorithm output topology and theoretically precise one, and practically means the -following: for the Voronoi diagram of a set of solid bodies inside the +following: for a Voronoi diagram of a set of solid bodies inside the Solar System (radius 2<sup>42</sup> metres) and the long double (64 bit mantissa) output coordinate type the maximum absolute error within the Solar System rectangle will be equal to 2<sup>-64</sup> * 2<sup>42</sup> @@ -205,8 +181,7 @@ equal and united.<br> <h2>Simple Interface </h2> The <a href="../../../boost/polygon/voronoi.hpp">boost/polygon/</a><a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> library header defines the following static functions to integrate the -Voronoi library -functionality with the Boost.Polygon interfaces:<br> +Voronoi extensions functionality with the Boost.Polygon interfaces:<br> <br> <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2"> <tbody> @@ -215,7 +190,7 @@ functionality with the Boost.Polygon interfaces:<br> <typename Point, typename VB><br> size_t <span style="font-weight: bold;">insert</span>(const Point &point, VB *vb) </td> - <td>Inserts a point into the Voronoi builder data structure.<br> + <td>Inserts a point into a Voronoi builder data structure.<br> Point type should model the point concept.<br> Returns index of the inserted site. </td> </tr> @@ -228,7 +203,7 @@ first, <br> PointIterator last,<br> VB *vb) </td> - <td>Inserts an iterator range of points into the Voronoi + <td>Inserts an iterator range of points into a Voronoi builder data structure.<br> Corresponding point type should model the point concept. </td> </tr> @@ -237,7 +212,7 @@ Corresponding point type should model the point concept. </td> <typename Segment, typename VB><br> size_t <span style="font-weight: bold;">insert</span>(const Segment &segment, VB *vb) </td> - <td>Inserts a segment into the Voronoi builder data + <td>Inserts a segment into a Voronoi builder data structure.<br> Segment type should model the segment concept.<br> Returns index of the inserted site. </td> @@ -251,7 +226,7 @@ first,<br> SegmentIterator last,<br> VB *vb) </td> - <td>Inserts an iterator range of segments into the Voronoi + <td>Inserts an iterator range of segments into a Voronoi builder data structure.<br> Corresponding segment type should model the segment concept. </td> </tr> @@ -263,7 +238,7 @@ first,<br> &nbs PointIterator last,<br> VD *vd) </td> - <td>Constructs the Voronoi diagram of a set of points.<br> + <td>Constructs a Voronoi diagram of a set of points.<br> Corresponding point type should model the point concept.<br> Complexity: O(N * log N), memory usage: O(N), where N is the total number of input points.<br> </td> @@ -276,7 +251,7 @@ first,<br> &nbs SegmentIterator last,<br> VD *vd) </td> - <td>Constructs the Voronoi diagram of a set of segments.<br> + <td>Constructs a Voronoi diagram of a set of segments.<br> Corresponding segment type should model the segment concept.<br> Complexity: O(N * log N), memory usage: O(N), where N is the total number of input segments.<br> </td> @@ -296,20 +271,18 @@ SegmentIterator s_first,<br> SegmentIterator s_last,<br> VD *vd) </td> - <td>Constructs the Voronoi -diagram of a set of points and segments.<br> -Corresponding point type should model the point concept.<br> -Corresponding segment type should model the segment concept.<br> -Complexity: O(N* log N), memory usage: O(N), where N is the total number of input points and segments.<br> -</td> + <td> + Constructs a Voronoi diagram of a set of points and segments.<br> + Corresponding point type should model the point concept.<br> + Corresponding segment type should model the segment concept.<br> + Complexity: O(N* log N), memory usage: O(N), where N is the total number of input points and segments.<br> + </td> </tr> </tbody> </table> <br> -The -following two lines of code construct the Voronoi diagram of a set of -points (as -long as the corresponding input geometry type satisfies the +The following two lines of code construct a Voronoi diagram of a set of +points (as long as the corresponding input geometry type satisfies the Boost.Polygon <a href="gtl_design_overview.htm">concept model</a>):<br> <br> <span style="font-family: Courier New,Courier,monospace;">voronoi_diagram<double> @@ -329,7 +302,7 @@ Voronoi tutorial</a>. The library allows users to implement their own Voronoi diagram / Delaunay triangulation construction routines based on the <a href="voronoi_builder.htm">Voronoi builder API</a>.<br> <h2>No Third Party Dependencies </h2> -The Voronoi extension of the Boost.Polygon library doesn't depend on +The Voronoi extensions of the Boost Polygon library doesn't depend on any 3rd party code and contains single dependency on the Boost libraries: boost/cstdint.hpp. @@ -337,95 +310,35 @@ All the required multiprecision types and related functionality are encapsulated as part of the implementation. The library is fast to compile (3 public and 4 private heades), has strong cohesion between its components and -is clearly modularized from the rest of the Boost.Polygon library, with +is clearly modularized from the rest of the Boost Polygon library, with the optional integration through the <a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> header.<br> <h2>Extensible for the User Provided Coordinate Types</h2> The implementation is coordinate type agnostic. As long -as the user provided types satisfy the set of the requirements of the <a href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits, -no additional -changes -are needed +as the user provided types satisfy the set of the requirements of the <a href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits, no additional changes are required neither to the algorithm, nor to the implementation of the predicates. -For example, it's -possible to +For example, it's possible to construct the Voronoi diagram with the 256-bit integer input coordinate -type -and -512-bit output floating-point type without making any changes to the +type and 512-bit output floating-point type without making any changes to the library.<br> <h2>Future Development </h2> -Below one may find the list of the main directions for the future -development of the library.<br> -The high-priority tasks that already have the approximate -implementation plan -are the following (some of those may be proposed as future GSoC -projects):<br> + Below one may find the list of the possible directions for the future + development of the library.<br> <ul> - <li>Implement the Delaunay triangulation data structure.<br> -Note: only data structure needs to be implemented that properly -processes events provided by the Voronoi builder.</li> - <li>Implement the medial axis transform data structure.<br> -Note: in general case the Voronoi diagram has completely the same -geometry -as the medial axis (they are 100% equal), however for many applications -user is not interested in the Voronoi edges inside the hole regions. -The main point -of this data structure is to automatically filter the Voronoi edges -that -belong to those areas.</li> - <li>The Voronoi -diagram data structure can be used to find the K nearest neighbors of -the N -sites in O(N*K*log(K) + N*log(N)) time. The return value would be a -list of the k nearest neighbors for each site. </li> - <li>Use the r-tree data structure built on top of the -bounding rectangles around the Voronoi cells to answer the nearest -neighbor queries in log(N) time, where N is the number of the Voronoi -cells.<br> -Note: there should be r-tree data structure available soon as part of -the Boost libraries.</li> - <li>Expose O(N) interface to retrieve the convex hull of a set -of -points and segments from the Voronoi builder, once the Voronoi diagram -is -constructed.</li> - <li>Provide serialization utilities for the Voronoi diagram -data structure. </li> + <li>Delaunay triangulation data structure implementation.</li> + <li>Medial axis data structure implementation.</li> + <li>Serialization utilities for the Voronoi diagram data structure.</li> + <li>Drop the restriction on the non-intersecting input geometries.</li> + <li>Support for the different types of the distance metrics.</li> </ul> -High-priority tasks to be considered:<br> - <ul> - <li>Drop the restriction on the non-intersecting input -geometries.</li> - <li>Integrate the Voronoi diagram data structure with the -BGL (Boost -Graph Library).</li> - <li>Support the other types of distance metrics.</li> - <li>Construction of the constrained Delaunay triangulation.</li> - <li>Support of the circular input geometries.</li> - </ul> -Based on the community suggestions priorities may be changed.<br> <h2>Theoretical Research </h2> -The Voronoi library -was developed as part of the Google Summer of Code 2010. The -library was actively maintained for the last three years and involved -the -strong mathematical research in the field of algorithms, data -structures, -relative error arithmetic and numerical robustness. Nowadays one can -often read a scientific paper, that contains non-practical -theoretical -results or implementation with -benchmarks nobody else can reproduce. The opposite story is with -the Voronoi library, that contains complete -implementation of -the Voronoi diagram construction algorithm and -benchmarks one may run on -his/her PC. Upon the community request, more documentation on the -theoretical aspects of the implementation will be published. -The -authors would like to acknowledge the Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm -for Voronoi diagrams</a>", that covers fundamental ideas of the -current implementation. </td> +The Voronoi extensions were developed as part of the Google Summer of Code 2010. +The library was actively maintained for the last three years and involved deep +mathematical research in the field of algorithms, data structures, relative +error arithmetic and numerical robustness. Upon the community request, +more details on the theoretical aspects of the implementation will be published. +The authors would like to acknowledge the Steven Fortune's article +"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm for Voronoi diagrams</a>", +that covers fundamental ideas of the current implementation. </td> </tr> <tr> <td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td> @@ -449,4 +362,4 @@ http://www.boost.org/LICENSE_1_0.txt</a>)</td> </tbody> </table> -</body></html>
\ No newline at end of file +</body></html> diff --git a/libs/polygon/meta/libraries.json b/libs/polygon/meta/libraries.json new file mode 100644 index 000000000..bfdf883a8 --- /dev/null +++ b/libs/polygon/meta/libraries.json @@ -0,0 +1,18 @@ +{ + "key": "polygon", + "name": "Polygon", + "authors": [ + "Lucanus Simonson", + "Andrii Sydorchuk" + ], + "description": "Voronoi diagram construction and booleans/clipping, resizing/offsetting and more for planar polygons with integral coordinates.", + "category": [ + "Algorithms", + "Data", + "Math" + ], + "maintainers": [ + "Lucanus Simonson <lucanus.j.simonson -at- intel.com>", + "Andrii Sydorchuk <sydorchuk.andriy -at- gmail.com>" + ] +} diff --git a/libs/polygon/test/Jamfile.v2 b/libs/polygon/test/Jamfile.v2 index 35657ff18..6a6e8caa1 100644 --- a/libs/polygon/test/Jamfile.v2 +++ b/libs/polygon/test/Jamfile.v2 @@ -22,6 +22,8 @@ test-suite polygon-unit [ run polygon_segment_test.cpp ] [ run polygon_interval_test.cpp ] [ run polygon_rectangle_test.cpp ] + [ run polygon_set_data_test.cpp ] + [ run polygon_90_data_test.cpp ] [ run gtl_boost_unit_test.cpp ] ; diff --git a/libs/polygon/test/gtl_boost_unit_test.cpp b/libs/polygon/test/gtl_boost_unit_test.cpp index 1ade24247..c85d5d661 100644 --- a/libs/polygon/test/gtl_boost_unit_test.cpp +++ b/libs/polygon/test/gtl_boost_unit_test.cpp @@ -681,7 +681,7 @@ namespace boost { namespace polygon{ std::cout << (ps2 == ps) << std::endl; ps2 ^= ps; std::cout << ps2.empty() << std::endl; - axis_transformation atr(axis_transformation::WS); + axis_transformation atr(axis_transformation::WEST_SOUTH); ps2 = ps; ps.transform(atr); transformation<int> tr(atr); diff --git a/libs/polygon/test/polygon_90_data_test.cpp b/libs/polygon/test/polygon_90_data_test.cpp new file mode 100644 index 000000000..9171a19f4 --- /dev/null +++ b/libs/polygon/test/polygon_90_data_test.cpp @@ -0,0 +1,51 @@ +// Boost.Polygon library polygon_90_data_test.cpp file + +// Copyright Andrii Sydorchuk 2015. +// Distributed under 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) + +// See http://www.boost.org for updates, documentation, and revision history. + +#define BOOST_TEST_MODULE POLYGON_90_DATA_TEST +#include <vector> + +#include <boost/mpl/list.hpp> +#include <boost/test/test_case_template.hpp> + +#include "boost/polygon/polygon.hpp" +using namespace boost::polygon; + +#include <iostream> + +typedef boost::mpl::list<int> test_types; + +BOOST_AUTO_TEST_CASE_TEMPLATE(polygon_90_data_test, T, test_types) { + typedef polygon_90_data<int> polygon_type; + typedef polygon_traits_90<polygon_type>::point_type point_type; + typedef polygon_type::iterator_type iterator_type; + + std::vector<point_type> data; + data.push_back(point_type(0, 0)); // 1 + data.push_back(point_type(10, 0)); // 2 + data.push_back(point_type(10, 10)); // 3 + data.push_back(point_type(0, 10)); // 4 + + polygon_type polygon; + polygon.set(data.begin(), data.end()); + + std::cout << "Interesting: " << std::endl; + for (polygon_type::compact_iterator_type it = polygon.begin_compact(); it != polygon.end_compact(); ++it) { + std::cout << *it << " "; + } + std::cout << std::endl; + + iterator_type it = polygon.begin(); + for (int i = 0; i < 2; i++) { + it++; + } + + iterator_type it_3rd = it; + it++; + BOOST_CHECK(it != it_3rd); +} diff --git a/libs/polygon/test/polygon_set_data_test.cpp b/libs/polygon/test/polygon_set_data_test.cpp new file mode 100644 index 000000000..d85936869 --- /dev/null +++ b/libs/polygon/test/polygon_set_data_test.cpp @@ -0,0 +1,111 @@ +// Boost.Polygon library polygon_set_data_test.cpp file + +// Copyright Andrii Sydorchuk 2015. +// Distributed under 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) + +// See http://www.boost.org for updates, documentation, and revision history. + +#define BOOST_TEST_MODULE POLYGON_SET_DATA_TEST +#include <vector> + +#include <boost/mpl/list.hpp> +#include <boost/test/test_case_template.hpp> + +#include "boost/polygon/polygon.hpp" +using namespace boost::polygon; +using namespace boost::polygon::operators; + +typedef boost::mpl::list<int> test_types; + +BOOST_AUTO_TEST_CASE_TEMPLATE(polygon_set_data_test1, T, test_types) { + typedef point_data<T> point_type; + typedef polygon_data<T> polygon_type; + typedef polygon_with_holes_data<T> polygon_with_holes_type; + typedef polygon_set_data<T> polygon_set_type; + + polygon_set_type pset; + std::vector<point_type> outbox; + outbox.push_back(point_type(0, 0)); + outbox.push_back(point_type(100, 0)); + outbox.push_back(point_type(100, 100)); + outbox.push_back(point_type(0, 100)); + pset.insert_vertex_sequence(outbox.begin(), outbox.end(), COUNTERCLOCKWISE, false); + std::vector<point_type> inbox; + inbox.push_back(point_type(20, 20)); + inbox.push_back(point_type(80, 20)); + inbox.push_back(point_type(80, 80)); + inbox.push_back(point_type(20, 80)); + pset.insert_vertex_sequence(inbox.begin(), inbox.end(), COUNTERCLOCKWISE, true); + + BOOST_CHECK(!pset.empty()); + BOOST_CHECK(!pset.sorted()); + BOOST_CHECK(pset.dirty()); + BOOST_CHECK_EQUAL(8, pset.size()); + + std::vector<polygon_with_holes_type> vpoly; + pset.get(vpoly); + BOOST_CHECK_EQUAL(1, vpoly.size()); + + polygon_with_holes_type poly = vpoly[0]; + BOOST_CHECK_EQUAL(5, poly.size()); + BOOST_CHECK_EQUAL(1, poly.size_holes()); +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(polygon_set_data_test2, T, test_types) { + typedef point_data<T> point_type; + typedef polygon_data<T> polygon_type; + typedef polygon_with_holes_data<T> polygon_with_holes_type; + typedef polygon_set_data<T> polygon_set_type; + + std::vector<point_type> data; + data.push_back(point_type(2,0)); + data.push_back(point_type(4,0)); + data.push_back(point_type(4,3)); + data.push_back(point_type(0,3)); + data.push_back(point_type(0,0)); + data.push_back(point_type(2,0)); + data.push_back(point_type(2,1)); + data.push_back(point_type(1,1)); + data.push_back(point_type(1,2)); + data.push_back(point_type(3,2)); + data.push_back(point_type(3,1)); + data.push_back(point_type(2,1)); + data.push_back(point_type(2,0)); + + polygon_type polygon; + set_points(polygon, data.begin(), data.end()); + + polygon_set_type pset; + pset.insert(polygon); + + std::vector<polygon_type> traps; + get_trapezoids(traps, pset, HORIZONTAL); + + BOOST_CHECK_EQUAL(4, traps.size()); +} + +BOOST_AUTO_TEST_CASE_TEMPLATE(polygon_set_data_test3, T, test_types) { + typedef point_data<T> point_type; + typedef polygon_data<T> polygon_type; + typedef polygon_with_holes_data<T> polygon_with_holes_type; + typedef polygon_set_data<T> polygon_set_type; + + std::vector<point_type> data; + data.push_back(point_type(0,0)); + data.push_back(point_type(6,0)); + data.push_back(point_type(6,4)); + data.push_back(point_type(4,6)); + data.push_back(point_type(0,6)); + data.push_back(point_type(0,0)); + data.push_back(point_type(4,4)); + data.push_back(point_type(5,4)); + + polygon_type polygon(data.begin(), data.end()); + polygon_set_type pset; + pset += polygon; + + BOOST_CHECK_EQUAL(32.0, area(polygon)); + BOOST_CHECK_EQUAL(32.0, area(polygon)); +} |