CGAL::2D Arrangements-7

本文主要是介绍CGAL::2D Arrangements-7，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

7 几何Traits

几何Traits封装了几何实体的定义以及处理这些几何实体的几何predicates和构造的实现，供Arrangement_on_surface_2类模板和其他周边模块使用。应用于Arrangement的各种算法所确定的最小要求被组织在精细几何特征概念的层次中。每个概念列出的需求只包括实现特定算法所需的完全必要的类型和操作。这种模块化结构产生了可控制的部件，这些部件可以毫不费力地生产、维护和使用。对于每个操作，还指定了其操作数必须满足的所有先决条件，因为这些先决条件可以进一步简化这些概念的模型的实现。每个特征类对一个或多个概念进行建模。本节详细描述了精化层次结构中的概念以及为这些概念建模的各种特性类。

构造和操纵Arrangement所需的所有代数都集中在特征类中。设计一个好的特性类所需的知识与开发包的其余部分或使用包所需的信息大不相同。它与计算几何的关系不大，主要涉及代数和数值计算。通过这种方式，可以在几乎不了解计算几何中的算法和数据结构的情况下开发新型曲线的特征类。在本节中，我们将讨论如何使用现有的traits类，但我们也将解释这些traits类模型的概念——这是每个此类新手开发人员的起点。

本节分为三个部分。第一部分描述了排列几何特征的细化层次概念。第二部分回顾了这些概念的各种模型。这些特征类处理不同的曲线族，例如线段、多段线、圆锥弧、贝塞尔曲线、代数曲线和球体上的测地线弧。最后一部分介绍了几何特征类的装饰器。traits类的装饰器将辅助数据附加到由原始traits类处理的几何对象，从而扩展它。

7.1 几何特征模板概念

7.1.1 基本概念

compare_x_2: 比较两个点的x坐标大小

compare_xy_2: 比较两点的字典序大小，首先x坐标，如果x坐标相同，就比较y坐标

7.1.2 相交

改进的Model需要支持下面附加的操作：

Split_2: 通过一个给定的在曲线上的点，分割一个X单调的曲线成2个子曲线

Are_mergeable_2: 判断2个x-monotone的曲线是否能合并成一个连续的x-monotone的曲线

Merge_2: Split_2的逆操作

Intersect_2:

7.1.3 支持任意曲线

ArrangementTraits_2 改进了ArrangementXMonotoneTraits_2，可以支持非X单调的曲线。比如圆，它会把圆切分成上半弧和下半弧，这个concept也支持如下额外的操作：

Make_x_monotone_2: 切分一个Curve_2类型的普遍曲线为2个弱x单调的曲线和弧立点

7.1.4 Landmark Concept

一个ArrangementApproximateTraits_2模型要支持下面的操作：

Approximate_2: 给定一个点p，使用不一定是多精度的数字类型来近似p的x和y坐标。我们将此操作用于近似计算——在搜索点的位置过程中执行的某些操作不需要精确，并且在执行时可以更快地执行，例如，使用固定精度的数字类型。

一个 ArrangementConstructXMonotoneCurveTraits_2 模型要支持下面的操作：

Construct_x_monotone_curve_2: 给定两点p1和p2，构造连接p1和p2的x单调曲线

大部分traits类是ArrangementTraits_2概念的模型，同时也有部分是ArrangementLandmarkTraits_2概念的模型。

7.1.5 The Construct Curve Concept（构建曲线的概念)

ArrangementConstructCurveTraits_2概念扩展了 ArrangementTraits_2概念。ArrangementConstructCurveTraits_2概念的模型必须支持下面的操作：

Construct_curve_2: 给定2个点p1和p2，构建一个连接p1和p2点的曲线

7.1.6 支持无界曲线和曲面

7.2 几何Traits 概念的模型

在本节中，我们将回顾作为前几节中介绍的概念模型的特征类。它们处理线段、圆弧、多段线、圆锥弧、有理函数、Bézier弧和代数曲线弧。最后一小节描述了用CGAL分布的几何特征类的装饰器，该装饰器通过将辅助数据附加到几何对象来扩展几何特征类。

