c++ - CGAL 4.4 安排插入(arr，曲线)与一些曲线崩溃

Question

我尝试使用 CGAL 的 Arrangement，但由于不明确的原因，CGAL 4.4 中的某些曲线程序崩溃(在以前的版本 4.3 中没有这样的问题)。看问题的简单概述，曲线是字母D的轮廓，转换成线段:

  dDouble dpts { 16.261, 95.267,  ... 95.267,  16.261, 95.267};
  dPoint pts = ... // converting to exact points with 3 decimal places
  Curve_2 cu = Curve_2(pts.begin(), pts.end());
  insert(arr, cu); // <----  here crash, supposed bug in CGAL 4.4  ------

此外 insert() 也输出空行到标准输出。我用 cmake 提供了完整的例子配置文件和程序的输出。系统正在运行 Linux Mint Petra。

完整程序:

---

主要.cpp

---

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Cartesian.h>
#include <CGAL/Arr_segment_traits_2.h>
#include <CGAL/Arr_polyline_traits_2.h>
#include <CGAL/Arr_curve_data_traits_2.h>
#include <CGAL/Arrangement_with_history_2.h>
#include <CGAL/Arr_extended_dcel.h>
#include <CGAL/intersections.h>
#include <CGAL/Gmpq.h>

typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef typename Kernel::FT    Nt;
//***************************************************************
typedef CGAL::Aff_transformation_2<Kernel>              Aff_Transformation_2;
typedef CGAL::Point_2<Kernel>                           Point_2;
//***************************************************************
typedef CGAL::Arr_segment_traits_2<Kernel>              Segment_traits_2;
typedef CGAL::Arr_polyline_traits_2<Segment_traits_2>   Polyline_traits_2;
typedef Polyline_traits_2::Curve_2                      Curve_2;
typedef Polyline_traits_2                               Traits_2;  // renaming
typedef CGAL::Arr_extended_dcel<Traits_2, int, int, int> Dcel;
typedef CGAL::Arrangement_with_history_2<Traits_2, Dcel>  Arrangement_2;
//***************************************************************
typedef CGAL::Gmpq                                      Gmpq;
typedef std::deque<Point_2>    dPoint_2;
typedef std::deque<double>    dDouble;
#define   MULVAL    1000
inline int toInt(double d, int mul) { return int(d*mul + .5); }
inline Gmpq toGmpq(double d, int mul=MULVAL) { return Gmpq(toInt(d,mul), mul); }
inline Point_2 toPoint_2(double x, double y, int mul=MULVAL) { return Point_2( Nt(toGmpq(x,mul)),  Nt(toGmpq(y,mul))  ); }

int main() {
  // simple D letter outline
  dDouble dpts {     16.261, 95.267,  16.261, 48.027, 153.477, 48.027, 164.912, 49.104, 186.691, 51.458, 201.573, 54.251, 211.367, 56.921,
   225.415, 61.957, 238.134, 68.049, 249.204, 74.952, 258.604, 82.468, 266.944, 91.033, 272.727, 98.754, 277.419,107.216, 280.673,116.053,
   282.289,124.687, 282.364,132.995, 281.97, 136.238, 279.901,144.167, 276.218,152.181, 270.568,160.737, 262.216,170.448, 257.505,174.921,
   248.805,181.405, 237.688,187.749, 221.082,195.281, 218.006,196.525, 204.35, 201.024, 187.094,204.993, 183.018,205.735, 165.239,208.084,
   147.989,208.866,  16.261,208.866,  16.261,168.055,  38.329,167.772,  38.153, 95.267,  16.261, 95.267};

  dPoint_2 pts;
  for(int i=0;i<dpts.size()/2;i++) pts.push_back(toPoint_2(dpts[2*i],dpts[2*i+1])); // converting into exact points
  for(auto &p : pts) std::cout << p << " | "; std::cout << "\n";   // control output
  Arrangement_2    arr; // empty arrangement
  Curve_2 cu = Curve_2(pts.begin(), pts.end());

  insert(arr, cu); // bug in CGAL 4.4

  std::cout << "Working\n";
  return 0;
}

