Я посмотрел намного больше на ваши входные данные.Из этого я могу «представить» только два действительных полигона:
- Кольцо {{0,0}, {8, 3}, {10, 7}, {8, 9}, {0, 6},}
- Ring { {0,0}, {8, 3}, {8, 5}, {10, 7}, {8, 9}, {0, 6}, }
Let's define them in code:
Ring const inputs[] = {
Ring { {0,0}, {8, 3}, {10, 7}, {8, 9}, {0, 6}, }, // {0, 0},
Ring { {0,0}, {8, 3}, {8, 5}, {10, 7}, {8, 9}, {0, 6}, } // {0, 0},
};
The closing points commented out are in case you have a polygon model that requires the polygon be closed.
In this case, I've opted fro Boost Geometries polygon model, and parameterized it to be not-closed:
static constexpr bool closed_polygons = false;
using bgPoly = bgm::polygon;
using bgMulti = bgm::multi_polygon;
using Ring = bgPoly::ring_type;
Let's do the tests
To create the test-cases that are not using integral numbers, let's transform the polygon by shifting it from (0,0) to (1,1) and also scaling every dimension by a factor of π.
let's also check for input validity (and optionally attempt to correct for errors):
template void validate(std::string name, G& geom) {
std::cout
Finally, let's save some SVG visualizations of the input and triangulations
Demo Program
Live On Coliru
#include <boost/polygon/voronoi.hpp>
#include <cassert>
#include <iostream>
using boost::polygon::voronoi_builder;
using boost::polygon::voronoi_diagram;
struct Point
{
double a;
double b;
Point(double x = 0, double y = 0) : a(x), b(y) {}
};
namespace boost { namespace polygon {
template <> struct geometry_concept<Point> { typedef point_concept type; };
template <> struct point_traits<Point> {
typedef double coordinate_type;
static inline coordinate_type get(const Point& point, orientation_2d orient) {
return (orient == HORIZONTAL) ? point.a : point.b;
}
};
} }
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/algorithms/convex_hull.hpp>
#include <boost/geometry/algorithms/transform.hpp>
#include <boost/geometry/strategies/transform.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <boost/geometry/geometries/multi_polygon.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/io/io.hpp>
#include <fstream>
namespace bg = boost::geometry;
namespace bgm = bg::model;
namespace bgs = bg::strategy;
BOOST_GEOMETRY_REGISTER_POINT_2D(Point, double, bg::cs::cartesian, a, b)
static constexpr bool closed_polygons = false;
using bgPoly = bgm::polygon<Point, false, closed_polygons>;
using bgMulti = bgm::multi_polygon<bgPoly>;
using Ring = bgPoly::ring_type;
template <typename G> void validate(std::string name, G& geom) {
std::cout << name << ": " << bg::wkt(geom) << "\n";
std::string reason;
if (!bg::is_valid(geom, reason)) {
std::cout << name << ": " << reason << "\n";
bg::correct(geom);
std::cout << bg::wkt(geom) << "\n";
if (!bg::is_valid(geom, reason)) {
std::cout << name << " corrected: " << reason << "\n";
}
}
}
int main()
{
int count = 0;
Ring const inputs[] = {
Ring { {0,0}, {8, 3}, {10, 7}, {8, 9}, {0, 6}, }, // {0, 0},
Ring { {0,0}, {8, 3}, {8, 5}, {10, 7}, {8, 9}, {0, 6}, } // {0, 0},
};
bgs::transform::matrix_transformer<double, 2, 2> const transformations[] = {
{ 1, 0, 0, // identity transformation
0, 1, 0,
0, 0, 1 },
{ M_PI, 0, 1, // just to get nice non-integral numbers everywhere
0, M_PI, 1, // shift to (1,1) and scale everything by π
0, 0, 1 },
};
for (auto transformation : transformations) {
for (auto input : inputs) {
validate("Input", input);
Ring transformed_input;
bg::transform(input, transformed_input, transformation);
validate("transformed_input", transformed_input);
// Construction of the Voronoi Diagram.
voronoi_diagram<double> vd;
construct_voronoi(transformed_input.begin(), transformed_input.end(), &vd);
bgMulti out;
Ring triangle;
for (const auto& vertex: vd.vertices()) {
triangle.clear();
for(auto edge = vertex.incident_edge(); triangle.empty() || edge != vertex.incident_edge(); edge = edge->rot_next()) {
triangle.push_back(transformed_input[edge->cell()->source_index()]);
if (triangle.size() == 3) {
#if 0
std::cout << " -- found \n";
bgPoly t{triangle};
validate("Triangle", t);
out.push_back(t);
#else
out.push_back({ triangle });
#endif
triangle.erase(triangle.begin() + 1);
}
}
}
std::cout << "Out " << bg::wkt(out) << "\n";
{
std::ofstream svg("/tmp/svg" + std::to_string(++count) + ".svg");
boost::geometry::svg_mapper<Point> mapper(svg, 600, 600);
mapper.add(out);
mapper.map(out, R"(fill-opacity:0.5;fill:rgb(153,204,0);stroke:rgb(153,204,0);stroke-dasharray=5,5;stroke-width:2)");
mapper.add(transformed_input);
mapper.map(transformed_input, R"(fill-opacity:0.1;fill:rgb(204,153,0);stroke:red;stroke-width:3)");
}
} // inputs
} // transformations
}
Вывод:
Input: POLYGON((0 0,8 3,10 7,8 9,0 6))
transformed_input: POLYGON((0 0,8 3,10 7,8 9,0 6))
Out MULTIPOLYGON(((0 6,0 0,8 3,0 6)),((8 9,0 6,8 3,8 9)),((10 7,8 9,8 3,10 7)))
Input: POLYGON((0 0,8 3,8 5,10 7,8 9,0 6))
transformed_input: POLYGON((0 0,8 3,8 5,10 7,8 9,0 6))
Out MULTIPOLYGON(((0 6,0 0,8 3,0 6)),((8 5,0 6,8 3,8 5)),((8 9,0 6,8 5,8 9)),((8 9,8 5,10 7,8 9)),((10 7,8 5,8 3,10 7)))
Input: POLYGON((0 0,8 3,10 7,8 9,0 6))
transformed_input: POLYGON((1 1,26.1327 10.4248,32.4159 22.9911,26.1327 29.2743,1 19.8496))
Out MULTIPOLYGON(((1 19.8496,1 1,26.1327 10.4248,1 19.8496)),((26.1327 29.2743,1 19.8496,26.1327 10.4248,26.1327 29.2743)),((32.4159 22.9911,26.1327 29.2743,26.1327 10.4248,32.4159 22.9911)))
Input: POLYGON((0 0,8 3,8 5,10 7,8 9,0 6))
transformed_input: POLYGON((1 1,26.1327 10.4248,26.1327 16.708,32.4159 22.9911,26.1327 29.2743,1 19.8496))
Out MULTIPOLYGON(((1 19.8496,1 1,26.1327 10.4248,1 19.8496)),((26.1327 16.708,1 19.8496,26.1327 10.4248,26.1327 16.708)),((26.1327 29.2743,1 19.8496,26.1327 16.708,26.1327 29.2743)),((26.1327 29.2743,26.1327 16.708,32.4159 22.9911,26.1327 29.2743)),((32.4159 22.9911,26.1327 16.708,26.1327 10.4248,32.4159 22.9911)))
и соответствующие файлы SVG:
