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

在下面的 C++ 代码中，我基本上用 Polygon_with_holes_2 替换了 Polyline。对于 stop 的所有值，我现在得到拓扑有效的简化多边形。我编辑了你的输出函数。您可以将新函数 print_coords_for_geogebra() 的输出直接复制并粘贴到 Geogebra.

这是 simplify_test.cpp 的编辑版本。您可以使用原始 post.

中包含的相同 CMakeLists.txt 对其进行编译

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polyline_simplification_2/simplify.h>
#include <CGAL/Polygon_with_holes_2.h>
#include <iostream>
#include <vector>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Point_2<K> Point;
namespace PS = CGAL::Polyline_simplification_2;
typedef PS::Stop_below_count_ratio_threshold Stop;
typedef PS::Squared_distance_cost Cost;
typedef CGAL::Polygon_2<K> Polygon;
typedef CGAL::Polygon_with_holes_2<K> Polygon_with_holes;

void print_coords_for_geogebra(Polygon ext_ring)
{
  unsigned int i = 0;
  std::cout << "Polygon(";
  for (Point coord : ext_ring) {
    std::cout << "("
              << coord.x()
              << ", "
              << coord.y()
              << ")";
    if (i != ext_ring.size() - 1) std::cout << ", ";
    i++;
  }
  std::cout << ")" << std::endl << std::endl;
}

void simplify_test2(Polygon_with_holes polygon, double stop)
{
  Cost cost;
  polygon = PS::simplify(polygon, cost, Stop(stop));
  print_coords_for_geogebra(polygon.outer_boundary());
}

int main(int argc, char* argv[])
{
  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},
  };

  // Insert coordinates into the external ring of a polygon with holes
  Polygon ext_ring;
  for (std::vector<int> coord : coords) {
    Point pt(coord[0], coord[1]);
    ext_ring.push_back(pt);
  }
  Polygon_with_holes polygon(ext_ring);
  print_coords_for_geogebra(polygon.outer_boundary());
  for (double stop = 1.0; stop > 0.0; stop -= 0.1) {
    simplify_test2(polygon, stop);
  }
  return EXIT_SUCCESS;
}

Answer 2

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

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

CGAL折线简化导致自相交

CGAL Polyline Simplification results in self-intersection

c++

cgal