7.2.1 Traits Classes for Line Segments and Linear Objects

有两个不同的特征类来处理线段。一个缓存曲线记录中的信息（请参见缓存段特征类一节），而另一个保留最少量的数据（请参见非缓存段特征类别一节）。对用前一个特征类实例化的排列的操作消耗了更多的空间，但对于密集排列（即由具有大量交叉点的线段引起的排列），它们更有效。另一个模型不仅处理（有界的）线段，还处理射线和直线；请参阅线性特征类一节。

The Caching Segment-Traits Class

到目前为止，大多数示例程序中使用的Arr_segment_traits_2<Kernel>类模板的实例是通过用必须符合Kernel概念的几何内核替换Kernel模板参数来实例化的；请参阅程序包概念。这个traits类将其点类型定义为Kernel:：point_2类型。然而，特征的Curve_2和X_monone_Curve_2嵌套类型都没有定义为Kernel:：Segment_2类型。内核段由其两个端点表示，与原始段端点的表示相比，当该段是几个分割操作的结果时，这些端点可能具有较大的比特大小表示。大比特大小表示可以显著减慢涉及这样的分段的各种特征类操作。（一个简单的解决方案是反复对所有计算的结果进行归一化。然而，我们的经验表明，不加区分的归一化会大大减慢Arrangement的构建速度。）

相反，Arr_segment_traits_2类模板除了表示两个端点之外，还表示使用其支撑线的线段。大多数计算都是在支撑线上进行的，支撑线不会随着线段的分割而改变。Arr_segment_traits_2类模板还缓存每个线段的一些附加信息，以加快各种predicates的速度，例如，有两个布尔标志，指示

（i）线段是否垂直和

（ii）线段目标点是否在字典上大于其源。支持线和两个布尔标志的计算被延迟到需要时的时间点，以实现效率的进一步提高。 X_monotone_curve_2对象仍然可以从两个端点或从一个kernel线段构造，并转换为X_monotone_curve_2对象。此外，还可以将X_monone_curve_2实例强制转换为 Kernel::Segment_2对象。因此，这两种类型可以相互转换。

在计算两个段之间的交集之前，应用一个有效的谓词来测试是否存在交集。这种优化具有可忽略不计的开销；因此，当构造由具有大量交点的线段引起的排列时，使用Arr_segment_traits_2<Kernel>类模板的实例仍然非常有效。效率受替换几何核的影响。使用Exact_predicates_Exact_constructions_kernel作为内核类型通常是一个不错的选择；线段端点的坐标表示为多精度有理数，这确保了所有计算的正确性，而不考虑输入。对多精度数字类型（如Gmpq）的计算比对机器精度浮点的计算耗时更长。上述类型的内核对象使用数值滤波来加快计算；参见Kernel_2和Kernel_3。如果线段的输入集合不具有退化；即，集合中没有两个段共享一个公共端点，也没有三个段在一个公共点相交，或者至少存在退化，但它们的数量相对较小，那么与容易出错的浮点运算相比，滤波计算只会产生可忽略的开销。事实上，在本手册中给出的几乎所有示例和应用程序中，预定义的过滤内核Exact_predicates_Exact_constructions_kernel都用于实例化线段特征类。

在下面的示例中，我们使用预定义的Exact_predicates_Exact_constructions_kernel来实例化我们的分段特征类。这个内核使用区间算术来过滤精确的计算。该程序从文件中读取一组具有整数坐标的线段，并计算它们的排列。默认情况下，它会打开位于examples文件夹中的fan_grids.dat输入文件，该文件包含104条线段，这些线段形成四个“扇形”网格，并形成密集排列，如图34.24（a）所示：

File Arrangement_on_surface_2/predefined_kernel.cpp

