Использование геометрии буста для проверки пересечения двух линий
Можно ли использовать boost :: geometry, чтобы проверить, пересекаются ли два отрезка (каждый задан двумя точками в 2D)? Если это возможно, позволяет ли boost :: geometry проверять также особые случаи, например, что только одна точка (численно) находится на другой линии или обе линии равны?
Решение
Если вы говорите конкретно об API Boost.Geometry, то это, конечно, возможно.
Ваш код должен выглядеть примерно так
#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);
Другие решения
Вы спрашиваете, пересекаются ли две линии. Две линии всегда будут пересекаться, если они не параллельны.
Следующий алгоритм помогает вам вычислить, пересекает ли отрезок линию. Он работает следующим образом: имея координаты 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).
Я изучил этот алгоритм в разделе «Алгоритм Сарруса», поэтому, возможно, поиск в Google мог бы дать лучшее объяснение.
Вы можете попробовать использовать алгоритм пересечения. Если линии пересекаются,
вывод будет не пустым.
пример для начинающих без использования 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);
detector