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:
- Storing value infinity to a variable
- C compilers default behavior with constants
- Reading a 4 bytes date (big endian) from binary file
- -Werror=format: how can the compiler know
- check unused variable in C project
- When using clang on OSX, what controls the automatically added command line options?
- How to avoid using printf in a signal handler?
- Remove console window with SDL application
- gcc-arm-none-eabi 11.3 "is not implemented and will always fail"
- is this the right way to use Includes in C?
- Unexpected output from right rotate function
- How can I convert virtual address from user space to physical address?(in linux device driver)
- What is the difference between open and creat system call in c?
- Are all elements of the dirent structure open to use?
- Is there a way to utilize all XMM registers?
- In the C if-else statement, should the condition which is more likely to be true come first?
- Optimization for global and static variables
- Having trouble with char and scanf_s()
- Allegro error in DevC++
- Compress string using bits Operation in C
- What is the difference in atomic_load() and assignment?
- bind: invalid arguments AF_UNIX
- Explicit cast of nested pointers and const qualification
- Ignoring or redefining GCC Standard Predefined Macros
- Format strings safely when vsnprintf is not available
- How can I print to standard error in C with 'printf'?
- __STDC_LIB_EXT1__ availability in gcc and clang
- How to reassign void pointer pointing to a string to a new string in C
- memset() or value initialization to zero out a struct?
- Can quicksort be implemented in C without stack and recursion?