То, что вы хотите, - это быстрый способ определить, пересекает ли отрезок прямой прямоугольник, выровненный по оси.Затем просто проверьте каждый сегмент линии в списке ребер по отношению к прямоугольнику.Вы можете сделать следующее:
1) Спроецировать линию на ось X, получив интервал L x .
2) Спроецировать прямоугольник на ось X,в результате получается интервал R x .
3) Если L x и R x не пересекаются, линия и прямоугольник не пересекаются.
[Повторите для оси Y]:
4) Спроецируйте линию на ось Y, получив интервал L y .
5)Проецируйте прямоугольник на ось Y, получив интервал R y .
6) Если L y и R y не пересекаются,линия и прямоугольник не пересекаются.
7) ...
8) Они пересекаются.
Обратите внимание, что если мы достигнем шага 7, фигуры не могут быть разделены линией, выровненной по оси.Теперь нужно определить, находится ли линия полностью за пределами прямоугольника.Мы можем определить это, проверив, что все угловые точки на прямоугольнике находятся на одной стороне линии.Если это так, линия и прямоугольник не пересекаются.
Идея, лежащая в основе 1-3 и 4-6, исходит из теоремы о разделительной оси ;если мы не можем найти разделяющую ось, они должны пересекаться. Все эти случаи должны быть проверены, прежде чем мы сможем заключить, что они пересекаются.
Вот соответствующий код:
#include <iostream>
#include <utility>
#include <vector>
typedef double number; // number type
struct point
{
number x;
number y;
};
point make_point(number pX, number pY)
{
point r = {pX, pY};
return r;
}
typedef std::pair<number, number> interval; // start, end
typedef std::pair<point, point> segment; // start, end
typedef std::pair<point, point> rectangle; // top-left, bottom-right
namespace classification
{
enum type
{
positive = 1,
same = 0,
negative = -1
};
}
classification::type classify_point(const point& pPoint,
const segment& pSegment)
{
// implicit line equation
number x = (pSegment.first.y - pSegment.second.y) * pPoint.x +
(pSegment.second.x - pSegment.first.x) * pPoint.y +
(pSegment.first.x * pSegment.second.y -
pSegment.second.x * pSegment.first.y);
// careful with floating point types, should use approximation
if (x == 0)
{
return classification::same;
}
else
{
return (x > 0) ? classification::positive :classification::negative;
}
}
bool number_interval(number pX, const interval& pInterval)
{
if (pInterval.first < pInterval.second)
{
return pX > pInterval.first && pX < pInterval.second;
}
else
{
return pX > pInterval.second && pX < pInterval.first;
}
}
bool inteveral_interval(const interval& pFirst, const interval& pSecond)
{
return number_interval(pFirst.first, pSecond) ||
number_interval(pFirst.second, pSecond) ||
number_interval(pSecond.first, pFirst) ||
number_interval(pSecond.second, pFirst);
}
bool segment_rectangle(const segment& pSegment, const rectangle& pRectangle)
{
// project onto x (discard y values)
interval segmentX =
std::make_pair(pSegment.first.x, pSegment.second.x);
interval rectangleX =
std::make_pair(pRectangle.first.x, pRectangle.second.x);
if (!inteveral_interval(segmentX, rectangleX))
return false;
// project onto y (discard x values)
interval segmentY =
std::make_pair(pSegment.first.y, pSegment.second.y);
interval rectangleY =
std::make_pair(pRectangle.first.y, pRectangle.second.y);
if (!inteveral_interval(segmentY, rectangleY))
return false;
// test rectangle location
point p0 = make_point(pRectangle.first.x, pRectangle.first.y);
point p1 = make_point(pRectangle.second.x, pRectangle.first.y);
point p2 = make_point(pRectangle.second.x, pRectangle.second.y);
point p3 = make_point(pRectangle.first.x, pRectangle.second.y);
classification::type c0 = classify_point(p0, pSegment);
classification::type c1 = classify_point(p1, pSegment);
classification::type c2 = classify_point(p2, pSegment);
classification::type c3 = classify_point(p3, pSegment);
// test they all classify the same
return !((c0 == c1) && (c1 == c2) && (c2 == c3));
}
int main(void)
{
rectangle r = std::make_pair(make_point(1, 1), make_point(5, 5));
segment s0 = std::make_pair(make_point(0, 3), make_point(2, -3));
segment s1 = std::make_pair(make_point(0, 0), make_point(3, 0));
segment s2 = std::make_pair(make_point(3, 0), make_point(3, 6));
segment s3 = std::make_pair(make_point(2, 3), make_point(9, 8));
std::cout << std::boolalpha;
std::cout << segment_rectangle(s0, r) << std::endl;
std::cout << segment_rectangle(s1, r) << std::endl;
std::cout << segment_rectangle(s2, r) << std::endl;
std::cout << segment_rectangle(s3, r) << std::endl;
}
Надеюсь, что имеет смысл.