Boost.Voronoi 在 C++ 中使用浮点输入生成不正确的 Voronoi 单元

Question

我正在处理代表房间内行人头部位置（以米为单位）的实验数据。我的目标是用 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 单元的示例（如您所见，边缘似乎没有正确绘制）：

此外，为了进行比较，以下是如何在 Python 中使用

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图，看起来几乎没问题：

我将所有点（也是线段的点）乘以 100（米到厘米），然后在绘图时将点除以 100。现在看起来几乎没问题，但有些线穿过点和其他单元格。

Answer 1

在我看来，“虚假”线是由于您尝试绘制多边形，就好像它们是单个线串一样。这不起作用，因为您不小心在相邻单元格的两个顶点之间绘制了线。

您可以煞费苦心地沿着您的路径回到一个共同的顶点，然后从那里继续。我想说最好将它们绘制为单独的系列：

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();
}

现场演示：

图片：