沃罗诺伊(Voronoi)的德劳内(Delaunay)增强:缺少具有非积分点坐标的三角形 [英] Delaunay from Voronoi with boost: missing triangle with non-integral point coordinates

问题描述

以下两个资源:

• 增强基本教程
• SO问题

• Boost basic tutorial
• SO Question

我用boost编写了Delaunay三角剖分.如果点坐标是整数，则可以正常工作(我生成了多个随机测试，但未观察到错误).但是，如果这些点是非整数的，我会发现许多不正确的三角剖分，这些三角剖分缺少边或边错误.

I wrote a Delaunay triangulation with boost. It works fine if the points coordinates are integral (I generated several random tests and I did not observed error). However if the points are non integral I found many incorrect triangulations with missing edges or wrong edges.

例如，此图像是使用四舍五入的值构建的，并且是正确的(请参见下面的代码)

For example this image has been build with rounded value and is correct (see code below)

但是此图像是使用原始值构建的，并且不正确(请参见下面的代码)

But this image as been build with raw values and is incorrect (see code below)

此代码重现了这两个示例(不显示).

This code reproduce this two examples (without the display).

#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;
}

推荐答案

如果点的坐标不是十进制，则效果很好

It works fine if the points coordinates are not decimal

玩弄了样本之后，我突然意识到您的意思不是当坐标不是十进制时".您的意思是积分".很大的不同.

After playing around with your sample I suddenly realized you didn't mean "when the coordinates are not decimal". You meant "integral". Big difference.

文档:点概念

预计坐标类型为整数

The coordinate type is expected to be integral

和

并非所有算法都支持浮点坐标类型，并且目前通常不适合与该库一起使用.

Floating point coordinate types are not supported by all the algorithms and generally not suitable for use with the library at present.

这篇关于沃罗诺伊(Voronoi)的德劳内(Delaunay)增强:缺少具有非积分点坐标的三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！