// Constructing an arrangement of intersecting line segments using the
// predefined kernel with exact constructions and exact predicates.
#include <list>
#include <CGAL/basic.h>
#include <CGAL/Timer.h>
#include "arr_exact_construction_segments.h"
#include "arr_print.h"
#include "read_objects.h"
int main (int argc, char* argv[]) {// Get the name of the input file from the command line, or use the default// fan_grids.dat file if no command-line parameters are given.const char* filename = (argc > 1) ? argv[1] : "fan_grids.dat";// Open the input file.std::ifstream in_file(filename);if (! in_file.is_open()) {std::cerr << "Failed to open " << filename << " ...\n";return 1;}std::list<Segment> segments;read_objects<Segment>(filename, std::back_inserter(segments));// Construct the arrangement by aggregately inserting all segments.Arrangement arr;CGAL::Timer timer;std::cout << "Performing aggregated insertion of "<< segments.size() << " segments.\n";timer.start();insert(arr, segments.begin(), segments.end());timer.stop();print_arrangement_size(arr);std::cout << "Construction took " << timer.time() << " seconds.\n";return 0;
}

The Non-Caching Segment-Traits Class

排列包提供了一个处理线段的替代线段特征类模板，即Arr_non_caching_segment_basic_trails_2<Kernel>类模板。该类模板和Arr_segment_traits_2<Kernel>类模板都由几何内核参数化，并对概念ArrangementTraits_2和ArrangementLandmarkTraits_2进行建模。[17] 类模板Arr_non_caching_segment_traits_2<Kernel>派生自实例Arr_non_caching_segment_basic_traits_2<Kernel>，该实例对ArrangementLandmarkTraits_2特征概念进行建模，但不对精化的ArrangementXMonotoneTraits_2概念进行建模。与Arr_segment_traits_2类模板一样，它派生自Kernel类型。与Arr_segment_traits_2类模板不同，它将其点类型和线段类型分别定义为Kernel:：point_2和Kernel：：segment_2，并且它定义的大多数操作都是Kernel类型的相应操作的委托。例如，函数Compare_xy_2定义为Kernel:：Compare_xy_2。剩下的操作是根据其他一些内核操作来定义的。例如，Compare_y_at_x_right_2谓词是根据Kernel:：Compare_slope_2谓词定义的（为了清楚起见，忽略先决条件）；有关此谓词的描述，请参见“基本概念”一节。在许多情况下，类模板Arr_non_caching_segment_basic_traits_2<Kernel>在构造成对内部不相交线段的排列方面的效率略低于Arr_segment_traits_2类模板，因为它根本不利用缓存。尽管如此，您可以选择使用这个traits类，因为它消耗的内存较少。对于相交线段的排列，可以使用类模板Arr_non_ching_segment_traits_2<Kernel>。然而，有利于Arr_segment_traits_2类模板的性能差异要大得多，尤其是当交叉点的数量很大时。

在下面的示例中，我们读取了一个输入文件，该文件包含一组内部成对不相交的线段。由于线段不相交，因此不会构造新的点，并且我们可以使用预定义的Exact_predicates_increact_constructions_Kernel实例化Arr_non_ching_segment_traits_basic_2＜Kernel＞类模板。请注意，我们使用insert_non_intersecting_curves（）函数来构造排列。默认情况下，示例打开位于examples文件夹中的Europe.dat输入文件，该文件包含3000多个具有浮点坐标的线段，这些线段构成了欧洲地图，如图34.24（b）所示：

Arrangement_on_surface_2/predefined_kernel_non_intersecting.cpp

