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

CGAL：创建点、线、三角形及其距离、关系

news 来源：原创 2025/7/17 0:19:08

CGAL（Computational Geometry Algorithms Library，计算几何算法库）是一个强大的开源库，为众多几何计算问题提供了高效的解决方案，在计算几何领域应用广泛。以下将基于提供的代码示例，详细介绍如何利用 CGAL 库创建点、线、三角形以及计算它们之间的距离和关系。

计算点的距离

在计算几何中，计算两点之间的距离是最基本的操作之一。以下代码示例展示了如何使用 CGAL 库中的 Exact_predicates_inexact_constructions_kernel 核来计算二维点之间的平方距离：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point_2;int main() {Point_2 p(1, 1), q(10, 10);std::cout << "距离：" << CGAL::squared_distance(p, q) << std::endl;return 0;
}

在这段代码中，首先引入了 Exact_predicates_inexact_constructions_kernel 核，该核提供了具有精确谓词和近似构造的几何对象和操作。定义了二维点类型 Point_2，然后创建了两个点 p 和 q，分别位于坐标 (1,1) 和 (10,10)。通过调用 CGAL::squared_distance 函数计算两点之间的平方距离，并将结果输出。

点、线、距离

接下来，我们进一步探讨点与线段之间的关系以及相关的距离计算。使用 Simple_cartesian 核，它可以基于双精度浮点数进行计算，效率较高，但在精度上相对一般：

#include <iostream>
#include <CGAL/Simple_cartesian.h>typedef CGAL::Simple_cartesian<double> K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;int points_and_segment() {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 << "两点之间的平方距离：" << 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 << "点 m 到线段 pq 的平方距离：" << CGAL::squared_distance(s, m) << std::endl;std::cout << "p 到 q 再到 m 三点的关系为(与先后顺序有关)： ";switch (CGAL::orientation(p, q, m)) {case CGAL::COLLINEAR:std::cout << "三点共线\n";break;case CGAL::LEFT_TURN:std::cout << "三点构成左转\n";break;case CGAL::RIGHT_TURN:std::cout << "三点构成右转\n";break;}std::cout << "p 和 q 的中点为： " << CGAL::midpoint(p, q) << std::endl;return 0;
}int main() {points_and_segment();return 0;
}

此代码中，定义了点 p 和 q，并输出它们的坐标。计算了两点之间的平方距离。然后创建了由 p 和 q 构成的线段 s，以及点 m。通过 CGAL::squared_distance 计算了点 m 到线段 s 的平方距离。使用 CGAL::orientation 函数判断点 p、q、m 三点之间的位置关系，即是否共线、构成左转还是右转。最后，利用 CGAL::midpoint 函数计算点 p 和 q 的中点坐标并输出。

计算线段交点

计算线段之间的交点是计算几何中的常见问题。以下代码展示了如何使用 Exact_predicates_exact_constructions_kernel 核来计算两条线段的交点：

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <iostream>typedef CGAL::Exact_predicates_exact_constructions_kernel K;
typedef K::Point_2 Point_2;
typedef K::Segment_2 Segment_2;int main() {Point_2 p1(0, 0), p2(2, 2), p3(0, 2), p4(2, 0);Segment_2 s1(p1, p2), s2(p3, p4);auto result = CGAL::intersection(s1, s2);if (result) {if (const Point_2* p = boost::get<Point_2>(&*result)) {std::cout << "交点: (" << p->x() << ", " << p->y() << ")\n";}} else {std::cout << "无交点。\n";}return 0;
}

在这段代码中，引入了 Exact_predicates_exact_constructions_kernel 核，它提供了精确的谓词和构造操作。定义了四个点 p1、p2、p3、p4，分别位于坐标 (0,0)、(2,2)、(0,2) 和 (2,0)。创建了两条线段 s1 和 s2，分别由 p1-p2 和 p3-p4 构成。调用 CGAL::intersection 函数计算两条线段的交点，并根据结果判断是否存在交点。如果存在交点，则输出交点的坐标。

通过 3 个顶点创建三角形

可以利用 CGAL 库轻松创建三角形。以下代码展示了如何通过三个顶点来创建一个三角形：

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Polygon_2.h>typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef K::Point_2 Point;
typedef CGAL::Polygon_2<K> Polygon_2;int main() {Point p1(0, 0);Point p2(1, 0);Point p3(0, 1);Polygon_2 triangle;triangle.push_back(p1);triangle.push_back(p2);triangle.push_back(p3);triangle.push_back(p1); // Close the polygonreturn 0;
}

此代码中，引入了 Exact_predicates_inexact_constructions_kernel 核和 Polygon_2 类。定义了三个点 p1、p2、p3，分别位于坐标 (0,0)、(1,0)、(0,1)。创建了一个 Polygon_2 对象 triangle，并依次将三个顶点添加到三角形中，最后将第一个点再次添加以闭合三角形。

判断一个二维点是否在一个二维三角形内

判断一个点是否在三角形内是一个经典的问题。以下代码展示了如何使用 CGAL 库来判断一个二维点是否在二维三角形内部、边上或外部：

#include <iostream>
#include <vector>
#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Triangle_2.h>typedef CGAL::Exact_predicates_exact_constructions_kernel Kernel;
typedef Kernel::Point_2 Point_2;
typedef CGAL::Triangle_2<Kernel> Triangle_2;int main() {Point_2 p(0, 1);Point_2 A(0, 0), B(10, 0), C(0, 10);Triangle_2 T(A, B, C);if (T.bounded_side(p) == CGAL::ON_UNBOUNDED_SIDE)std::cout << "点在三角形外部 " << std::endl;else if (T.bounded_side(p) == CGAL::ON_BOUNDARY)std::cout << "点在三角形边上 " << std::endl;else if (T.bounded_side(p) == CGAL::ON_BOUNDED_SIDE)std::cout << "点在三角形内部 " << std::endl;system("pause");return 0;
}

在这段代码中，引入了 Exact_predicates_exact_constructions_kernel 核和 Triangle_2 类。定义了点 p 和三角形的三个顶点 A、B、C，分别位于坐标 (0,1)、(0,0)、(10,0)、(0,10)。创建了一个三角形 T。通过调用三角形对象的 bounded_side 函数判断点 p 相对于三角形的位置，根据返回值确定点是在三角形外部、边上还是内部，并输出相应的结果。

通过以上示例可以看出，CGAL 库为创建和操作几何对象（如点、线、三角形）以及计算它们之间的距离和关系提供了简单而强大的接口。无论是进行基本的几何计算还是复杂的几何分析，CGAL 库都能为开发者提供便捷且高效的解决方案，大大简化了几何计算的开发过程，提高了开发效率和计算的准确性。

计算点的距离

点、线、距离

计算线段交点

通过 3 个顶点创建三角形

判断一个二维点是否在一个二维三角形内

相关文章：