清丰网站建设价格php和网站建设

当前位置： 首页 > news >正文

清丰网站建设价格,php和网站建设,网络设计一个月多少钱,开商城网站多少钱7 几何Traits 几何Traits封装了几何实体的定义以及处理这些几何实体的几何predicates和构造的实现#xff0c;供Arrangement_on_surface_2类模板和其他周边模块使用。应用于Arrangement的各种算法所确定的最小要求被组织在精细几何特征概念的层次中。每个概念列出的需求只包括…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_2Kernel类模板的实例是通过用必须符合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_2Kernel类模板的实例仍然非常有效。效率受替换几何核的影响。使用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.24a所示 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::listSegment segments;read_objectsSegment(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_2Kernel类模板。该类模板和Arr_segment_traits_2Kernel类模板都由几何内核参数化并对概念ArrangementTraits_2和ArrangementLandmarkTraits_2进行建模。[17] 类模板Arr_non_caching_segment_traits_2Kernel派生自实例Arr_non_caching_segment_basic_traits_2Kernel该实例对ArrangementLandmarkTraits_2特征概念进行建模但不对精化的ArrangementXMonotoneTraits_2概念进行建模。与Arr_segment_traits_2类模板一样它派生自Kernel类型。与Arr_segment_traits_2类模板不同它将其点类型和线段类型分别定义为Kernel:point_2和Kernelsegment_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_2Kernel在构造成对内部不相交线段的排列方面的效率略低于Arr_segment_traits_2类模板因为它根本不利用缓存。尽管如此您可以选择使用这个traits类因为它消耗的内存较少。对于相交线段的排列可以使用类模板Arr_non_ching_segment_traits_2Kernel。然而有利于Arr_segment_traits_2类模板的性能差异要大得多尤其是当交叉点的数量很大时。 在下面的示例中我们读取了一个输入文件该文件包含一组内部成对不相交的线段。由于线段不相交因此不会构造新的点并且我们可以使用预定义的Exact_predicates_increact_constructions_Kernel实例化Arr_non_ching_segment_traits_basic_2Kernel类模板。请注意我们使用insert_non_intersecting_curves函数来构造排列。默认情况下示例打开位于examples文件夹中的Europe.dat输入文件该文件包含3000多个具有浮点坐标的线段这些线段构成了欧洲地图如图34.24b所示 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_2Kernel Traits_2; typedef Traits_2::Point_2 Point_2; typedef Traits_2::X_monotone_curve_2 Segment_2; typedef CGAL::Arrangement_2Traits_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::listSegment_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_2SubcurveTraits_2模板类处理折线它是下面4个概念的模型 ArrangementTraits_2,ArrangementDirectionalXMonotoneTraits_2ArrangementConstructXMonotoneCurveTraits_2, andArrangementConstructCurveTraits_2. 实例化Arr_polyline_traits_2SubcurveTraits_2时替换模板参数SubcurveTraits_2的类型必须是 对相同四个概念建模的几何特征类。在下文中我们将使用模板参数SubcurveTraits_2作为Subcurve特征的类型。此外如果Subcurve特征还对概念ArrangementApproximateTraits_2进行建模则实例化的Arr_polyline_traits_2SubcurveTraits类型也对概念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_2x_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_extensionNT,Root实现了这个扩展类型它配备了一组算术运算的实现和顺序关系这些运算和顺序关系利用了操作数的相同扩展。平方根扩展提供的算术运算和阶关系在满足相同扩展条件时的运行时间与有理数类型的相应算术运算的运行时间相当。当条件不满足时顺序关系的运行时间仅略大。在实践中使用表示任意代数数的数字类型会显著增加应用程序的运行时间。 我们把圆心坐标和半径平方为有理数的圆称为有理圆。这样一个圆的方程即 (x−x0)2(y−y0)2r2(x0,y0) 和 r代表圆的中心点和半径分别的都是有理系数 2D Arrangements包提供了一个名为Arr_circle_segment_traits_2Kernel的特性类模板该模板专门处理线段、圆弧和整圆并对ArrangementTraits_2和ArrangementDirectionalXMonotoneTraits_2概念进行建模请参阅包2D正则化布尔集运算参考。请注意它不是ArrangementLandmarkTraits_2概念的模型。它利用了平方根数的有效计算这使得它对线段、圆弧和整个圆引起的排列很有吸引力。当traits类模板被实例化时Kernel模板参数必须替换为对Kernel概念建模的几何内核。始终插入使用有理数类型的内核例如Exact_predicates_Exact_constructions_kernel。观察traits类定义的嵌套类型Point_2其坐标通常是2次代数数与Kernel:Point_2类型不同。点的坐标使用嵌套在traits类模板中的数字类型CoordNT表示。 ​ 图34.26 文件 Arrangement_on_surface_2/circles.cpp是三个圆构建的Arrangement每个圆都分割成2个x单调的圆弧红点表示这些圆弧的终点空心圆点表示交点点Vmax是三个圆的公共交点。 在以下代码示例中构建了三个完整圆的Arrangement如上图34.26所示。每个圆都被分割成两个x单调圆弧其端点被绘制为红色圆盘环形标记与交点相对应的顶点。一旦构造了Arrangement我们就定位排列中最大度的顶点。这个顶点的几何映射用Vmax表示是点4,3因为所有三个圆都在这个点相交并且相关的顶点有六条入射边。 文件Arrangement_on_surface_2/circles.cpp // Constructing an arrangement of circles using the circle-segment traits. #include CGAL/draw_arrangement_2.h #include arr_circular.h int main() {Arrangement arr;// Create a circle centered at the origin with radius 5 (C1).insert(arr, Curve(Circle(Rational_point(0, 0), Number_type(25))));// Create a circle centered at (7,7) with radius 5 (C2).insert(arr, Curve(Circle(Rational_point(7, 7), Number_type(25))));// Create a circle centered at (4,-0.5) with radius 3.5 ( ⁷⁄₂) (C3).Rational_point c3(4, Number_type(-1) / Number_type(2));insert(arr, Curve(Circle(c3, Number_type(49) / Number_type(4))));// Locate the vertex with maximal degree.auto vit arr.vertices_begin();Arrangement::Vertex_const_handle v_max vit;for (vit; vit ! arr.vertices_end(); vit)if (vit-degree() v_max-degree()) v_max vit;// Locate the vertex with maximum degree.std::cout The vertex with maximal degree in the arrangement is: v_max ( v_max-point() ) with degree v_max-degree() . std::endl;CGAL::draw(arr);return 0; } 下面列出了使用Arr_circle_segment_traits_2类模板的示例程序的常见类型并在头文件Arr_circle.h中进行了定义。尽管需要代数数字类型来表示曲线为圆或圆弧的点的坐标例如Arr_circle _segment_taits_2类模板处理的曲线rational内核就足够了经过过滤的内核进一步提高了性能。 #include CGAL/Exact_predicates_exact_constructions_kernel.h #include CGAL/Arr_circle_segment_traits_2.h #include CGAL/Arrangement_2.h typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel; typedef Kernel::FT Number_type; typedef CGAL::Arr_circle_segment_traits_2Kernel Traits; typedef Traits::CoordNT CoordNT; typedef Traits::Point_2 Point; typedef Traits::Curve_2 Curve; typedef Traits::Rational_point_2 Rational_point; typedef Traits::Rational_segment_2 Segment; typedef Traits::Rational_circle_2 Circle; typedef CGAL::Arrangement_2Traits Arrangement; Arr_circle_segment_traits_2中嵌套的Curve_2类型可用于表示圆、圆弧或线段。我们现在描述并演示了构造这种类型的曲线的各种方法。曲线对象可以从Kernel::Circle_2对象或从Kernel::Segment_2对象构造。圆弧通常由一个支撑圆和两个端点定义其中端点类型为Point_2具有有理或无理坐标。圆弧的方向由支撑圆的方向决定。类似地我们也支持在给定线段的支持线类型为Kernel::line_2和两个端点的情况下构建线段这两个端点可能具有无理坐标与Kernel::Segment_2类型不同。 请注意Kernel::Circle_2类型用于表示半径平方为有理数的圆其中半径本身可能是无理数的。但是如果已知半径是有理数的则建议使用半径以提高效率。因此也可以构造一个圆或圆弧指定圆心Kernel::Point_2、其有理半径Kernel::FT类型和方向。最后我们还支持由两个端点和位于端点之间的圆弧上的任意内部点来定义圆弧的构造。在这种情况下所有三个点都需要有有理坐标即它们都被给定为Kernel::Point_2对象。 ​ Figure 34.27 An arrangement of two full circles, two line segments, and three circular arcs as constructed in Arrangement_on_surface_2/circular_arcs.cpp. Endpoints are drawn as red disks and intersection points are drawn as rings. 以下示例演示了圆弧和线段的各种构造方法的用法。Arrangement结果如图34.27所示。注意CoordNT构造函数αβγ的用法它创建了一个2次代数数类型其值为。 Arrangement_on_surface_2/circular_arcs.cpp // Constructing an arrangement of various circular arcs and line segments. #include CGAL/draw_arrangement_2.h #include arr_circular.h #include arr_print.h int main() {std::listCurve curves;// Create a circle (C1) centered at the origin with squared radius 2.curves.push_back(Curve(Circle(Rational_point(0, 0), Number_type(2))));// Create a circle (C2) centered at (2, 3) with radius ³⁄₂. Note that// as the radius is rational we use a different curve constructor.Number_type three_halves Number_type(3) / Number_type(2);curves.push_back(Curve(Rational_point(2, 3), three_halves));// Create a segment (C3) of the line (y x) with rational endpoints.Segment s3 Segment(Rational_point(-2, -2), Rational_point(2, 2));curves.push_back(Curve(s3));// Create a line segment (C4) with the same supporting line (y x), but// having one endpoint with irrational coordinates.CoordNT sqrt_15 CoordNT(0, 1, 15); // sqrt(15)curves.push_back(Curve(s3.supporting_line(),Point(3, 3), Point(sqrt_15, sqrt_15)));// Create a circular arc (C5) that is the upper half of the circle centered at// (1, 1) with squared radius 3. Create the circle with clockwise orientation,// so the arc is directed from (1 - sqrt(3), 1) to (1 sqrt(3), 1).Rational_point c5(1, 1);Circle circ5(c5, 3, CGAL::CLOCKWISE);CoordNT one_minus_sqrt_3(1, -1, 3);CoordNT one_plus_sqrt_3(1, 1, 3);Point s5(one_minus_sqrt_3, CoordNT(1));Point t5(one_plus_sqrt_3, CoordNT(1));curves.push_back(Curve(circ5, s5, t5));// Create an arc (C6) of the unit circle, directed clockwise from// (-¹⁄₂, sqrt(3)/2) to (¹⁄₂, sqrt(3)/2).// The supporting circle is oriented accordingly.Rational_point c6(0, 0);Number_type half Number_type(1) / Number_type(2);CoordNT sqrt_3_div_2(Number_type(0), half, 3);Point s6(-half, sqrt_3_div_2);Point t6(half, sqrt_3_div_2);curves.push_back(Curve(c6, 1, CGAL::CLOCKWISE, s6, t6));// Create a circular arc (C7) defined by two endpoints and a midpoint,// all having rational coordinates. This arc is the upper right// quarter of a circle centered at the origin with radius 5.curves.push_back(Curve(Rational_point(0, 5), Rational_point(3, 4),Rational_point(5, 0)));// Construct the arrangement of the curves and print its size.Arrangement arr;insert(arr, curves.begin(), curves.end());print_arrangement_size(arr);CGAL::draw(arr);return 0; } 也可以使用类似的构造函数来构造表示x单调圆弧或线段的x单调曲线对象。完整的圆圈不是x单调的。 排列包提供的traits类模板Arr_circular_line_arc_traits_2CircularKernel也处理圆弧和线段。它是Arr_circle_segment_traits_2Kernel类模板的替代方案。这两个类模板虽然具有相似的目的但基于不同的概念并具有不同的特征。我们鼓励您尝试两者比较它们的性能并使用最适合您的案例的。 A Traits Class for Conic Arcs A conic curve is an algebraic curve of degree 2. Namely, it is the locus of all points (x,y) satisfying the equation , where the six coefficients 〈r,s,t,u,v,w〉 completely characterize the curve. The sign of the expression  determines the type of curve: If Δc0, the curve is an ellipse. A circle is a special case of an ellipse, where rs and t0. If Δc0, the curve is a parabola—an unbounded conic curve with a single connected branch. When rst0 we have a line, which can be considered as a degenerate parabola. If Δc0, the curve is a hyperbola. That is, it comprises of two disconnected unbounded branches. 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_2Traits, Segment_colorData_traits; typedef Data_traits::Curve_2 Colored_segment; typedef CGAL::Arrangement_2Data_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; }