// Constructing an arrangement of non-intersecting line segments using the
// predefined kernel with exact predicates.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Arr_non_caching_segment_basic_traits_2.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Timer.h>
#include <list>
#include <fstream>
typedef CGAL::Exact_predicates_inexact_constructions_kernel   Kernel;
typedef Kernel::FT                                            Number_type;
typedef CGAL::Arr_non_caching_segment_basic_traits_2<Kernel>  Traits_2;
typedef Traits_2::Point_2                                     Point_2;
typedef Traits_2::X_monotone_curve_2                          Segment_2;
typedef CGAL::Arrangement_2<Traits_2>                         Arrangement_2;
int main(int argc, char* argv[]) {// Get the name of the input file from the command line, or use the default// Europe.dat file if no command-line parameters are given.const char* filename = (argc > 1) ? argv[1] : "Europe.dat";// Open the input file.std::ifstream in_file(filename);if (! in_file.is_open()) {std::cerr << "Failed to open " << filename << " ...\n";return 1;}// Read the segments from the file.// The input file format should be (all coordinate values are double// precision floating-point numbers):// <n>                                 // number of segments.// <sx_1> <sy_1>  <tx_1> <ty_1>        // source and target of segment #1.// <sx_2> <sy_2>  <tx_2> <ty_2>        // source and target of segment #2.//   :      :       :      :// <sx_n> <sy_n>  <tx_n> <ty_n>        // source and target of segment #n.std::list<Segment_2>  segments;unsigned int n;in_file >> n;unsigned int i;for (i = 0; i < n; ++i) {double sx, sy, tx, ty;in_file >> sx >> sy >> tx >> ty;segments.push_back (Segment_2 (Point_2 (Number_type(sx), Number_type(sy)),Point_2 (Number_type(tx), Number_type(ty))));}in_file.close();// Construct the arrangement by aggregately inserting all segments.Arrangement_2 arr;CGAL::Timer timer;std::cout << "Performing aggregated insertion of " << n << " segments.\n";timer.start();insert_non_intersecting_curves (arr, segments.begin(), segments.end());timer.stop();// Print the arrangement dimensions.std::cout << "V = " << arr.number_of_vertices()<< ",  E = " << arr.number_of_edges()<< ",  F = " << arr.number_of_faces() << std::endl;std::cout << "Construction took " << timer.time() << " seconds.\n";return 0;
}

7.2.2 The Polyline and Polycurve Traits Classes（折线和分段曲线特征类）

多段线是连续的分段线性曲线。多段线特别令人感兴趣，因为它们可以用于近似平面中更复杂的曲线。同时，与高次代数曲线相比，它们更容易处理，因为有理算术足以对多段线进行计算，并以精确和稳健的方式构建多段线的排列。在这里，我们扩展了多段线的概念，并使用该术语来指代不一定是线性的子服务器链。但是，每个子曲线必须由处理过的曲线族中的两个点唯一定义（因此，可以从中唯一构建）；请参见“多段线特征类”一节。我们还提供了一个类似的特征类，它处理不一定是线性的、不受上述约束的连续分段曲线；请参阅多曲线特征类一节。

The Polyline Traits Class

Arr_polyline_traits_2<SubcurveTraits_2>模板类处理折线，它是下面4个概念的模型：

ArrangementTraits_2,
ArrangementDirectionalXMonotoneTraits_2
ArrangementConstructXMonotoneCurveTraits_2, and
ArrangementConstructCurveTraits_2.

实例化Arr_polyline_traits_2<SubcurveTraits_2>时替换模板参数SubcurveTraits_2的类型必须是对相同四个概念建模的几何特征类。在下文中，我们将使用模板参数SubcurveTraits_2作为Subcurve特征的类型。此外，如果Subcurve特征还对概念ArrangementApproximateTraits_2进行建模，则实例化的Arr_polyline_traits_2<SubcurveTraits>类型也对概念ArraangementApproxiateTraits_2_进行建模。（根据定义，对概念ArrangementApproximateTraits_2和ArrangementConstructXMonotoneCurveTraits_2建模意味着对概念ArraangementLandmarkTraits_2进行建模。对ArrangementConstructXMonotoneCurveTraits_2概念进行建模意味着，在给定两个输入点的情况下，Subcurve特征必须支持唯一（x单调）段的构建。

多段线特征类模板的实例从子服务器特征继承其嵌套点类型，即point_2，并定义嵌套类型Curve_2和X_monone_Curve_2，它们分别用于表示多段线和X单调多段线。嵌套类型Curve_2的多段线被存储为SuburveTraits_2:：Curve_2对象的向量，并且嵌套类型x_monone_Curve_2的x单调多段线存储为SubcurveTraits_2：：x_monone_Curve_2对象向量。嵌套的X_monone_curve_2类型继承自嵌套类型curve_2。默认情况下，Arr_segment_traits_2用作子服务器特征（如果省略了SubcurveTraits_2参数）。在这种情况下，嵌套类型SubcurveTraits_2:：Curve_2和SubcurveTraits_2:：X_monone_Curve_2是表示线段的相同类型。

