c++ - CGAL折线简化导致自相交

Question

我目前在使用 CGAL 的 Polyline Simplification 时遇到了一些麻烦.

更具体地说，对于以下示例，PS::simplify(ct, Cost(), Stop(0.2)) 生成一条自相交折线。在下图中，蓝色折线是 PS::simplify() 的输入折线，而绿色折线是结果(输出)折线。红色箭头指向生成的折线中的自交。

在下面，我从 2 个文件 simplify_test.cpp 和 CMakeLists.txt 中复制并粘贴了我的代码。安装所需的库后，要运行此示例，您可以将它们放在同一目录中，cd 到该目录，然后在您的终端中运行以下命令:

$ cmake .
$ make
$ ./simplify_test

这将输出结果坐标(下图中的绿色多段线)，其中包含自交。

我想知道:
(1)为什么会导致自相交
以及 (2) 可以做什么才不会导致自相交。

感谢您的帮助!

这是名为 simplify_test.cpp 的文件中的简化代码:

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polyline_simplification_2/simplify.h>

#include <iostream>
#include <string>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Point_2<K> Point;
typedef std::vector<Point> Polyline;
namespace PS = CGAL::Polyline_simplification_2;
typedef PS::Vertex_base_2<K> Vb;
typedef CGAL::Constrained_triangulation_face_base_2<K> Fb;
typedef CGAL::Triangulation_data_structure_2<Vb, Fb> TDS;
typedef CGAL::Constrained_Delaunay_triangulation_2<K, TDS, CGAL::Exact_predicates_tag> CDT;
typedef CGAL::Constrained_triangulation_plus_2<CDT> CT;
typedef PS::Stop_below_count_ratio_threshold Stop;
typedef PS::Squared_distance_cost Cost;

void print_coords(Polyline polyline) {
  std::cout << std::endl;
  std::cout << "Simplified coordinates:" << std::endl << std::endl;

  // Print out the simplified coordinates
  unsigned int i = 0;
  for (Point coord : polyline) {
    std::cout << "[ ";
    std::cout << coord.x();
    std::cout << ", ";
    std::cout << coord.y();
    std::cout << " ]";
    if (i != polyline.size() - 1) std::cout << ",";
    i++;
  }
  std::cout << std::endl << std::endl;
}

void simplify_test() {
  // Hard code a minimum working example where running PS::simplify results in
  // self-intersections. There are no self-intersections when {27, 9} is
  // omitted.
  std::vector<std::vector<int>> coords = {
      {64, 20}, {33, 27}, {27, 9}, {33, 18}, {44, 18}, {44, 8},
      {24, 0},  {0, 13},  {9, 49}, {84, 41}, {83, 29}, {64, 20},
  };
  // Simplification outputs:
  // [ 64, 20 ],[ 27, 9 ],[ 44, 18 ],[ 24, 0 ],
  // [ 9, 49 ],[ 83, 29 ],[ 64, 20 ],[ 64, 20 ]

  // Create polyline for simplifying later
  Polyline polyline;

  // Insert coordinates into polyline
  for (std::vector<int> coord : coords) {
    Point pt(coord[0], coord[1]);
    polyline.push_back(pt);
  }

  // Insert polyline into ct and run simplify()
  CT ct;
  ct.insert_constraint(polyline.begin(), polyline.end());
  PS::simplify(ct, Cost(), Stop(0.2));
  Polyline polyline_simplified;

  // Transfer simplified coordinates from ct to polyline for easy handling
  auto cit = ct.constraints_begin();
  for (auto vit = ct.points_in_constraint_begin(*cit);
       vit != ct.points_in_constraint_end(*cit); vit++) {
    polyline_simplified.push_back(*vit);
  }

  print_coords(polyline_simplified);
}

int main() {
  simplify_test();
}

这是 CMakeLists.txt 文件。

cmake_minimum_required(VERSION 3.1)
project(simplify_test LANGUAGES CXX)

set(CMAKE_CXX_STANDARD 20)
set(CMAKE_BUILD_TYPE Release)

# Detecting appropriate compiler
if (APPLE)
  set(CMAKE_C_COMPILER "/usr/local/opt/llvm/bin/clang")
  set(CMAKE_CXX_COMPILER "/usr/local/opt/llvm/bin/clang++")
elseif(UNIX) # implicit AND NOT APPLE
  set(CMAKE_CXX_COMPILER "g++-10")
  set(CMAKE_C_COMPILER "gcc-10")
endif()

# Finding appropriate packages
find_package(CGAL)

# Adding executables needed
add_executable(simplify_test ./simplify_test.cpp)

# Linking appropriate libraries required
target_link_libraries(
  simplify_test
  CGAL::CGAL
)

Answer 1

我进一步将它缩减为折线 std::vector<std::vector<int> > coords = { {64, 20}, {33, 27}, {27, 9}, {33, 18}, {44, 18}, {24, 0} };

您在约束迭代器的点中发现了一个错误。作为解决方法，您应该使用 Vertex_in_constraint_iterator 然后调用方法 point() .我将在 github 上提交问题并进行修复。