Using boost geometry to check if two lines have an intersection

Question

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?

Answer 1

If you are talking specifically about Boost.Geometry API to it is, of course, possible.

Your code should look roughly like this

#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);

If you need intersection points:

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

Now output will have 0, 1 or 2 points, depending on locations.

Of course, your Point type should be "compliant" with Boost.Geometry concepts. The following code will make QPointF compliant:

#include <boost/geometry/geometries/register/point.hpp>
BOOST_GEOMETRY_REGISTER_POINT_2D_GET_SET(QPointF, qreal, cs::cartesian, x, y, setX, setY);

Answer 2

You ask whether two lines intersect. Two lines will always intersect unless they are parallel.

The following algoritm helps you compute if a segment intersects a line. It works as follows: having the coordinates of 3 points you compute the determinant of

x1 y1 1
x2 y2 1
x3 y3 1

Where (x1;y1) and (x2;y2) are the point representing your line and (x3; y3) represent your 3rd point (one of the extremes of your segment). If determinant is positive then (x3; y3) is to the right from the vector oriented from (x1;y1) to (x2;y2), if it is negative it is to the right. And if the determinant is 0 then the point is on the line.

What you have to do is to apply this algorithm twice once for one extreme of the segment and once for the other, if the product of determinants is negative, it intersects, if not, it doesn't.

You can go further and compute if two segments intersect. All you have to do is apply the same idea twice, only that the second time your (x1;y1) and (x2;y2) will be the values you used for (x3;y3) and your new (x3;y3) your old (x1;y1) and (x2;y2).

I learned this algorithm under "Sarrus algorithm" so maybe googling it might give a better explanation.