c++ - ブーストで無限エッジを有限エッジにする方法は?

Question

ブースト ライブラリのボロノイ図では、一部のエッジ データが無限であることがわかりました。指示に従って、それを切り取る必要があります。しかし、私はそれを行う方法を見つけることができません。誰かサンプルコードを教えてください。

どうも

Answer 1

これはかなり古い質問ですが、まったく同じ問題を解決しようとしたときに見つけました。私が思いついた解決策を共有するのは公正なことなので、次の貧しい樹液が自分で解決する必要はありません.

これが特に良い方法であるかどうかはわかりません。湾曲したセルを使い始めると苦労するのではないかと思いますが、私の目的には問題なく機能しました。

基本的な問題は、無限のエッジに対して頂点が 1 つしかないため、方向ベクトルを自分で計算する必要があることです。使用する方向は、エッジで区切られた 2 点間のベクトルに対して垂直です。

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