A polyline can be constructed given one of the following inputs:

A range of points, where two succeeding points in the range represent the endpoints of a segment of the polyline.
A range of segments.
A pair of points or a single segment. In this case a polyline that consists of a single segment is constructed.

7.2.3 Traits Classes for Algebraic Curves(代数曲线特征类)

在我们的上下文中，曲线通常（但不一定）被定义为具有有理（或等价地，积分）系数的二元非零多项式的零集。我们称这种多项式和它们定义的曲线为代数。当处理线性曲线（例如，线段和多段线）时，具有有理系数可以保证所有交点也具有有理坐标，从而可以仅使用有理算术来构建和维护这些曲线的排列。2D Arrangements包还提供了几何特征类，这些几何特征类处理由阶数高于~1的代数多项式定义的代数曲线。不幸的是，由这些特征模型构建的交点的坐标是阶数大于1的一般代数数[18]。因此，很明显，我们必须使用不同于普通有理数的数字类型来表示点坐标，并能够对它们应用算术运算。

几种类型的代数曲线由多个特征模型处理。线性特征类一节介绍了一些处理线段的不同特征模型。随着处理代数曲线的特征类的引入，这种重复变得更加明显。不同的性状模型具有不同的性质。在某些情况下，它们是由不同的作者在不同的时间利用开发时可用的不同工具开发的。一般来说，你应该始终使用仍然满足你需求的最小特征模型，因为最专注的模型最有可能是最有效的。

Circular Arcs and Line Segments

圆弧和线段的Arrangement非常有用，并且在应用中经常出现，其中包含线段和圆弧的曲线组用于对复杂形状的边界进行建模。这样的曲线组可以比简单的多段线更紧密、更紧凑地拟合原始边界。例如，当将多边形扩展一定半径时，我们得到一个形状，其边界由线段和圆弧组成，线段对应于扩展的多边形边，圆弧由扩展的多边形顶点产生。例如，使用边界曲线的Arrangement，可以计算一组扩张多边形的并集。除了圆弧和线段Arrangement的重要性之外，事实证明，可以实现有效的特性模型，该模型处理仅限于圆弧和线段的曲线集。有理数不能以精确的方式表示在这种排列中可能出现的交点的坐标。因此，必须使用代数的数类型。然而，可以通过使用一种称为平方根扩展的有效类型的精确代数数来减少（一般）代数的数类型对性能的影响，该代数的数类型以几乎直接的方式使用有理算术。

平方根数据类型的形式如： α+βγ−−√, α, β, 和γ 都是有理数，平方根数也叫一根数，有理数γ被称为推广。每个具有特定扩展的子集在算术运算和次序关系下是封闭的；因此，它是一个有效的代数结构。类模板CGAL::Sqrt_extension<NT,Root>实现了这个扩展类型，它配备了一组算术运算的实现和顺序关系，这些运算和顺序关系利用了操作数的相同扩展。平方根扩展提供的算术运算和阶关系在满足相同扩展条件时的运行时间与有理数类型的相应算术运算的运行时间相当。当条件不满足时，顺序关系的运行时间仅略大。在实践中，使用表示（任意）代数数的数字类型会显著增加应用程序的运行时间。

我们把圆心坐标和半径平方为有理数的圆称为有理圆。这样一个圆的方程，即

(x−x0)2+(y−y0)2=r2，(x0,y0) 和 r代表圆的中心点和半径，分别的都是有理系数，

