如何使boost的无限边缘提升到有限的边缘? [英] how to give make infinite edge in boost to a finite edge?

问题描述

我发现在boost库中，对于voronoi图，一些边缘数据是无限的.根据说明，它必须被裁剪.但是我找不到怎么做. 有人可以给我一个示例代码吗?

I find that in the boost library, for the voronoi diagram, some edge data is infinite. According to the instruction, it has to be clipped. But I cant find how to do it. Could anybody can give me a example code, please?

Thx

推荐答案

这是一个过时的问题，但是我在尝试解决完全相同的问题时发现了它.分享我所遇到的解决方案是公平的，因此下一个可怜的树液不必自己弄清楚.

This is a rather stale question, but I found it when trying to solve the exact same problem. It's only fair to share the solution I hit upon so the next poor sap doesn't have to figure it out themselves.

我不知道这是否是一种特别好的做事方法，我怀疑如果您开始使用弯曲的电池会很困难，但是对于我的目的来说它行得通.

I have no idea if this is a particularly good way to do things, and I suspect it would struggle if you started using curved cells, but it worked OK for my purposes.

基本问题是无限边缘只有一个顶点，因此必须自己计算方向向量.使用的方向垂直于由边缘分隔的两点之间的向量.

The basic problem is that you only have one vertex for the infinite edges, so you have to calculate the direction vector yourself. The direction to use is perpendicular to the vector between the two points separated by the edge.

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

typedef boost::polygon::point_data<int> point;
typedef voronoi_diagram<double>::cell_type cell_type;
typedef voronoi_diagram<double>::edge_type edge_type;
typedef voronoi_diagram<double>::vertex_type vertex_type;

int main(int argc, char *argv[])
{
   std::vector<point> points;

   // Populate with random points
   for (int i = 0; i < 50; i++)
   {
      points.push_back(point(60 + rand() % 500, 60 + rand() % 500));
   }

   voronoi_diagram<double> vd;
   construct_voronoi(points.begin(), points.end(), &vd);

   // vd now contains the voronoi diagram. Let's visualise it
   // pseudocode 'draw_line(x1, y1, x2, y2)'

   for (voronoi_diagram<double>::const_cell_iterator it = vd.cells().begin();
        it != vd.cells().end(); ++it)
   {
      const cell_type& cell = *it;
      const edge_type* edge = cell.incident_edge();

      do
      {
         if (edge->is_primary())
         {
            // Easy finite edge case
            if (edge->is_finite())
            {
               // Without this check each edge would be drawn twice
               // as they are really half-edges
               if (edge->cell()->source_index() < 
                   edge->twin()->cell()->source_index())
               {
                  draw_line(edge->vertex0()->x(), edge->vertex0()->y(),
                            edge->vertex1()->x(), edge->vertex1()->y());
               }
            }
            else
            {
               // This covers the infinite edge case in question.
               const vertex_type* v0 = edge->vertex0();
               // Again, only consider half the half-edges, ignore edge->vertex1()
               // to avoid overdrawing the lines
               if (v0)
               {
                  // Direction of infinite edge if perpendicular to direction
                  // between the points owning the two half edges. 
                  // Take the rotated right vector and multiply by a large 
                  // enough number to reach your bounding box
                  point p1 = points[edge->cell()->source_index()];
                  point p2 = points[edge->twin()->cell()->source_index()];
                  int end_x = (p1.y() - p2.y()) * 640;
                  int end_y = (p1.x() - p2.x()) * -640;

                  draw_line(v0->x(), v0->y(),
                            end_x, end_y);
               }
            }
         }
         edge = edge->next();
      } while (edge != cell.incident_edge());
   }
}

这篇关于如何使boost的无限边缘提升到有限的边缘?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！