---

CMakeLists.txt

---

cmake_minimum_required(VERSION 2.8)
SET(CMAKE_VERBOSE_MAKEFILE ON)
set(XXX main)
project(XXX)
SET(CMAKE_BUILD_TYPE Debug)
set(CMAKE_CXX_FLAGS "-std=c++0x -frounding-math")
find_package(CGAL QUIET COMPONENTS Core )
include( ${CGAL_USE_FILE} )
add_executable(${XXX} ${XXX}.cpp)

---

输出:cmake。

---

-- The C compiler identification is GNU 4.8.1
-- The CXX compiler identification is GNU 4.8.1
...
-- Using /usr/bin/c++ compiler.
-- Requested component: Core
-- Requested component: MPFR
-- Requested component: GMP
..

---

程序输出

---

16.261 95.267 | 16.261 48.027 | 153.477 48.027 | 164.912 49.104 | 186.691 51.458 | 201.573 54.251 | 211.367 56.921 | 225.415 61.957 | 
238.134 68.049 | 249.204 74.952 | 258.604 82.468 | 266.944 91.033 | 272.727 98.754 | 277.419 107.216 | 280.673 116.053 | 282.289 124.687 | 
282.364 132.995 | 281.97 136.238 | 279.901 144.167 | 276.218 152.181 | 270.568 160.737 | 262.216 170.448 | 257.505 174.921 | 248.805 181.405 | 
237.688 187.749 | 221.082 195.281 | 218.006 196.525 | 204.35 201.024 | 187.094 204.993 | 183.018 205.735 | 165.239 208.084 | 147.989 208.866 | 
16.261 208.866 | 16.261 168.055 | 38.329 167.772 | 38.153 95.267 | 16.261 95.267 | 

terminate called after throwing an instance of 'CGAL::Precondition_exception'
  what():  CGAL ERROR: precondition violation!
Expr: i != INVALID_INDEX
File: /usr/local/include/CGAL/Arr_polyline_traits_2.h
Line: 619
Aborted

---

Answer 1

确实是 4.4 中的一个错误。

下面的补丁应该可以修复它。

将在下一次正式修订中修复。

diff --git a/Arrangement_on_surface_2/include/CGAL/Arr_polyline_traits_2.h b/Arrangement_on_surface_2/include/CGAL/Arr_polyline_traits_2.h
index 1a04d7d..aa48ded 100644
--- a/Arrangement_on_surface_2/include/CGAL/Arr_polyline_traits_2.h
+++ b/Arrangement_on_surface_2/include/CGAL/Arr_polyline_traits_2.h
@@ -2742,8 +2742,7 @@ namespace CGAL {
      *         If q is not in the x-range of cv, returns INVALID_INDEX.
      */
     template <typename Compare>
-    std::size_t locate_gen(const X_monotone_curve_2& cv,
-                            Compare compare) const
+    std::size_t locate_gen(const X_monotone_curve_2& cv, Compare compare) const
     {
       // The direction of cv. SMALLER means left-to-right and
       // otherwise right-to-left
@@ -2766,7 +2765,14 @@ namespace CGAL {
       Comparison_result res_to = compare(cv[to], ARR_MAX_END);
       if (res_to == EQUAL) return to;

-      if (res_to == res_from) return INVALID_INDEX;
+      // Check whether the point is either lexicographically to the left of
+      // the curve or lexicographically to the right of the curve.
+      if (res_to == res_from)
+        // If the x-monotone polyline is vertical, return the index of the
+        // segment that is closest to the point. Otherwise, the point is not
+        // in the x-range of the polyline.
+        return (is_vertical_2_object()(cv)) ?
+          ((res_to == SMALLER) ? from : to) : INVALID_INDEX;

       // Perform a binary search to locate the segment that contains q in its
       // range: