做PS的赚钱的网站,在线crm客户关系管理,制作网站合同需注意,icp对网站内容ubuntu下的安装
CGAL安装
参考地址:https://doc.cgal.org/latest/Manual/usage.html
在ubuntu下安装: sudo apt-get install libcgal-dev 安装后的路径:
注意安装这个步骤安装后#xff0c;boost,CGAL,gmp,mpfr头文件都在/usr/include目录下。
boost,gmp,mpfr库文件都在/…ubuntu下的安装
CGAL安装
参考地址:https://doc.cgal.org/latest/Manual/usage.html
在ubuntu下安装: sudo apt-get install libcgal-dev 安装后的路径:
注意安装这个步骤安装后boost,CGAL,gmp,mpfr头文件都在/usr/include目录下。
boost,gmp,mpfr库文件都在/usr/lib/x86_64-linux-gnu目录下。CGAL5.0及以后版本只有头文件没有库文件 头文件路径: /usr/include/CGAL 库文件路径: /usr/lib/x86_64-linux-gnu 教程 Hello World 原文地址:https://doc.cgal.org/latest/Manual/tutorial_hello_world.html 本教程适用于了解 C 并具有几何算法基础知识的 CGAL 新手。第一部分展示如何定义点和线段类以及如何对其应用几何谓词。本节进一步提高了人们的认识即使用浮点数作为坐标时存在严重问题。在第二部分中您将遇到一个典型的 CGAL 函数它计算 2D 凸包。第三部分展示了Traits类的含义第四部分解释了概念和模型的概念。
1 三点一线
在第一个示例中我们演示了如何构造一些点和一段并对它们执行一些基本操作。
所有 CGAL 头文件都位于子目录中include/CGAL。所有 CGAL 类和函数都在命名空间中CGAL。类以大写字母开头全局函数以小写字母开头常量全部大写。物体的尺寸用后缀表示。
几何基元如点类型是在kernel中定义的。我们为第一个示例选择的内核使用double精度浮点数作为该点的笛卡尔坐标。
除了类型之外我们还看到诸如三点方向测试之类的谓词以及诸如距离和中点计算之类的*结构。*谓词具有一组离散的可能结果而构造则产生一个数字或另一个几何实体。
文件 Kernel_23/points_and_segment.cpp
#include iostream
#include CGAL/Simple_cartesian.h
typedef CGAL::Simple_cartesiandouble Kernel;
typedef Kernel::Point_2 Point_2;
typedef Kernel::Segment_2 Segment_2;
int main()
{Point_2 p(1,1), q(10,10); //构造点std::cout p p std::endl;std::cout q q.x() q.y() std::endl;//两点之间的距离std::cout sqdist(p,q) CGAL::squared_distance(p,q) std::endl;Segment_2 s(p,q); //构造直线Point_2 m(5, 9);std::cout m m std::endl;//点到直线的距离std::cout sqdist(Segment_2(p,q), m) CGAL::squared_distance(s,m) std::endl;std::cout p, q, and m ;switch (CGAL::orientation(p,q,m)){case CGAL::COLLINEAR:std::cout are collinear\n; //共线break;case CGAL::LEFT_TURN:std::cout make a left turn\n; //逆时针break;case CGAL::RIGHT_TURN:std::cout make a right turn\n; //顺时针break;}std::cout midpoint(p,q) CGAL::midpoint(p,q) std::endl;return 0;
}正如下一个示例所示用浮点数处理几何图形可能会令人惊讶。
文件 Kernel_23/surprising.cpp
#include iostream
#include CGAL/Simple_cartesian.h
typedef CGAL::Simple_cartesiandouble Kernel;
typedef Kernel::Point_2 Point_2;
int main()
{{Point_2 p(0, 0.3), q(1, 0.6), r(2, 0.9); //结果不共线std::cout (CGAL::collinear(p,q,r) ? collinear\n : not collinear\n);}{Point_2 p(0, 1.0/3.0), q(1, 2.0/3.0), r(2, 1); //结果不共线std::cout (CGAL::collinear(p,q,r) ? collinear\n : not collinear\n);}{Point_2 p(0,0), q(1, 1), r(2, 2); //结果共线std::cout (CGAL::collinear(p,q,r) ? collinear\n : not collinear\n);}return 0;
}阅读代码我们可以假设它会打印三次“共线”。然而实际输出如下
不共线
不共线
共线
这是因为这些分数不能表示为双精度数并且共线性测试将在内部计算 3x3 矩阵的行列式该行列式接近但不等于 0因此前两个测试的非共线性。
执行左转的点可能会发生类似的情况但由于行列式计算期间的舍入误差这些点似乎是共线的或者执行右转。
如果您必须确保以完全精度解释您的数字您可以使用执行精确谓词和提取结构的 CGAL 内核。
文件 Kernel_23/exact.cpp
#include iostream
#include CGAL/Exact_predicates_exact_constructions_kernel.h
#include sstream
typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
int main()
{Point_2 p(0, 0.3), q, r(2, 0.9);{q Point_2(1, 0.6); //结果不共线std::cout (CGAL::collinear(p,q,r) ? collinear\n : not collinear\n); }{std::istringstream input(0 0.3 1 0.6 2 0.9);input p q r; //结果共线std::cout (CGAL::collinear(p,q,r) ? collinear\n : not collinear\n);}{q CGAL::midpoint(p,r); //结果共线std::cout (CGAL::collinear(p,q,r) ? collinear\n : not collinear\n);}return 0;
}这是输出您可能仍然会感到惊讶。
不共线
共线
共线 在第一个块中点仍然不共线原因很简单您看到的文本坐标会变成浮点数。当它们转换为任意精度有理数时它们精确地表示浮点数但不是文本
这在第二个块中有所不同它对应于从文件中读取数字。然后直接从字符串构造任意精度有理数以便它们准确地表示文本。
在第三个块中您会看到中点构造的构造是精确的正如内核类型的名称所暗示的那样。
在许多情况下您将拥有“精确”的浮点数即它们是由某些应用程序计算或从传感器获取的。它们不是字符串“0.1”或动态计算为“1.0/10.0”而是一个全精度浮点数。如果它们被输入到不进行构造的算法则可以使用提供精确谓词但不精确构造的内核。一个这样的例子是凸包算法我们将在下一节中看到。输出是输入的子集算法仅比较坐标并执行方向测试。
乍一看执行精确谓词和构造的内核似乎是完美的选择但性能要求或有限的内存资源使其并非如此。此外对于许多算法来说进行精确的构造是无关紧要的。例如表面网格简化算法通过将边缘折叠到边缘的中点来迭代地收缩边缘。
大多数 CGAL 包都会解释它们应该使用或支持哪种内核。
2 点序列的凸包
本节中的所有示例都计算一组点的 2D 凸包。我们展示了算法将其输入作为表示一系列点的开始/结束迭代器对并将结果在示例中为凸包上的点写入输出迭代器。
2.1 内置数组中的点的凸包
在第一个示例中我们有一个由五个点组成的数组作为输入。由于这些点的凸包是输入的子集因此提供一个用于存储具有相同大小的结果的数组是安全的。
文件 Convex_hull_2/array_convex_hull_2.cpp
#include iostream
#include CGAL/Exact_predicates_inexact_constructions_kernel.h
#include CGAL/convex_hull_2.h
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
int main()
{Point_2 points[5] { Point_2(0,0), Point_2(10,0), Point_2(10,10), Point_2(6,5), Point_2(4,1) };Point_2 result[5];Point_2 *ptr CGAL::convex_hull_2( points, points5, result );std::cout ptr - result points on the convex hull: std::endl;for(int i 0; i ptr - result; i){std::cout result[i] std::endl;}return 0;
}我们在上一节中已经看到 CGAL 附带了多个内核。由于凸包算法仅对输入点的坐标和方向进行比较因此我们可以选择提供精确谓词但不提供精确几何构造的内核。
凸包函数采用三个参数即输入的起始指针和结束指针以及结果数组的起始指针。该函数将指针返回到结果数组中正好位于最后写入的凸包点后面因此指针差异告诉我们凸包上有多少个点。
2.2 向量中点的凸包
在第二个示例中我们将内置数组替换为std::vector标准模板库的数组。
文件 Convex_hull_2/vector_convex_hull_2.cpp
#include CGAL/Exact_predicates_inexact_constructions_kernel.h
#include CGAL/convex_hull_2.h
#include vector
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef std::vectorPoint_2 Points;
int main()
{Points points, result;points.push_back(Point_2(0,0));points.push_back(Point_2(10,0));points.push_back(Point_2(10,10));points.push_back(Point_2(6,5));points.push_back(Point_2(4,1));CGAL::convex_hull_2( points.begin(), points.end(), std::back_inserter(result) );std::cout result.size() points on the convex hull std::endl;return 0;
}我们将一些点放入向量中调用类push_back()的方法std::vector。
然后我们调用凸包函数。前两个参数points.begin()和points.end()是迭代器它们是指针的泛化它们可以取消引用和递增。凸包函数是通用的因为它将任何可以取消引用和递增的内容作为输入。
第三个参数是结果写入的位置。在前面的示例中我们提供了指向已分配内存的指针。这种指针的泛化是输出迭代器它允许递增并向取消引用的迭代器赋值。在此示例中我们从一个空向量开始该向量根据需要增长。因此我们不能简单地传递它result.begin()而是传递一个由辅助函数生成的输出迭代器std::back_inserter(result)。该输出迭代器在递增时不执行任何操作而是调用result.push_back(..)赋值。
如果您了解 STL标准模板库那么上面的内容就很有意义因为这就是 STL 将算法与容器解耦的方式。如果您不了解STL您最好先熟悉一下它的基本思想。
3 关于内核和特征类
在本节中我们将展示如何表达必须满足的要求以便类似的函数convex_hull_2()可以与任意点类型一起使用。
如果您查看该函数convex_hull_2()和其他 2D 凸包算法的手册页您会发现它们有两个版本。在我们到目前为止看到的示例中该函数采用两个用于输入点范围的迭代器和一个用于写入结果的输出迭代器。第二个版本有一个附加的模板参数Traits和一个此类型的附加参数。
templateclass InputIterator , class OutputIterator , class Traits
OutputIterator
convex_hull_2(InputIterator first,InputIterator beyond,OutputIterator result,const Traits ch_traits)典型的凸包算法使用哪些几何基元当然这取决于算法所以让我们考虑什么可能是最简单有效的算法即所谓的“Graham/Andrew Scan”。该算法首先从左到右对点进行排序然后通过从排序列表中逐个添加点来增量构建凸包。为此它至少必须了解某种点类型应该知道如何对这些点进行排序并且必须能够评估三重点的方向。
这就是模板参数的用武之地Traits。因为ch_graham_andrew()它必须提供以下嵌套类型
Traits::Point_2Traits::Less_xy_2Traits::Left_turn_2Traits::Equal_2
你可以猜到Left_turn_2负责方向测试而 则Less_xy_2用于对点进行排序。这些类型必须满足的要求已与该概念一起完整记录ConvexHullTraits_2。
这些类型被重新分组的原因很简单。另一种选择是使用相当冗长的函数模板以及更长的函数调用。
template class InputIterator, class OutputIterator, class Point_2, class Less_xy_2, class Left_turn_2, class Equal_2
OutputIterator
ch_graham_andrew( InputIterator first,InputIterator beyond,OutputIterator result);有两个明显的问题什么可以用作此模板参数的参数为什么我们有模板参数
为了回答第一个问题CGAL概念的任何Kernel模型都提供了该概念所需的内容ConvexHullTraits_2
至于第二个问题考虑一个我们想要计算投影到平面上的 3D 点的凸包的应用程序yz。使用该类Projection_traits_yz_3是对前面示例的一个小修改。
文件 Convex_hull_2/convex_hull_yz.cpp
#include iostream
#include iterator
#include CGAL/Exact_predicates_inexact_constructions_kernel.h
#include CGAL/Projection_traits_yz_3.h
#include CGAL/convex_hull_2.h
typedef CGAL::Exact_predicates_inexact_constructions_kernel K3;
typedef CGAL::Projection_traits_yz_3K3 K;
typedef K::Point_2 Point_2;
int main()
{std::istream_iterator Point_2 input_begin( std::cin );std::istream_iterator Point_2 input_end;std::ostream_iterator Point_2 output( std::cout, \n );CGAL::convex_hull_2( input_begin, input_end, output, K() );return 0;
}另一个示例是关于用户定义的点类型或来自 CGAL 之外的第三方库的点类型。将点类型与该点类型所需的谓词放在类的范围内您就可以convex_hull_2()使用这些点来运行。
最后让我们解释一下为什么将一个traits对象传递给凸包函数它将允许使用更通用的投影特征对象来存储状态例如如果投影平面由方向给出则该方向在类中是硬连线的Projection_traits_yz_3。
4 概念和模型
在上一节中我们写道CGAL概念的任何**模型都提供了该概念所需的内容。 KernelConvexHullTraits_2
概念是对类型的一组要求即它具有某些嵌套类型、某些成员函数或带有某些以该类型为基础的自由函数*。**概念的模型*是满足概念要求的类。
我们来看看下面的函数。
template typename T
T
duplicate(T t)
{return t;
}如果你想用一个类来实例化这个函数C这个类至少必须提供一个复制构造函数我们说这个类C必须是一个模型CopyConstructible。单例类不能满足此要求。
另一个例子是函数
template typename T
T std::min(const T a, const T b)
{return (ab)?a:b;
}operator(..)仅当为用作 as 的类型定义时此函数才会编译T并且我们说该类型必须是LessThanComparable的模型。
具有所需自由函数的概念的一个示例是HalfedgeListGraphCGAL 包CGAL 和 Boost Graph Library。为了成为HalfedgeListGraph类的模型G必须有全局函数halfedges(const G)等。
具有所需特征类的概念的一个示例是InputIterator。对于模型来说InputIterator类的专门化std::iterator_traits必须存在或者通用模板必须适用。
5 进一步阅读
我们还推荐 Addison-Wesley 的 Nicolai M. Josuttis 所著的标准教科书“The C Standard Library, A Tutorial and Reference”或 Matthew H. Austern 所著的“Generic Planning and the STL”介绍 STL 及其概念和概念。楷模。
CGAL 的其他资源包括教程的其余部分以及https://www.cgal.org/上的用户支持页面。
原文链接1. cgal在ubuntu下的安装及Hello World的测试_cgal ubuntu-CSDN博客
