Boost.Voronoi 在 C++ 中使用浮点输入生成不正确的 Voronoi 单元
问题描述 投票：0回答：1
我正在处理代表房间内行人头部位置（以米为单位）的实验数据。我的目标是用 C++ 生成围绕每个行人的 Voronoi 单元，以便我计算这些单元的面积。然而，在使用 Boost.Voronoi 生成 Voronoi 单元格并绘制它们之后，我发现单元格绘制不正确 – 这些点没有按照预期正确地分成单个单元格。
我在 Boost.Voronoi 文档中发现一条注释，默认情况下，输入坐标应为整数。为了使用真实世界坐标，我定义了允许使用浮点值的自定义点类型。下面是我用来生成 Voronoi 图并以文本形式输出数据的代码。此代码使用
g++-13
进行编译，但
clang-tidy在构建段期间会引发错误：
#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;
}
}
这里是如何绘制 Voronoi 单元的示例（如您所见，边缘似乎没有正确绘制）：
scipy.Voronoi
可视化相同的数据（据我了解 VOronoi 图，这是正确的代码）：
问题：如何在 Boost.Voronoi 中正确生成和可视化浮点输入的 Voronoi 单元？
我还应该注意到，Boost 提供了一个使用 OpenGL 来可视化 Voronoi 单元的示例，但该示例不再与 Qt6 兼容。我的目的是找到一个合适的解决方案，它也可以作为 Boost 库的更新示例，取代过时的 OpenGL 方法。
附录：
生成 Voronoi 图并使用 QT 绘制的完整 C++ 代码： 生成 Voronoi 图并绘制的完整代码：
#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();
}
第一个代码的输出：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)
用于生成此可视化的相应 Python 代码：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()
编辑：感谢来自@MSalters的建议，我能够构建Voronoi图，看起来几乎没问题：
1个回答
0
投票
投票
在我看来，“虚假”线是由于您尝试绘制多边形，就好像它们是单个线串一样。这不起作用，因为您不小心在相邻单元格的两个顶点之间绘制了线。
您可以煞费苦心地沿着您的路径回到一个共同的顶点，然后从那里继续。我想说最好将它们绘制为单独的系列：
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);
另请注意，由于 boost::geometry::is_valid
为 true，那么根据定义，您的多边形已经闭合：无需重复第一个点。这是一个演示，将输入缩放 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();
}
现场演示：
最新问题
- 将 Spring Boot 项目连接到 PostgreSQL 数据库的问题
- 填充接触图像边界的对象中的孔
- 32位操作系统跳转重新加载代码段后崩溃
- Java 哈希集。与 Hashmap 相比，重复项的处理有何不同？
- @jitsi/react-native-sdk 支持 React Native 展会吗？
- javascript 对象变量和函数
- veth 上的 XDP 无法处理非直连流量
- 修改 NestJS 中 OpenAPI (Swagger) 架构中出现的 DTO 名称
- 如何使用Echarts Js在MarkPoint属性中自动设置symbolSize
- 计算每行中的字符数，如果所有字符都低于某个数字，则丢弃
- JavaScript - 对象函数
- 当用户向下滚动时，如何使标题中的文本变小？
- 带有部分页面更新功能的 HTMX hx-get 从原始页面重新加载资源
- Oracle APEX - 数据库中过程内部的并行执行
- 是否可以简化这个javascript？
- 我该如何简化这个？
- find_package（MYSQL_CONCPP）错误--找不到MYSQL_CONCPP（缺少：MYSQL_CONCPP_DIR）
- 如何简化这个javascript？
- jQuery – 我怎样才能简化这个？
- Swf 卸载，但该 swf 中的 AS3 仍然执行
© www.soinside.com 2019 - 2024. All rights reserved.