Boost.Voronoi generates incorrect Voronoi cells with floating-point input in C++
I'm working with experimental data representing head positions of pedestrians in meters within a room. My goal is to generate Voronoi cells in C++ that surround each pedestrian, allowing me to calculate the areas of these cells. However, after generating the Voronoi cells using Boost.Voronoi and plotting them, I found that the cells are incorrectly drawn – the points are not properly separated into individual cells as expected.
I came across a note in the Boost.Voronoi documentation that the input coordinates are, by default, expected to be integers. To work with real-world coordinates, I defined my custom point type that allows the use of floating-point values.
Below is the code I used to generate the Voronoi diagram and output the data in textual form. This code compiles with g++-13, but clang-tidy raises an error during the construction of segments:
#include <iostream>
#include <vector>
#include <format>
#include <boost/polygon/polygon.hpp>
#include <boost/polygon/voronoi.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/polygon.hpp>
#include <boost/polygon/voronoi.hpp>
#include <boost/polygon/voronoi_diagram.hpp>
using namespace std;
struct Position
{
using coordinate_type = double;
coordinate_type x, y;
};
using coordinate_type = Position::coordinate_type;
using segment_type = boost::polygon::segment_data<coordinate_type>;
using VoronoiDiagram = boost::polygon::voronoi_diagram<coordinate_type>;
/// settings necessarily for boost to be able to use Position as points:
template <>
struct boost::polygon::geometry_concept<Position> { typedef point_concept type; };
template <>
struct boost::polygon::point_traits<Position>
{
using coordinate_type = ::coordinate_type;
static inline coordinate_type get(const Position& point, boost::polygon::orientation_2d orient)
{
return (orient == boost::polygon::HORIZONTAL) ? point.x : point.y;
}
};
using polygonF = boost::geometry::model::polygon<Position, /*ClockWise=*/false, /*Closed=*/false>;
/// settings required to use boost::geometry::area(polygonF):
namespace boost { namespace geometry { namespace traits {
template <>
struct tag<Position> {
using type = point_tag;
};
template <>
struct coordinate_type<Position> {
using type = Position::coordinate_type;
};
template <>
struct coordinate_system<Position> {
using type = cs::cartesian;
};
template <>
struct dimension<Position> : boost::mpl::int_<2> {};
template <>
struct access<Position, 0> {
static double get(const Position& p) { return p.x; }
static void set(Position& p, const double& value) { p.x = value; }
};
template <>
struct access<Position, 1> {
static double get(const Position& p) { return p.y; }
static void set(Position& p, const double& value) { p.y = value; }
};
}}} // namespace boost::geometry::traits
polygonF verticesOfCell(const VoronoiDiagram::cell_type& voronoiCell)
{
polygonF polygon;
const auto* edge = voronoiCell.incident_edge();
do {
if (!edge)
{
break;
}
if (edge->is_primary())
{
if (edge->is_finite())
{
auto v0 = edge->vertex0();
auto v1 = edge->vertex1();
polygon.outer().emplace_back(v0->x(), v0->y());
polygon.outer().emplace_back(v1->x(), v1->y());
}
}
edge = edge->next();
} while (edge != voronoiCell.incident_edge());
return polygon;
}
int main(int argc, char *argv[])
{
//////////////// configuration points and segments:
std::vector<Position> positions
= {Position{0.476191, -0.952381}, Position{-0, -0.952381},
Position{-0.476191, -0.952381}, Position{-0.476191, -1.42857},
Position{-0.952381, -1.42857}, Position{-1.90476, -0.952381},
Position{-1.42857, -1.42857}, Position{-1.90476, -1.42857},
Position{-2.38095, -1.90476}, Position{-1.42857, -2.38095},
Position{-1.42857, -1.90476}, Position{-0.952381, -2.85714},
Position{-0.952381, -3.33333}, Position{-0, -3.80952},
Position{0.952381, -4.28571}, Position{0.476191, -4.28571},
Position{0.476191, -3.80952}, Position{0.952381, -3.33333},
Position{0.476191, -3.33333}, Position{-0, -2.38095},
Position{0.476191, -2.38095}, Position{0.952381, -1.90476},
Position{0.476191, -1.90476}, Position{-0, -1.90476},
Position{0.476191, -0.476191}, Position{-0.952381, -0.952381},
Position{0.476191, -1.42857}, Position{-0.476191, -2.38095},
Position{-0.952381, -2.38095}, Position{-2.38095, -2.85714},
Position{-1.90476, -3.33333}, Position{-1.42857, -3.33333},
Position{-0, -2.85714}, Position{-0.476191, -2.85714},
Position{-0, -3.33333}, Position{-0, -4.76191},
Position{0.952381, -2.38095}, Position{0.952381, -2.85714},
Position{0.476191, -2.85714}, Position{-0.476191, -1.90476},
Position{0.952381, -3.80952}, Position{1.42857, -2.85714},
Position{1.90476, -2.38095}, Position{0.952381, -4.76191},
Position{-0.476191, -5.2381}, Position{0.476191, -5.2381},
Position{1.90476, -3.33333}, Position{-2.85714, -2.38095},
Position{-2.38095, -1.42857}, Position{-2.38095, -0.952381},
Position{-1.42857, -2.85714}, Position{-1.90476, -1.90476},
Position{1.42857, -1.90476}, Position{2.38095, -2.85714},
Position{2.38095, -1.42857}, Position{2.38095, -0.952381},
Position{1.90476, -1.42857}, Position{2.38095, -1.90476},
Position{-1.90476, -2.38095}, Position{0.952381, -0.952381},
Position{-3.33333, -3.33333}, Position{-3.80952, -2.38095},
Position{-3.80952, -1.42857}, Position{-3.33333, -1.90476},
Position{-3.33333, -0.952381}, Position{-0.476191, -4.28571},
Position{-0, -1.42857}, Position{-0.952381, -1.90476}};
std::vector<segment_type> segments;
segments.emplace_back(Position(-6.5, -5.5), Position(3.5, -5.5)); // for clang can be compile error, for g++ compiles
segments.emplace_back(Position(3.5, -5.5), Position(3.5, 3));
segments.emplace_back(Position(3.5, 3), Position(-6.5, 3));
segments.emplace_back(Position(-6.5, 3), Position(-6.5, -5.5));
//////////////// construction of Voronoi diagram + printing cells
VoronoiDiagram vd;
boost::polygon::construct_voronoi(begin(positions), end(positions), begin(segments), end(segments), &vd);
unsigned int cell_index = 0;
for (auto it = vd.cells().begin(); it != vd.cells().end(); ++it) {
if (it->contains_point()) {
switch (it->source_category())
{
case boost::polygon::SOURCE_CATEGORY_SINGLE_POINT:
{
std::size_t index = it->source_index();
auto p = positions[index];
cout << format("Cell #{} contains a point: ({:.2f}, {:.2f})", cell_index, p.x, p.y) << endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT:
{
std::size_t index = it->source_index() - positions.size();
auto p0 = low(segments[index]);
cout << format("Cell #{} contains segment start point: ({:.2f}, {:.2f})", cell_index, p0.x(), p0.y()) << endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT:
{
std::size_t index = it->source_index() - positions.size();
auto p1 = high(segments[index]);
cout << format("Cell #{} contains segment end point: ({:.2f}, {:.2f})", cell_index, p1.x(), p1.y()) << endl;
break;
}
}
auto cellPolygon = verticesOfCell(*it);
if (!cellPolygon.outer().empty()) {
cout << "\t[vertices:" << cellPolygon.outer().size() << "]";
if (boost::geometry::is_valid(cellPolygon))
{
cout << "{area:" << boost::geometry::area(cellPolygon) << "}";
}
for (int i = 0; i < cellPolygon.outer().size(); ++i) {
const auto &p = cellPolygon.outer()[i];
cout << "\t(" << p.x << ", " << p.y << "),";
}
cout << endl;
}
} else {
std::size_t index = it->source_index() - positions.size();
auto p0 = low(segments[index]);
auto p1 = high(segments[index]);
cout << format("Cell #{} contains a segment: ({:.2f}, {:.2f}) -> ({:.2f}, {:.2f})", cell_index, p0.x(), p0.y(), p1.x(), p1.y()) << endl;
}
++cell_index;
}
}
Here is an example of how the Voronoi cells are drawn (as you can see, the edges don't seem to be correctly drawn):
Additionally, for comparison, here's how the same data is visualized using scipy.Voronoi in Python (as I understand VOronoi diagrams this is correct code):
Question: How can I correctly generate and visualize Voronoi cells in Boost.Voronoi for floating-point input?
I should also note that Boost provides an example using OpenGL to visualize Voronoi cells, but this example is no longer compatible with Qt6. My intention is to find a proper solution that could also potentially serve as an updated example for the Boost library, replacing the outdated OpenGL approach.
Appendix:
Full C++ code which generates Voronoi diagrams and draws with QT: Full code which generates Voronoi diagram and draws:
#include <iostream>
#include <vector>
#include <format>
#include <QtWidgets/QApplication>
#include <QtWidgets/QMainWindow>
#include <QtCharts/QChartView>
#include <QtCharts/QScatterSeries>
#include <QtCharts/QLineSeries>
#include <boost/polygon/polygon.hpp>
#include <boost/polygon/voronoi.hpp>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/polygon.hpp>
#include <boost/polygon/voronoi.hpp>
#include <boost/polygon/voronoi_diagram.hpp>
using namespace std;
struct Position
{
using coordinate_type = double;
coordinate_type x, y;
bool operator<(Position rhs) const;
bool operator==(Position rhs) const;
};
using coordinate_type = Position::coordinate_type;
using segment_type = boost::polygon::segment_data<coordinate_type>;
using VoronoiDiagram = boost::polygon::voronoi_diagram<coordinate_type>;
/// settings necessarily for boost to be able to use Position as points:
template <>
struct boost::polygon::geometry_concept<Position> { typedef point_concept type; };
template <>
struct boost::polygon::point_traits<Position>
{
using coordinate_type = ::coordinate_type;
static inline coordinate_type get(const Position& point, boost::polygon::orientation_2d orient)
{
return (orient == boost::polygon::HORIZONTAL) ? point.x : point.y;
}
};
using polygonF = boost::geometry::model::polygon<Position, /*ClockWise=*/false, /*Closed=*/false>;
/// settings required to use boost::geometry::area(polygonF):
namespace boost { namespace geometry { namespace traits {
template <>
struct tag<Position> {
using type = point_tag;
};
template <>
struct coordinate_type<Position> {
using type = Position::coordinate_type;
};
template <>
struct coordinate_system<Position> {
using type = cs::cartesian;
};
template <>
struct dimension<Position> : boost::mpl::int_<2> {};
template <>
struct access<Position, 0> {
static double get(const Position& p) { return p.x; }
static void set(Position& p, const double& value) { p.x = value; }
};
template <>
struct access<Position, 1> {
static double get(const Position& p) { return p.y; }
static void set(Position& p, const double& value) { p.y = value; }
};
}}} // namespace boost::geometry::traits
QPolygonF verticesOfCell(const VoronoiDiagram::cell_type& voronoiCell)
{
QPolygonF polygon;
const auto* edge = voronoiCell.incident_edge();
do {
if (!edge)
{
break;
}
if (edge->is_primary())
{
if (edge->is_finite())
{
auto v0 = edge->vertex0();
auto v1 = edge->vertex1();
polygon << QPointF{v0->x(), v0->y()};
polygon << QPointF{v1->x(), v1->y()};
}
}
edge = edge->next();
} while (edge != voronoiCell.incident_edge());
return polygon;
}
polygonF toBoostPolygon(const QPolygonF& polygonQt)
{
polygonF polygon;
for (const auto p : polygonQt)
polygon.outer().emplace_back(p.x(), p.y());
return polygon;
}
int main(int argc, char *argv[])
{
//////////////// configuration points and segments:
std::vector<Position> positions
= {Position{0.476191, -0.952381}, Position{-0, -0.952381},
Position{-0.476191, -0.952381}, Position{-0.476191, -1.42857},
Position{-0.952381, -1.42857}, Position{-1.90476, -0.952381},
Position{-1.42857, -1.42857}, Position{-1.90476, -1.42857},
Position{-2.38095, -1.90476}, Position{-1.42857, -2.38095},
Position{-1.42857, -1.90476}, Position{-0.952381, -2.85714},
Position{-0.952381, -3.33333}, Position{-0, -3.80952},
Position{0.952381, -4.28571}, Position{0.476191, -4.28571},
Position{0.476191, -3.80952}, Position{0.952381, -3.33333},
Position{0.476191, -3.33333}, Position{-0, -2.38095},
Position{0.476191, -2.38095}, Position{0.952381, -1.90476},
Position{0.476191, -1.90476}, Position{-0, -1.90476},
Position{0.476191, -0.476191}, Position{-0.952381, -0.952381},
Position{0.476191, -1.42857}, Position{-0.476191, -2.38095},
Position{-0.952381, -2.38095}, Position{-2.38095, -2.85714},
Position{-1.90476, -3.33333}, Position{-1.42857, -3.33333},
Position{-0, -2.85714}, Position{-0.476191, -2.85714},
Position{-0, -3.33333}, Position{-0, -4.76191},
Position{0.952381, -2.38095}, Position{0.952381, -2.85714},
Position{0.476191, -2.85714}, Position{-0.476191, -1.90476},
Position{0.952381, -3.80952}, Position{1.42857, -2.85714},
Position{1.90476, -2.38095}, Position{0.952381, -4.76191},
Position{-0.476191, -5.2381}, Position{0.476191, -5.2381},
Position{1.90476, -3.33333}, Position{-2.85714, -2.38095},
Position{-2.38095, -1.42857}, Position{-2.38095, -0.952381},
Position{-1.42857, -2.85714}, Position{-1.90476, -1.90476},
Position{1.42857, -1.90476}, Position{2.38095, -2.85714},
Position{2.38095, -1.42857}, Position{2.38095, -0.952381},
Position{1.90476, -1.42857}, Position{2.38095, -1.90476},
Position{-1.90476, -2.38095}, Position{0.952381, -0.952381},
Position{-3.33333, -3.33333}, Position{-3.80952, -2.38095},
Position{-3.80952, -1.42857}, Position{-3.33333, -1.90476},
Position{-3.33333, -0.952381}, Position{-0.476191, -4.28571},
Position{-0, -1.42857}, Position{-0.952381, -1.90476}};
std::vector<segment_type> segments;
segments.emplace_back(Position(-6.5, -5.5), Position(3.5, -5.5)); // for clang can be compile error, for g++ compiles
segments.emplace_back(Position(3.5, -5.5), Position(3.5, 3));
segments.emplace_back(Position(3.5, 3), Position(-6.5, 3));
segments.emplace_back(Position(-6.5, 3), Position(-6.5, -5.5));
//////////////// Qt's part - set up Widgets
QApplication app(argc, argv);
QMainWindow window;
QChart *chart = new QChart();
chart->setTitle("Voronoi Diagram Example");
chart->setAnimationOptions(QChart::AllAnimations);
QScatterSeries *pointsSeries = new QScatterSeries();
pointsSeries->setName("Source Points (head positions)");
pointsSeries->setMarkerSize(10.0);
for (const auto &pos : positions) {
pointsSeries->append(pos.x, pos.y);
}
QLineSeries *voronoiEdgesSeries = new QLineSeries();
voronoiEdgesSeries->setName("Voronoi Edges");
chart->addSeries(pointsSeries);
QLineSeries *segmentsSeries = new QLineSeries();
segmentsSeries->setName("Segments (room end)");
//////////////// construction of Voronoi diagram + printing cells
VoronoiDiagram vd;
boost::polygon::construct_voronoi(begin(positions), end(positions), begin(segments), end(segments), &vd);
unsigned int cell_index = 0;
for (auto it = vd.cells().begin(); it != vd.cells().end(); ++it) {
if (it->contains_point()) {
switch (it->source_category())
{
case boost::polygon::SOURCE_CATEGORY_SINGLE_POINT:
{
std::size_t index = it->source_index();
auto p = positions[index];
cout << format("Cell #{} contains a point: ({:.2f}, {:.2f})", cell_index, p.x, p.y) << endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT:
{
std::size_t index = it->source_index() - positions.size();
auto p0 = low(segments[index]);
cout << format("Cell #{} contains segment start point: ({:.2f}, {:.2f})", cell_index, p0.x(), p0.y()) << endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT:
{
std::size_t index = it->source_index() - positions.size();
auto p1 = high(segments[index]);
cout << format("Cell #{} contains segment end point: ({:.2f}, {:.2f})", cell_index, p1.x(), p1.y()) << endl;
break;
}
}
auto cellPolygon = verticesOfCell(*it);
if (!cellPolygon.empty()) {
cout << "\t[vertices:" << cellPolygon.size() << "]";
if (auto boostPolygon = toBoostPolygon(cellPolygon);
boost::geometry::is_valid(boostPolygon))
{
cout << "{area:" << boost::geometry::area(boostPolygon) << "}";
}
for (int i = 0; i < cellPolygon.size(); ++i) {
const QPointF &p = cellPolygon[i];
const QPointF &p2 = cellPolygon[(i + 1) % cellPolygon.size()];
voronoiEdgesSeries->append(p.x(), p.y());
voronoiEdgesSeries->append(p2.x(), p2.y());
cout << "\t(" << p.x() << ", " << p.y() << "),";
}
cout << endl;
}
} else {
std::size_t index = it->source_index() - positions.size();
auto p0 = low(segments[index]);
auto p1 = high(segments[index]);
cout << format("Cell #{} contains a segment: ({:.2f}, {:.2f}) -> ({:.2f}, {:.2f})", cell_index, p0.x(), p0.y(), p1.x(), p1.y()) << endl;
}
++cell_index;
}
//////////////// Qt: setting up charts && drawing && showing:
for (const auto& segment : segments)
{
auto p0 = segment.low();
auto p1 = segment.high();
segmentsSeries->append(p0.x(), p0.y());
segmentsSeries->append(p1.x(), p1.y());
}
chart->addSeries(voronoiEdgesSeries);
chart->addSeries(segmentsSeries);
chart->createDefaultAxes();
chart->setDropShadowEnabled(false);
QChartView *chartView = new QChartView(chart);
chartView->setRenderHint(QPainter::Antialiasing);
window.setCentralWidget(chartView);
window.resize(800, 600);
window.show();
return app.exec();
}
Output of first code:
Cell #0 contains segment end point: (-6.50, -5.50)
Cell #1 contains a segment: (-6.50, 3.00) -> (-6.50, -5.50)
Cell #2 contains segment start point: (-6.50, 3.00)
Cell #3 contains a segment: (-6.50, -5.50) -> (3.50, -5.50)
Cell #4 contains a segment: (3.50, 3.00) -> (-6.50, 3.00)
Cell #5 contains a point: (-3.33, -3.33)
[vertices:10]{area:2.60011} (-2, -3.75), (-2, -3), (-2, -3), (-2.5, -2.5), (-2.5, -2.5), (-4.45833, -2.5), (-4.45833, -2.5), (-4.4641, -3.4641), (-4.4641, -3.4641), (-2, -3.75),
Cell #6 contains a point: (-3.81, -2.38)
[vertices:8]{area:1.95833} (-2.5, -2.5), (-2.5, -1.5), (-2.5, -1.5), (-4.45833, -1.5), (-4.45833, -1.5), (-4.45833, -2.5), (-4.45833, -2.5), (-2.5, -2.5),
Cell #7 contains a point: (-3.81, -1.43)
[vertices:8]{area:1.95833} (-2.5, -1.5), (-2.5, -0.5), (-2.5, -0.5), (-4.45833, -0.5), (-4.45833, -0.5), (-4.45833, -1.5), (-4.45833, -1.5), (-2.5, -1.5),
Cell #8 contains a point: (-3.33, -0.95)
[vertices:8]{area:3.41267} (-2.5, -0.5), (-2.5, 1.45833), (-2.5, 1.45833), (-4.24264, 1.24264), (-4.24264, 1.24264), (-4.45833, -0.5), (-4.45833, -0.5), (-2.5, -0.5),
Cell #9 contains a point: (-2.38, -2.86)
[vertices:10]{area:1.25} (-1.5, -2.5), (-1.5, -1.5), (-1.5, -1.5), (-2.5, -1.5), (-2.5, -1.5), (-2.5, -2.5), (-2.5, -2.5), (-2, -3), (-2, -3), (-1.5, -2.5),
Cell #10 contains a point: (-2.38, -1.90)
[vertices:8]{area:1} (-1.5, -1.5), (-1.5, -0.5), (-1.5, -0.5), (-2.5, -0.5), (-2.5, -0.5), (-2.5, -1.5), (-2.5, -1.5), (-1.5, -1.5),
Cell #11 contains a point: (-2.38, -0.95)
[vertices:8]{area:1.95833} (-1.5, 1.45833), (-2.5, 1.45833), (-2.5, 1.45833), (-2.5, -0.5), (-2.5, -0.5), (-1.5, -0.5), (-1.5, -0.5), (-1.5, 1.45833),
Cell #12 contains a point: (-1.43, -3.33)
[vertices:12]{area:1.875} (-0.5, -3.5), (-0.5, -2.5), (-0.5, -2.5), (-1.5, -2.5), (-1.5, -2.5), (-2, -3), (-2, -3), (-2, -3.75), (-2, -3.75), (-1, -4), (-1, -4), (-0.5, -3.5),
Cell #13 contains a point: (-1.43, -2.38)
[vertices:8]{area:1} (-0.5, -2.5), (-0.5, -1.5), (-0.5, -1.5), (-1.5, -1.5), (-1.5, -1.5), (-1.5, -2.5), (-1.5, -2.5), (-0.5, -2.5),
Cell #14 contains a point: (-1.90, -1.90)
[vertices:8]{area:1} (-0.5, -1.5), (-0.5, -0.5), (-0.5, -0.5), (-1.5, -0.5), (-1.5, -0.5), (-1.5, -1.5), (-1.5, -1.5), (-0.5, -1.5),
Cell #15 contains a point: (-1.90, -0.95)
[vertices:8]{area:1.95833} (-0.5, 1.45833), (-1.5, 1.45833), (-1.5, 1.45833), (-1.5, -0.5), (-1.5, -0.5), (-0.5, -0.5), (-0.5, -0.5), (-0.5, 1.45833),
Cell #16 contains a point: (0.48, -5.24)
Cell #17 contains a point: (-0.48, -4.29)
[vertices:8]{area:0.75} (1, -4), (0.5, -3.5), (0.5, -3.5), (-0.5, -3.5), (-0.5, -3.5), (-1, -4), (-1, -4), (1, -4),
Cell #18 contains a point: (0.95, -3.81)
[vertices:8]{area:1} (0.5, -3.5), (0.5, -2.5), (0.5, -2.5), (-0.5, -2.5), (-0.5, -2.5), (-0.5, -3.5), (-0.5, -3.5), (0.5, -3.5),
Cell #19 contains a point: (0.95, -2.38)
[vertices:8]{area:1} (0.5, -2.5), (0.5, -1.5), (0.5, -1.5), (-0.5, -1.5), (-0.5, -1.5), (-0.5, -2.5), (-0.5, -2.5), (0.5, -2.5),
Cell #20 contains a point: (-0.95, -1.43)
[vertices:8]{area:1} (0.5, -1.5), (0.5, -0.5), (0.5, -0.5), (-0.5, -0.5), (-0.5, -0.5), (-0.5, -1.5), (-0.5, -1.5), (0.5, -1.5),
Cell #21 contains a point: (-0.48, -0.95)
[vertices:10]{area:2.71875} (1, -0), (1, 1.33333), (1, 1.33333), (-0.5, 1.45833), (-0.5, 1.45833), (-0.5, -0.5), (-0.5, -0.5), (0.5, -0.5), (0.5, -0.5), (1, -0),
Cell #22 contains a point: (1.90, -3.33)
[vertices:12]{area:1.82843} (1.82843, -3.82843), (2, -3), (2, -3), (1.5, -2.5), (1.5, -2.5), (0.5, -2.5), (0.5, -2.5), (0.5, -3.5), (0.5, -3.5), (1, -4), (1, -4), (1.82843, -3.82843),
Cell #23 contains a point: (1.43, -2.86)
[vertices:10] (1.5, -0.585786), (1.9375, -1.5), (1.9375, -1.5), (0.5, -1.5), (0.5, -1.5), (0.5, -2.5), (0.5, -2.5), (1.5, -2.5), (1.5, -2.5), (1.5, -0.585786),
Cell #24 contains a point: (1.90, -1.43)
[vertices:12] (1.9375, -1.5), (1.5, -2.41421), (1.5, -2.41421), (1.5, -0.5), (1.5, -0.5), (1, -0), (1, -0), (0.5, -0.5), (0.5, -0.5), (0.5, -1.5), (0.5, -1.5), (1.9375, -1.5),
Cell #25 contains a point: (2.38, -2.86)
[vertices:6]{area:0.478553} (2, -3), (1.5, -0.585786), (1.5, -0.585786), (1.5, -2.5), (1.5, -2.5), (2, -3),
Cell #26 contains a point: (2.38, -1.90)
[vertices:6]{area:0.837468} (1.5, -2.41421), (2.375, -0.5), (2.375, -0.5), (1.5, -0.5), (1.5, -0.5), (1.5, -2.41421),
Cell #27 contains a point: (2.38, -0.95)
[vertices:10]{area:1.62731} (2.375, -0.5), (1.44949, 1.44949), (1.44949, 1.44949), (1, 1.33333), (1, 1.33333), (1, -0), (1, -0), (1.5, -0.5), (1.5, -0.5), (2.375, -0.5),
Cell #28 contains segment start point: (3.50, -5.50)
Cell #29 contains a segment: (3.50, -5.50) -> (3.50, 3.00)
Cell #30 contains segment start point: (3.50, 3.00)
corresponding Python code used to generate this visualization:
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial import Voronoi, voronoi_plot_2d
# Definicja punktów
positions = np.array([
[0.476191, -0.952381], [-0, -0.952381],
[-0.476191, -0.952381], [-0.476191, -1.42857],
[-0.952381, -1.42857], [-1.90476, -0.952381],
[-1.42857, -1.42857], [-1.90476, -1.42857],
[-2.38095, -1.90476], [-1.42857, -2.38095],
[-1.42857, -1.90476], [-0.952381, -2.85714],
[-0.952381, -3.33333], [-0, -3.80952],
[0.952381, -4.28571], [0.476191, -4.28571],
[0.476191, -3.80952], [0.952381, -3.33333],
[0.476191, -3.33333], [-0, -2.38095],
[0.476191, -2.38095], [0.952381, -1.90476],
[0.476191, -1.90476], [-0, -1.90476],
[0.476191, -0.476191], [-0.952381, -0.952381],
[0.476191, -1.42857], [-0.476191, -2.38095],
[-0.952381, -2.38095], [-2.38095, -2.85714],
[-1.90476, -3.33333], [-1.42857, -3.33333],
[-0, -2.85714], [-0.476191, -2.85714],
[-0, -3.33333], [-0, -4.76191],
[0.952381, -2.38095], [0.952381, -2.85714],
[0.476191, -2.85714], [-0.476191, -1.90476],
[0.952381, -3.80952], [1.42857, -2.85714],
[1.90476, -2.38095], [0.952381, -4.76191],
[-0.476191, -5.2381], [0.476191, -5.2381],
[1.90476, -3.33333], [-2.85714, -2.38095],
[-2.38095, -1.42857], [-2.38095, -0.952381],
[-1.42857, -2.85714], [-1.90476, -1.90476],
[1.42857, -1.90476], [2.38095, -2.85714],
[2.38095, -1.42857], [2.38095, -0.952381],
[1.90476, -1.42857], [2.38095, -1.90476],
[-1.90476, -2.38095], [0.952381, -0.952381],
[-3.33333, -3.33333], [-3.80952, -2.38095],
[-3.80952, -1.42857], [-3.33333, -1.90476],
[-3.33333, -0.952381], [-0.476191, -4.28571],
[-0, -1.42857], [-0.952381, -1.90476]
])
# Definicja segmentów
segments = np.array([
[[-6.5, -5.5], [3.5, -5.5]],
[[3.5, -5.5], [3.5, 3]],
[[3.5, 3], [-6.5, 3]],
[[-6.5, 3], [-6.5, -5.5]]
])
# Generowanie diagramu Voronoi
vor = Voronoi(positions)
# Rysowanie diagramu Voronoi
fig, ax = plt.subplots()
voronoi_plot_2d(vor, ax=ax, show_vertices=False, line_colors='blue', line_width=1.5, point_size=5)
# Dodanie punktów źródłowych
ax.plot(positions[:, 0], positions[:, 1], 'ro', label="Source Points (head positions)")
# Dodanie segmentów
for segment in segments:
ax.plot(segment[:, 0], segment[:, 1], 'k-', lw=2, label="Segments (room end)")
# Ustawienia wykresu
ax.set_title("Voronoi Diagram Example")
ax.legend()
ax.set_aspect('equal')
# Wyświetlenie wykresu
plt.show()
EDIT: Thanks for suggestion from: @MSalters I was able to construct Voronoi diagram, which looks almost OK:
I multiplied all points (also segment's points) with 100 (meters to centimeters) then when drawing I divided points with 100. Now it looks almost OK, but some lines are going through points and other cells.
Solution
Looks to me the "spurious" lines are due to you trying plot polygons as if they're a single linestring. That doesn't work because you accidentally draw lines between two vertices from adjacent cells.
You could painstakingly retrace your path to a common vertex and continue from there. I'd say it's better to plot them as individual series:
QLineSeries* voronoiEdgesSeries = new QLineSeries();
voronoiEdgesSeries->setName("Voronoi Edges");
for (QPointF const& p : cellPolygon) {
voronoiEdgesSeries->append(p.x() / SCALE, p.y() / SCALE);
std::cout << "\t(" << p.x() / SCALE << ", " << p.y() / SCALE << "),";
}
chart->addSeries(voronoiEdgesSeries);
chart->legend()->markers(voronoiEdgesSeries)[0]->setVisible(false);
Note also, that since boost::geometry::is_valid is true, then by definition your polygon is already closed: no need to repeat the first point.
Here's a demo, scaling the inputs by 2^10:
#include <format>
#include <iostream>
#include <vector>
#include <QtCharts/QBarLegendMarker>
#include <QtCharts/QChartView>
#include <QtCharts/QLineSeries>
#include <QtCharts/QScatterSeries>
#include <QtWidgets/QApplication>
#include <QtWidgets/QMainWindow>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/box.hpp>
#include <boost/geometry/geometries/point.hpp>
#include <boost/polygon/point_data.hpp>
#include <boost/polygon/polygon.hpp>
#include <boost/polygon/voronoi.hpp>
#include <boost/polygon/voronoi_diagram.hpp>
#include <boost/polygon/gmp_override.hpp>
using namespace QtCharts;
struct Position {
using coordinate_type = double;
coordinate_type x, y;
};
using coordinate_type = Position::coordinate_type;
using segment_type = boost::polygon::segment_data<coordinate_type>;
using VoronoiDiagram = boost::polygon::voronoi_diagram<coordinate_type>;
/// settings necessarily for boost to be able to use Position as points:
template <> struct boost::polygon::geometry_concept<Position> {
typedef point_concept type;
};
template <> struct boost::polygon::point_traits<Position> {
using coordinate_type = ::coordinate_type;
static inline coordinate_type get(Position const& point, boost::polygon::orientation_2d orient) {
return (orient == boost::polygon::HORIZONTAL) ? point.x : point.y;
}
};
using polygonF = boost::geometry::model::polygon<Position, /*ClockWise=*/false, /*Closed=*/false>;
/// settings required to use boost::geometry::area(polygonF):
namespace boost { namespace geometry { namespace traits {
template <> struct tag<Position> { using type = point_tag; };
template <> struct coordinate_type<Position> { using type = Position::coordinate_type; };
template <> struct coordinate_system<Position> { using type = cs::cartesian; };
template <> struct dimension<Position> : boost::mpl::int_<2> {};
template <> struct access<Position, 0> {
static ::coordinate_type get(Position const& p) { return p.x; }
static void set(Position& p, ::coordinate_type const& value) { p.x = value; }
};
template <> struct access<Position, 1> {
static ::coordinate_type get(Position const& p) { return p.y; }
static void set(Position& p, ::coordinate_type const& value) { p.y = value; }
};
}}} // namespace boost::geometry::traits
QPolygonF verticesOfCell(VoronoiDiagram::cell_type const& voronoiCell) {
QPolygonF polygon;
auto const* edge = voronoiCell.incident_edge();
do {
if (!edge)
break;
if (edge->is_primary()) {
if (edge->is_finite()) {
auto v0 = edge->vertex0();
auto v1 = edge->vertex1();
polygon << QPointF{v0->x(), v0->y()};
polygon << QPointF{v1->x(), v1->y()};
}
}
edge = edge->next();
} while (edge != voronoiCell.incident_edge());
return polygon;
}
polygonF toBoostPolygon(QPolygonF const& polygonQt) {
polygonF polygon;
for (auto const& p : polygonQt)
polygon.outer().emplace_back(p.x(), p.y());
return polygon;
}
int main(int argc, char* argv[]) {
//////////////// configuration points and segments:
std::vector<Position> positions = {
{0.476191, -0.952381}, {-0, -0.952381}, {-0.476191, -0.952381}, {-0.476191, -1.42857},
{-0.952381, -1.42857}, {-1.90476, -0.952381}, {-1.42857, -1.42857}, {-1.90476, -1.42857},
{-2.38095, -1.90476}, {-1.42857, -2.38095}, {-1.42857, -1.90476}, {-0.952381, -2.85714},
{-0.952381, -3.33333}, {-0, -3.80952}, {0.952381, -4.28571}, {0.476191, -4.28571},
{0.476191, -3.80952}, {0.952381, -3.33333}, {0.476191, -3.33333}, {-0, -2.38095},
{0.476191, -2.38095}, {0.952381, -1.90476}, {0.476191, -1.90476}, {-0, -1.90476},
{0.476191, -0.476191}, {-0.952381, -0.952381}, {0.476191, -1.42857}, {-0.476191, -2.38095},
{-0.952381, -2.38095}, {-2.38095, -2.85714}, {-1.90476, -3.33333}, {-1.42857, -3.33333},
{-0, -2.85714}, {-0.476191, -2.85714}, {-0, -3.33333}, {-0, -4.76191},
{0.952381, -2.38095}, {0.952381, -2.85714}, {0.476191, -2.85714}, {-0.476191, -1.90476},
{0.952381, -3.80952}, {1.42857, -2.85714}, {1.90476, -2.38095}, {0.952381, -4.76191},
{-0.476191, -5.2381}, {0.476191, -5.2381}, {1.90476, -3.33333}, {-2.85714, -2.38095},
{-2.38095, -1.42857}, {-2.38095, -0.952381}, {-1.42857, -2.85714}, {-1.90476, -1.90476},
{1.42857, -1.90476}, {2.38095, -2.85714}, {2.38095, -1.42857}, {2.38095, -0.952381},
{1.90476, -1.42857}, {2.38095, -1.90476}, {-1.90476, -2.38095}, {0.952381, -0.952381},
{-3.33333, -3.33333}, {-3.80952, -2.38095}, {-3.80952, -1.42857}, {-3.33333, -1.90476},
{-3.33333, -0.952381}, {-0.476191, -4.28571}, {-0, -1.42857}, {-0.952381, -1.90476}};
auto SCALE = std::pow(2.0, 10);
std::vector<segment_type> segments;
segments.emplace_back(Position{-6.5, -5.5},
Position{3.5, -5.5}); // for clang can be compile error, for g++ compiles
segments.emplace_back(Position{3.5, -5.5}, Position{3.5, 3});
segments.emplace_back(Position{3.5, 3}, Position{-6.5, 3});
segments.emplace_back(Position{-6.5, 3}, Position{-6.5, -5.5});
for (Position& p : positions) {
p.x *= SCALE;
p.y *= SCALE;
}
for (auto& s : segments) {
s.low({s.low().x() * SCALE, s.low().y() * SCALE});
s.high({s.high().x() * SCALE, s.high().y() * SCALE});
}
//////////////// construction of Voronoi diagram + printing cells
VoronoiDiagram vd;
boost::polygon::construct_voronoi( //
begin(positions), end(positions), //
begin(segments), end(segments), //
&vd);
// SCALE = 1;
//////////////// Qt's part - set up Widgets
QApplication app(argc, argv);
QMainWindow window;
QChart* chart = new QChart();
chart->setTitle("Voronoi Diagram Example");
chart->setAnimationOptions(QChart::NoAnimation);
{
QScatterSeries* pointsSeries = new QScatterSeries();
pointsSeries->setName("Source Points (head positions)");
pointsSeries->setMarkerSize(10.0);
for (auto const& pos : positions)
pointsSeries->append(pos.x / SCALE, pos.y / SCALE);
chart->addSeries(pointsSeries);
}
QLineSeries* segmentsSeries = new QLineSeries();
segmentsSeries->setName("Segments (room end)");
for (unsigned int cell_index = 0; auto cell : vd.cells()) {
if (cell.contains_point()) {
switch (cell.source_category()) {
case boost::polygon::SOURCE_CATEGORY_SINGLE_POINT: {
size_t index = cell.source_index();
auto p = positions.at(index);
std::cout << std::format("Cell #{} contains a point: ({:.2f}, {:.2f})", cell_index,
p.x / SCALE, p.y / SCALE)
<< std::endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_SEGMENT_START_POINT: {
size_t index = cell.source_index() - positions.size();
auto p0 = low(segments.at(index));
std::cout << std::format("Cell #{} contains segment start point: ({:.2f}, {:.2f})",
cell_index, p0.x() / SCALE, p0.y() / SCALE)
<< std::endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_SEGMENT_END_POINT: {
size_t index = cell.source_index() - positions.size();
auto p1 = high(segments.at(index));
std::cout << std::format("Cell #{} contains segment end point: ({:.2f}, {:.2f})",
cell_index, p1.x() / SCALE, p1.y() / SCALE)
<< std::endl;
break;
}
case boost::polygon::SOURCE_CATEGORY_INITIAL_SEGMENT:
case boost::polygon::SOURCE_CATEGORY_REVERSE_SEGMENT:
case boost::polygon::SOURCE_CATEGORY_GEOMETRY_SHIFT:
case boost::polygon::SOURCE_CATEGORY_BITMASK: break;
}
auto cellPolygon = verticesOfCell(cell);
if (!cellPolygon.empty()) {
std::cout << "\t[vertices:" << cellPolygon.size() << "]";
{
std::string reason;
if (auto boostPolygon = toBoostPolygon(cellPolygon);
boost::geometry::is_valid(boostPolygon, reason)) {
std::cout << "{area:" << boost::geometry::area(boostPolygon) / SCALE / SCALE << "}";
} else {
std::cerr << "{INVALID:" << reason << "}";
return 3;
}
}
{
QLineSeries* voronoiEdgesSeries = new QLineSeries();
voronoiEdgesSeries->setName("Voronoi Edges");
for (QPointF const& p : cellPolygon) {
voronoiEdgesSeries->append(p.x() / SCALE, p.y() / SCALE);
std::cout << "\t(" << p.x() / SCALE << ", " << p.y() / SCALE << "),";
}
chart->addSeries(voronoiEdgesSeries);
chart->legend()->markers(voronoiEdgesSeries)[0]->setVisible(false);
}
std::cout << std::endl;
}
} else {
size_t index = cell.source_index() - positions.size();
auto p0 = low(segments.at(index));
auto p1 = high(segments.at(index));
std::cout << std::format("Cell #{} contains a segment: ({:.2f}, {:.2f}) -> ({:.2f}, {:.2f})",
cell_index, p0.x() / SCALE, p0.y() / SCALE, p1.x() / SCALE,
p1.y() / SCALE)
<< std::endl;
}
++cell_index;
}
//////////////// Qt: setting up charts && drawing && showing:
for (auto const& segment : segments) {
auto p0 = segment.low();
auto p1 = segment.high();
segmentsSeries->append(p0.x() / SCALE, p0.y() / SCALE);
segmentsSeries->append(p1.x() / SCALE, p1.y() / SCALE);
}
chart->addSeries(segmentsSeries);
chart->createDefaultAxes();
chart->setDropShadowEnabled(false);
QChartView* chartView = new QChartView(chart);
chartView->setRenderHint(QPainter::Antialiasing);
window.setCentralWidget(chartView);
window.resize(800, 600);
window.show();
return app.exec();
}
With a live demo:
The image:
- STM32 SPI LL DMA Transmit
- Setting LED value using one integer changes another integer
- How can i make my program testing goldbach hypotheis optimize in less than 5 sec
- equivalent of memcmp() in Java?
- How to ignore invalid options in getopt_long
- switching C compiler causes: Error Initializer cannot be specified for a flexible array member
- Why is "const char * const" not used as input string argument for a function in C?
- What is a "static" function in C?
- Is there a way to check if <string.h> is included?
- using C struct that is declared later
- How to use the Linux kernel hashtable API?
- 0%2 coming out to be 1
- What is the remainder after division by zero?
- How to create file as another user via C/C++ in Linux?
- Sizeof compound literal array producing side effects?
- Using poll() for a TCP server in C
- Segmentation Fault during Balancing of violated AVL tree
- How does C read an equality operator in the initialization of the counter of a "for" loop?
- How to configure codeblocks?
- AVX Intrinsic Clarification, 4x4 Matrix Multiplication Oddities
- FATFS via SPI for NUCLEOF103RB not working, returns FR_NOT_READY (3)
- Why doesn't __attribute__((constructor)) work in a static library?
- How do I gracefully exit an X11 event loop?
- "Palindrome recursive function" detects palindromes right but doesn't behave as expected
- Unexpected behaviour when trying to implement a queue with two stacks in C
- C Editor or Compiler for Windows CE
- STM32 Nucleo F303RE: USART1 DMA not receiving data from GY-25 sensor
- what is meanging of gcc option "-fmessage-length"?
- Promotions and conversions of variables in printf()
- What registers to save in the ARM C calling convention?