2D Arrangements包提供了一个名为Arr_circle_segment_traits_2<Kernel>的特性类模板，该模板专门处理线段、圆弧和整圆，并对ArrangementTraits_2和ArrangementDirectionalXMonotoneTraits_2概念进行建模；请参阅包2D正则化布尔集运算参考。请注意，它不是ArrangementLandmarkTraits_2概念的模型。它利用了平方根数的有效计算，这使得它对线段、圆弧和整个圆引起的排列很有吸引力。当traits类模板被实例化时，Kernel模板参数必须替换为对Kernel概念建模的几何内核。始终插入使用有理数类型的内核，例如Exact_predicates_Exact_constructions_kernel。观察traits类定义的嵌套类型Point_2，其坐标通常是2次代数数，与Kernel:：Point_2类型不同。点的坐标使用嵌套在traits类模板中的数字类型CoordNT表示。

7.3 Traits-Class Decorators（特征类装饰器）

几何特征类装饰器允许您将辅助数据附加到几何对象（曲线和点）。数据由装饰器自动操作，并分布到构建的几何实体中。可替换地，可以通过扩展由排列所使用的DCEL类提供的顶点、半边缘或面类型来维护附加信息；有关详细信息，请参阅扩展DCEL一节。然而，在许多情况下，可以方便地将数据附加到曲线本身，利用从每条曲线到其所有诱导的子曲线的附加数据字段的自动增殖。此外，由于两个半边缘与单个曲线相关联，将数据存储在曲线记录中一次既节省了空间，又避免了从一个半边缘到其双边缘的间接访问。

Arrangement_on_surface_2/consolidated_curve_data.cpp

// Associating a color attribute with segments using the consolidated
// curve-data traits.
#include <CGAL/basic.h>
#include <CGAL/Arr_consolidated_curve_data_traits_2.h>
#include "arr_exact_construction_segments.h"
enum Segment_color {RED, BLUE};
typedef CGAL::Arr_consolidated_curve_data_traits_2<Traits, Segment_color>Data_traits;
typedef Data_traits::Curve_2                               Colored_segment;
typedef CGAL::Arrangement_2<Data_traits>                   Colored_arr;
int main() {Colored_arr arr;// Construct an arrangement containing three RED line segments.insert(arr, Colored_segment(Segment(Point(-1, -1), Point(1, 3)), RED));insert(arr, Colored_segment(Segment(Point(2, 0), Point(3, 3)), RED));insert(arr, Colored_segment(Segment(Point(0, 3), Point(2, 5)), RED));// Insert three BLUE line segments.insert(arr, Colored_segment(Segment(Point(-1, 3), Point(4, 1)), BLUE));insert(arr, Colored_segment(Segment(Point(-1, 0), Point(4, 1)), BLUE));insert(arr, Colored_segment(Segment(Point(-2, 1), Point(1, 4)), BLUE));// Go over all vertices and print just the ones corresponding to intersection// points between RED segments and BLUE segments. Skip endpoints of// overlapping sections.for (auto vit = arr.vertices_begin(); vit != arr.vertices_end(); ++vit) {// Go over the current-vertex incident-halfedges and examine their colors.bool       has_red = false, has_blue = false;Colored_arr::Halfedge_around_vertex_const_circulator eit, first;eit = first = vit->incident_halfedges();do {// Get the color of the current halfedge.if (eit->curve().data().size() == 1) {Segment_color color = eit->curve().data().front();if (color == RED)       has_red = true;else if (color == BLUE) has_blue = true;}} while (++eit != first);// Print the vertex only if incident RED and BLUE edges were found.if (has_red && has_blue) {std::cout << "Red intersect blue at (" << vit->point() << ")\n";}}// Locate the edges that correspond to a red-blue overlap.for (auto eit = arr.edges_begin(); eit != arr.edges_end(); ++eit) {// Go over the incident edges of the current vertex and examine their colors.bool has_red{false}, has_blue{false};for (auto it = eit->curve().data().begin(); it != eit->curve().data().end();++it){if (*it == RED) has_red = true;else if (*it == BLUE) has_blue = true;}// Print the edge only if it corresponds to a red-blue overlap.if (has_red && has_blue)std::cout << "Red overlap blue at [" << eit->curve() << "]\n";}return 0;
}

这篇关于CGAL::2D Arrangements-7的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！