c++ - 来自 Voronoi 的 Delaunay with boost：缺少具有非积分点坐标的三角形

问题描述

在这两个资源之后：

我用boost. 如果点坐标是积分的，它工作正常（我生成了几个随机测试，我没有观察到错误）。但是，如果这些点不是积分的，我会发现许多不正确的三角剖分缺少边缘或错误的边缘。

例如，这个图像是用四舍五入的值构建的并且是正确的（见下面的代码）

但是这个图像是用原始值构建的并且是不正确的（见下面的代码）

此代码重现了这两个示例（没有显示）。

#include <boost/polygon/voronoi.hpp>
using boost::polygon::voronoi_builder;
using boost::polygon::voronoi_diagram;

struct Point
{
  double a;
  double b;
  Point(double x, double y) : a(x), b(y) {}
};

namespace boost
{
  namespace polygon
  {
    template <>
    struct geometry_concept<Point>
    {
      typedef point_concept type;
    };

    template <>
    struct point_traits<Point>
    {
      typedef double coordinate_type;

      static inline coordinate_type get(const Point& point, orientation_2d orient)
      {
        return (orient == HORIZONTAL) ? point.a : point.b;
      }
    };
  }  // polygon
}  // boost

int main()
{ 

 std::vector<double> xx = {8.45619987, 9.96573889, 0.26574428, 7.63918524, 8.15187618, 0.09100718};
 std::vector<double> yy = {9.2452883, 7.0843455, 0.4811701, 3.1193826, 5.1336435, 5.5368374};

 // std::vector<double> xx = {8, 10, 0, 8, 8, 0};
 // std::vector<double> yy = {9, 7, 0, 3, 5, 6};

  std::vector<Point> points;

  for (int i = 0 ; i < xx.size() ; i++)
  {
    points.push_back(Point(xx[i], yy[i]));
  }

  // Construction of the Voronoi Diagram.
  voronoi_diagram<double> vd;
  construct_voronoi(points.begin(), points.end(), &vd);

  for (const auto& vertex: vd.vertices())
  {
    std::vector<Point> triangle;
    auto edge = vertex.incident_edge();
    do
    {
      auto cell = edge->cell();
      assert(cell->contains_point());

      triangle.push_back(points[cell->source_index()]);
      if (triangle.size() == 3)
      {   
        // process output triangles
        std::cout << "Got triangle: (" << triangle[0].a << " " << triangle[0].b << ") (" << triangle[1].a << " " << triangle[1].b << ") (" << triangle[2].a << " " << triangle[2].b << ")" << std::endl;
        triangle.erase(triangle.begin() + 1);
      }

      edge = edge->rot_next();
    } while (edge != vertex.incident_edge());
  }

  return 0;
}

标签： c++boostvoronoidelaunayboost-polygon

如果点坐标不是十进制的，它工作正常

在玩弄了你的样本之后，我突然意识到你的意思不是“当坐标不是十进制时”。你的意思是“整体”。巨大差距。

文档：点概念

坐标类型应为整数

和

并非所有算法都支持浮点坐标类型，目前一般不适合与库一起使用。

c++ - 来自 Voronoi 的 Delaunay with boost：缺少具有非积分点坐标的三角形

问题描述

解决方案

推荐阅读