使用boost几何库检查两条直线是否相交。

Question

使用boost几何库检查两条直线是否相交。

c++boostgeometrynumerical-methodsboost-geometry

6

是否可以使用boost::geometry来检查两个线段（每个线段由2D中的两个点给出）是否相交？如果可能，boost::geometry是否允许检查特殊情况，例如仅有一个点（数值上）在另一条线上，或者两条线段相等？

- Thomas W.

只是为了让我的问题更加精确：我指的是两条线段。 - Thomas W.

4个回答

2

这是一个适用于初学者的示例，不使用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);

- user1277317

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 算法”学习这个算法的，因此可能在谷歌搜索中会得到更好的解释。

- Alexandru Barbarosie

我考虑了一下，发现它并不适用于所有的边角情况。只需考虑第一条线段[0,0]->[1,1]和第二条线段[2,2]->[3,3]。显然，这两条线段不相交，但是两个行列式的值都为零，因为这两条线段都属于同一条（无限长的）直线。 - Thomas W.

你可以轻松检查这个特定的情况 - 你可以从两个点计算出直线函数，比较斜率和系数，然后检查它们是否不重叠。 - Alexandru Barbarosie

0

你可以尝试使用交点算法。如果这些线相交，输出将不为空。

- anjruu

有趣，但它是否高效？我只是想知道这两条线是否相交，不需要得到相交的几何形状。更重要的是，这些函数的数值稳定性如何？如果一个点包含在另一条线的 epsilon 环境中，它会如何表现？ - Thomas W.

等一下，你是在2D空间中。答案是“是的，除非这些线是平行的”。 - anjruu

@anjruu 我认为他的意思是两条线段。 - user180326

哦，那就算了。我不清楚boost::geometry::intersection的数值稳定性。 - anjruu

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael Simbirsky · Accepted Answer

如果您特别讨论的是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);