6

Is it possible to use boost::geometry to check whether two line segments (each given by two points in 2D) intersect each other? If this is possible, does boost::geometry allow to check also for special cases such as that only one point is (numerically) on the other line, or that both lines are equal?

4

4 回答 4

12

如果您专门谈论 Boost.Geometry API，当然是可能的。

您的代码应大致如下所示

#include <boost/geometry/geometries/segment.hpp> 
#include <boost/geometry/algorithms/intersection.hpp>

typedef boost::geometry::model::segment<Point> Segment;
Segment AB( Point(x1,y1), Point(x2,y2) );
Segment CD; //similar code

bool result = boost::geometry::intersects(AB, CD);

如果您需要交点：

std::vector<Point> output; 
boost::geometry::intersection(AB, CD, output);

现在输出将有 0、1 或 2 个点，具体取决于位置。

当然，您的 Point 类型应该与 Boost.Geometry 概念“兼容”。以下代码将使 QPointF 兼容：

#include <boost/geometry/geometries/register/point.hpp>
BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(QPointF, qreal, cs::cartesian, x, y, setX, setY);
于 2013-11-08T22:11:47.710 回答
1

你问两条线是否相交。两条线将永远相交，除非它们平行。

以下算法可帮助您计算线段是否与线相交。它的工作原理如下：通过 3 个点的坐标计算行列式

x1 y1 1
x2 y2 1
x3 y3 1

其中 (x1;y1) 和 (x2;y2) 是代表您的线的点， (x3; y3) 代表您的第三点（您的线段的极端之一）。如果行列式为正，则 (x3; y3) 从 (x1;y1) 到 (x2;y2) 的向量向右，如果为负，则向右。如果行列式为 0，则该点在线上。

您需要做的是对该段的一个极端应用该算法两次，然后对另一个极端应用一次，如果行列式的乘积为负，则相交，否则不相交。

您可以进一步计算两个线段是否相交。您所要做的就是两次应用相同的想法，只是第二次您的 (x1;y1) 和 (x2;y2) 将是您用于 (x3;y3) 和新 (x3;y3) 的值旧的 (x1;y1) 和 (x2;y2)。

我在“Sarrus 算法”下学习了这个算法，所以谷歌搜索它可能会给出更好的解释。

于 2013-11-08T19:55:58.130 回答
1

不使用 BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET 的初学者示例

namespace bg = boost::geometry;

typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
typedef bg::model::segment<point_t> segment_t;

segment_t seg1(point_t(0.0, 0.0), point_t(5.0, 5.0));
segment_t seg2(point_t(10.0, 5.0), point_t(5.0, 0.0));

bool result = boost::geometry::intersects(seg1, seg2);
于 2017-01-06T19:50:12.287 回答
0

您可以尝试使用交集算法。如果线相交，则输出将为非空。

于 2013-11-08T19:45:10.223 回答