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
, andArrangementConstructCurveTraits_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表示。
图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 (= 7/2) (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_2<Kernel> 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_2<Traits> 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::list<Curve> 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 3/2. 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// (-1/2, sqrt(3)/2) to (1/2, 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_2<CircularKernel>也处理圆弧和线段。它是Arr_circle_segment_traits_2<Kernel>类模板的替代方案。这两个类模板虽然具有相似的目的,但基于不同的概念,并具有不同的特征。我们鼓励您尝试两者,比较它们的性能,并使用最适合您的案例的。
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 Δc>0, the curve is an ellipse. A circle is a special case of an ellipse, where r=s and t=0.
-
If Δc=0, the curve is a parabola—an unbounded conic curve with a single connected branch. When r=s=t=0 we have a line, which can be considered as a degenerate parabola.
-
If Δc<0, 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_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
7 几何Traits 几何Traits封装了几何实体的定义以及处理这些几何实体的几何predicates和构造的实现,供Arrangement_on_surface_2类模板和其他周边模块使用。应用于Arrangement的各种算法所确定的最小要求被组织在精细几何特征概念的层次中。每个概念列出的需求只包括…...
linux系统下vscode portable版本的rust环境搭建004:rust
目的:希望在获得一个新的系统之后,以最简便快速的方式搭配一个rust的编程环境命令在线安装只执行这句就行了 :curl --proto https --tlsv1.2 -sSf https://sh.rustup.rs | sh,因为是要portable安装所以按照以下的方式执行。 下载…...
从汇编角度解释线程间互斥-mutex互斥锁与lock_guard的使用
多线程并发的竞态问题 我们创建三个线程同时进行购票,代码如下 #include<iostream> #include<thread> #include<list> using namespace std; //总票数 int ticketCount100; //售票线程 void sellTicket(int idx) {while(ticketCount>0){cou…...
高程 | 多态性(c++)
文章目录 📚多态📚运算符重载🐇定义🐇规则🐇友元运算符重载函数🐇成员运算符重载函数 📚虚函数📚纯虚函数和抽象类 📚多态 多态:同样的消息被不同类型的对象…...
LV.23 D2 开发环境搭建及平台介绍 学习笔记
一、Keil MDK-ARM简介及安装 Keil MDK,也称MDK-ARM,Realview MDK (Microcontroller Development Kit)等。目前Keil MDK 由三家国内代理商提供技术支持和相关服务。 MDK-ARM软件为基于Cortex-M、Cortex-R4、ARM7、ARM9处理器设备…...
[uniapp生命周期]详细讲解uniapp中那些属于vue生命周期,那些属于uniapp独有的生命周期,以及这中间的区别 相关的内容和api 代码注释
目录 1. Vue.js生命周期函数2.Vue生命周期函数代码beforeCreatecreatedbeforeMountmountedbeforeUpdateupdatedbeforeDestroydestroyed$nextTick$forceUpdate$destroy 3. UniApp独有的生命周期函数onLaunchonShowonHideonError 4.总结 在UniApp中,除了Vue.js的生命周…...
【动态规划】【记忆化搜索】【状态压缩】1681. 最小不兼容性
作者推荐 【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 本文涉及知识点 动态规划汇总 状态压缩 记忆化搜索 1681. 最小不兼容性 给你一个整数数组 nums 和一个整数 k 。你需要将这个数组划分到 k 个相同大小的子集中,使得同一…...
JVM-类加载器 双亲委派机制
申明:文章内容是本人学习极客时间课程所写,文字和图片基本来源于课程资料,在某些地方会插入一点自己的理解,未用于商业用途,侵删。 什么是JVM JVM是Java Virtual Machine(Java虚拟机)的缩写&a…...
vue axios 请求后端无法传参问题
vue请求后端无法传参问题 问题描述处理过程总结 问题描述 在学习vue时,使用axios调用后端,发现无法把参数正确传到后端,现象如下: 使用vue发起请求,浏览器上已经有传参,但是后端没接收到对应的用户名密码&…...
打印最小公倍数
打印最小公倍数 题目描述: 输入2个整数m和n,计算m和n的最小公倍数,并打印出结果 测试1: 输入:18 24 输出:72 测试2: 输入:18 6 输出:18解法思路: 最小公倍数是指两个…...
[AIGC] Java 和 Kotlin 的区别
好的,我还是以“萌萌哒小码农”的身份继续回答您的问题。 Java 和 Kotlin 是两种不同的编程语言,它们有许多共同点,但也有一些重要的区别。以下是一些常见的 Java 和 Kotlin 的区别: 语法 Kotlin 的语法比 Java 简洁得多&#…...
蓝桥杯电子类单片机提升一——超声波测距
前言 单片机资源数据包_2023 一、超声波测距原理 二、超声波测距的应用 1.超声波的发射 2.单片机知识补充:定时器 3.超声波的接收与计时 4.距离的计算 1)定时器1为16位自动重载+1T11.0592MHz 2)定时器1为16位自动重载&am…...
前端架构: 脚手架开发流程中的难点梳理
脚手架的开发流程 1 )开发流程 创建 npm 项目创建脚手架入口文件,最上方添加: #!/usr/bin/env node 配置 package.json, 添加 bin 属性编写脚手架代码将脚手架发布到 npm 2 )使用流程 安装脚手架 npm install -g your-own-cli …...
django中配置使用websocket
Django 默认情况下并不支持 WebSocket,但你可以通过集成第三方库如 channels 来实现 WebSocket 功能。channels 是一个 Django 应用,它提供了对 WebSocket、HTTP2 和其他协议的支持。 下面是如何在 Django 项目中使用 WebSocket 的基本步骤:…...
Rust复合类型详解
在Rust中,复合类型是一种能够将多个值组合在一起的数据类型。本篇博客将介绍两种常见的复合类型:元组(Tuple)和数组(Array)。 Tuple(元组) 元组是Rust中的一种复合类型,…...
学习 JavaScript 闭包
1. 前言 闭包是 JavaScript 中一种非常重要的概念,它允许函数访问其外部作用域中的变量,即使在函数被返回或者在其原始定义的作用域之外执行时仍然可以访问这些变量。 在讲解闭包之前我们得弄清楚下面的概念: 作用域链: JavaSc…...
VScode中配置 C/C++ 环境 | IT拯救者
文章目录 0 引言1. 下载编辑器VScode2. 下载编译器MinGW并解压3. 将MinGW添加至环境变量4. 配置VScode插件5. 运行代码6. 调整和优化7. 提示8. 例行格式条款9. 例行格式条款 0 引言 由于VScode毛毛张使用不习惯,因此配置教程记不住,不过毛毛张看到一篇不…...
基于Python实现Midjourney集成到(个人/公司)平台中
目前Midjourney没有对外开放Api,想体验他们的服务只能在discord中进入他们的频道进行体验或者把他们的机器人拉入自己创建的服务器中;而且现在免费的也用不了了,想使用就得订阅。本教程使用midjourney-api这个开源项目,搭建Midjou…...
蓝桥杯刷题--python-6
0最大距离 - 蓝桥云课 (lanqiao.cn) n=int(input()) nums=list(map(int,input().split()))max_=float(-inf) for i in range (n):for j in range (i+1,n):tmp=abs(i-j)+abs(nums[i]-nums[j])max_=max(tmp,max_) print(max_) 0最长递增 - 蓝桥云课 (lanqiao.cn) import os im…...
node+vue3+mysql前后分离开发范式——实现对数据库表的增删改查
文章目录 ⭐前言⭐ 功能设计与实现💖 node后端操作数据库实现增删改查💖 vue3前端实现增删改查⭐ 效果⭐ 总结⭐ 结束⭐结束⭐前言 大家好,我是yma16,本文分享关于 node+vue3+mysql前后分离开发范式——实现对数据库表的增删改查。 技术选型 前端:vite+vue3+antd 后端:…...
【Android】使用Apktool反编译Apk文件
文章目录 1. 下载Apktool1.1 Apktool官网下载1.2 百度网盘下载 2. 安装Apktool3. 使用Apktool3.1 配置Java环境3.2 准备Apk文件3.3 反编译Apk文件3.3.1 解包Apk文件3.3.2 修改Apk文件3.3.3 打包Apk文件3.3.4 签名Apk文件 1. 下载Apktool 要使用Apktool,需要准备好 …...
(04)Hive的相关概念——order by 、sort by、distribute by 、cluster by
Hive中的排序通常涉及到order by 、sort by、distribute by 、cluster by 一、语法 selectcolumn1,column2, ... from table [where 条件] [group by column] [order by column] [cluster by column| [distribute by column] [sort by column] [limit [offset,] rows]; …...
Django模板(二)
标签if 标签在渲染过程中提供使用逻辑的方法,比如:if和for 标签被 {% 和 %} 包围,如下所示: 由于在模板中,没有办法通过代码缩进判断代码块,所以控制标签都需要有结束的标签 if判断标签{% if %} {% endif %} : # athlete_list 不为空 {% if athlete_list %}# 输出 ath…...
勒索病毒最新变种.faust勒索病毒来袭,如何恢复受感染的数据?
引言: 随着我们进入数字化时代,数据的重要性变得愈发显著,而网络安全威胁也日益增加。.faust勒索病毒是其中一种备受恶意分子钟爱的危险工具,它通过加密用户文件并勒索高额赎金来对个人和组织发起攻击。本文将深入探讨.faust勒索…...
python 人脸检测器
import cv2# 加载人脸检测器 关键文件 haarcascade_frontalface_default.xml face_cascade cv2.CascadeClassifier(haarcascade_frontalface_default.xml)# 读取图像 分析图片 ren4.png image cv2.imread(ren4.png) gray cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)# 进行人脸…...
机器学习与深度学习
什么是机器学习 机器学习是一门跨学科的学科,它致力于研究和开发让计算机能够模拟人类学习行为的技术和方法。机器学习涉及多个学科的知识,如概率论、统计学、逼近论、凸分析、算法复杂度理论等,这些学科为机器学习提供了理论基础和数学工具…...
算法训练营day27(补),贪心算法1
import "sort" //455. 分发饼干 func findContentChildren(g []int, s []int) int { sort.Ints(g) sort.Ints(s) // g代表胃口数组, s代表饼干数组 count : 0 // 统计数量 //饼干下标 index : len(s) - 1 // 胃口循环 for i : len(g) - 1; i > 0; i--…...
[office] excel2003限定单元格输入值范围教程 #微信#经验分享
excel2003限定单元格输入值范围教程 在Excel中录入数据前都会设置单元格的一些格式,其中会有限定单元格输入值范围的需求,或许有的朋友并不知道单元格该如何限定输入范围,如果不懂的朋友欢迎一起来学习研究。下面是小编带来的关于excel2003限…...
OLED显示红外遥控键码
基本原理 本遥控器的编码是NEC编码,为PWM(脉冲宽度调制)。 发射红外载波的时间固定,通过改变不发射载波的时间来改变占空比。 逻辑“0”是由0.56ms的38KHZ载波和0.560ms的无载波间隔组成;逻辑“1”是由0.56ms的38KHZ…...
LabVIEW智能温度监控系统
LabVIEW智能温度监控系统 介绍了一个基于LabVIEW的智能温度监控系统,实现对工业环境中温度的实时监控与调控。通过集成传感器技术和LabVIEW软件平台,系统能够自动检测环境温度,及时响应温度变化,并通过图形用户界面(GUI)为用户提…...
专业140+总分420+浙江大学842信号系统与数字电路考研经验电子信息与通信,真题,大纲,参考书。
今年考研已经结束,初试专业课842信号系统与数字电路140,总分420,很幸运实现了自己的目标,被浙大录取,这在高考是想都不敢想的学校,在考研时实现了,所以大家也要有信心,通过自己努力实…...
C语言学习day15:数组强化训练
题目一: 称体重:分别给10个值,来获得最大值 思路: 定义数组,给数组内赋10个值第一个下标的值与第二个下标的值进行比较定义max,将比较得来的较大的值赋值给max一直比较直到比较到最后一个下标࿰…...
缓存穿透、缓存击穿与缓存雪崩
缓存穿透、缓存击穿与缓存雪崩 1.本质区别 缓存穿透指的是数据库不存在数据,导致无法缓存,每次查询都查数据库,数据库压垮 缓存击穿指的是缓存键值对key过期了,key过期期间,大量请求访问,不经过缓存&…...
一周学会Django5 Python Web开发-项目配置settings.py文件-模版配置
锋哥原创的Python Web开发 Django5视频教程: 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计17条视频,包括:2024版 Django5 Python we…...
CF1845 D. Rating System [思维题+数形结合]
传送门:CF [前题提要]:自己在做这道题的时候思路完全想错方向,导致怎么做都做不出来,看了题解之后感觉数形结合的思考方式挺好的(或者这种做法挺典的),故写篇题解记录一下 题目很简单,不再解释.先不考虑 k k k,想想是一种什么情况?很显然应该是跟下图一样是一个折线图的变化.…...
HeidiSQL安装配置(基于小皮面板(phpstudy))连接MySQL
下载资源 对于这款图形化工具,博主建议通过小皮面板(phpstudy)来下载即可,也是防止你下载到钓鱼软件,小皮面板(phpstudy)如果你不懂是什么,请看下面链接这篇博客 第二篇:…...
【蓝桥2013】错误票据
错误票据 题目描述 某涉密单位下发了某种票据,并要在年终全部收回。 每张票据有唯一的 ID 号。全年所有票据的 ID 号是连续的,但 ID 的开始数码是随机选定的。 因为工作人员疏忽,在录入 ID 号的时候发生了一处错误,造成了某个…...
nvm对node版本进行管理及疑难解决,vue项目搭建与启动
一、nvm安装与node版本管理 nvm安装 1、nvm地址:https://github.com/coreybutler/nvm-windows/releases 2、无需配置安装包,nvm-setup-v1.1.10.zip 解压后双击nvm-setup.exe,选择安装路径,一路next即可 打开dos窗口输入nvm vers…...
Redisson分布式锁 原理 + 运用 记录
Redisson 分布式锁 简单入门 pom <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.13.6</version></dependency>配置类 package com.hmdp.config;import org.redisson.Redisson;…...
Spring Boot 笔记 021 项目部署
1.1 引入坐标,并双击package打包成jar包 1.2 在服务器上运行jar包 1.3 使用postman测试 2.1 运行配置 2.1.1 命令更改端口 java -jar big-event-1.0-SNAPSHOT.jar --server.port7777 2.1.2 环境变量更新(略) 2.1.3 外部配置文件,…...
新技术革命开始了,Sora一出,所有的视频人、电影人都下岗
Sora一出,所有的视频人、电影人都下岗! Sora直接用文本制作长达60秒的视频长镜头,也就是说,将来,只需要输入分镜脚本,电影就可以制作出来,不再需要几十人几百人声势浩大地去“拍”了,…...
【FPGA开发】Modelsim和Vivado的使用
本篇文章包含的内容 一、FPGA工程文件结构二、Modelsim的使用三、Vivado的使用3.1 建立工程3.2 分析 RTL ANALYSIS3.2.1 .xdc约束(Constraints)文件的产生 3.3 综合 SYNTHESIS3.4 执行 IMPLEMENTATION3.5 烧录程序3.6 程序固化3.6.1 SPI约束3.6.2 .bin文…...
现代浏览器对 es模块 【esm】原生支持
现代浏览器对 ES(ECMAScript)模块的原生支持是指浏览器可以直接解析和执行 JavaScript 文件中的 ES 模块语法,无需额外的工具或转换。 具体来说,当浏览器遇到 import 和 export 关键字时,会将其识别为 ES 模块语法&…...
修改SpringBoot中默认依赖版本
例如SpringBoot2.7.2中ElasticSearch版本是7.17.4 我希望把它变成7.6.1...
网络安全最典型基础靶场-DVWA-本地搭建与初始化
写在前面: 之前也打过这个 DVWA 靶场,但是是在虚拟机环境下的一个小块分区靶场; 本篇博客主要介绍在本地搭建 DVWA 靶场以及靶场的初始化,后续会陆续更新通关教程。 由于我们是在本地搭建,则需要基于你已经装好 phpstu…...
算法-----高精度2(高精度乘法,高精度除法,高精度斐波那锲数列)
高精度乘法 对于高精度乘法来说似乎不像高精度加减法那样简单了,我们似乎得一个一个加了,因为我们都知道 abaaaaa…a(b个a)。如果真要这要的话那1e9*1e9不得超时啊,所以不能这样,我们还是得从乘法竖式入手 这样看似乎看不出来什…...
windows vs 自己编译源码 leveldb 然后使用自己编译的文件
1 准备源码文件 1.1 第一种方法 git下载源码 vs项目中git leveldb源码和git third_party googletest-CSDN博客 1.2 第二种方法 手动下载 然后把第三方的源码下载 复制到 third_party 对应的文件夹中 没有文件夹 third_party -> powershell mkdir third_party 2 编译lev…...
基于GPT一键完成数据分析全流程的AI Agent: Streamline Analyst
大型语言模型(LLM)的兴起不仅为获取知识和解决问题开辟了新的可能性,而且催生了一些新型智能系统,例如旨在辅助用户完成特定任务的AI Copilot以及旨在自动化和自主执行复杂任务的AI Agent,使得编程、创作等任务变得高效…...
C语言-----习题
1.通过这个例题,我们可以知道*p.a是无法打印99的,因为.的优先级比解引用*高; struct S {int a;int b; }; int main() {struct S a, * p &a;//可以分为两部分理解//struct S a;//struct S *p &a;a.a 99;printf("%d\n"…...
Java学习笔记(五)
目录 一、控制结构 1.1 顺序控制 1.2 分支控制 (一)单分支 (二)双分支 (三)多分支 (四)嵌套分支 (五)switch分支 1.3 循环控制 (一&…...