voronoi benchmark

gistfile1.cc

takram::Line2d clip(const boost::polygon::voronoi_diagram<double>::edge_type& edge) {
  const auto& cell1 = *edge.cell();
  const auto& cell2 = *edge.twin()->cell();
  takram::Vec2d origin, direction;
  if (cell1.contains_point() && cell2.contains_point()) {
    assert(cell1.source_category() == SOURCE_CATEGORY_SINGLE_POINT &&
           cell2.source_category() == SOURCE_CATEGORY_SINGLE_POINT);
    const auto& p1 = points_.at(cell1.source_index());
    const auto& p2 = points_.at(cell2.source_index());
    origin.x = (p1.x + p2.x) / 2.0;
    origin.y = (p1.y + p2.y) / 2.0;
    direction.x = p1.y - p2.y;
    direction.y = p2.x - p1.x;
  } else {
    assert(false);
  }
  if (edge.vertex0() && !edge.vertex1()) {
    return takram::Line2d(
        edge.vertex0()->x(),
        edge.vertex0()->y(),
        origin.x - direction.x * diagonal(),
        origin.y - direction.y * diagonal());
  }
  return takram::Line2d();
}

void run() {
  for (int i{}; i < 0xffff; ++i) {
    points_.emplace_back(takram::Vec2d::random(0, 0xffff));
  }
  edges_.clear();
  boost::timer timer;
  takram::VoronoiTriangulator voronoi;
  voronoi(points_);
  for (const auto& edge : voronoi) {
    if (edge.finite) {
      edges_.emplace_back(edge.a, edge.b);
    } else {
      edges_.emplace_back(edge.a, edge.a + edge.b * diagonal());
    }
  }
  std::cout << "triangle: " << timer.elapsed() << std::endl;
  timer.restart();
  boost::polygon::voronoi_diagram<double> diagram;
  boost::polygon::construct_voronoi(points_.begin(), points_.end(), &diagram);
  for (const auto& edge : diagram.edges()) {
    if (edge.is_finite()) {
      edges_.emplace_back(edge.vertex0()->x(), edge.vertex0()->y(),
                          edge.vertex1()->x(), edge.vertex1()->y());
    } else {
      edges_.emplace_back(clip(edge));
    }
  }
  std::cout << "boost: " << timer.elapsed() << std::endl;
}

std::vector<takram::Vec2d> points_;
std::vector<takram::Line2d> edges_;