Добавлен Msey,
опубликован
Даны два отрезка AB и CD (они могут вырождаться в точки). Требуется найти их пересечение: оно может быть пустым (если отрезки не пересекаются), может быть одной точкой, и может быть целым отрезком (если отрезки накладываются друг на друга).
Алгоритм
Работать с отрезками будем как с прямыми: построим по двум отрезкам уравнения их прямых, проверим, не параллельны ли прямые. Если прямые не параллельны, то всё просто: находим их точку пересечения и проверяем, что она принадлежит обоим отрезкам (для этого достаточно проверить, что точка принадлежит каждому отрезку в проекции на ось X и на ось Y по отдельности). В итоге в этом случае ответом будет либо "пусто", либо единственная найденная точка.
Более сложный случай — если прямые оказались параллельными (сюда же относится случай, когда один или оба отрезка выродились в точки). В этом случае надо проверить, что оба отрезка лежат на одной прямой (или, в случае когда они оба вырождены в точку — что эта точка совпадает). Если это не так, то ответ — "пусто". Если это так, то ответ — это пересечение двух отрезков, лежащих на одной прямой, что реализуется достаточно просто — надо взять максимум из левых концов и минимум из правых концов.
В самом начале алгоритма напишем так называемую "проверку на bounding box" — во-первых, она необходима для случая, когда два отрезка лежат на одной прямой, а во-вторых, она, как легковесная проверка, позволяет алгоритму работать в среднем быстрее на случайных тестах.
Реализация
Приведём здесь полную реализацию, включая все вспомогательные функции по работе с точками и прямыми.
Главной здесь является функция intersect, которая пересекает два переданных ей отрезка, и если они пересекаются хотя бы по одной точке, то возвращает true, а в аргументах left и right возвращает начало и конец отрезка-ответа (в частности, когда ответ — это единственная точка, возвращаемые начало и конец будут совпадать).
const double EPS = 1E-9;
struct pt {
double x, y;
bool operator< (const pt & p) const {
return x < p.x-EPS || abs(x-p.x) < EPS && y < p.y - EPS;
}
};
struct line {
double a, b, c;
line() {}
line (pt p, pt q) {
a = p.y - q.y;
b = q.x - p.x;
c = - a * p.x - b * p.y;
norm();
}
void norm() {
double z = sqrt (a*a + b*b);
if (abs(z) > EPS)
a /= z, b /= z, c /= z;
}
double dist (pt p) const {
return a * p.x + b * p.y + c;
}
};
#define det(a,b,c,d) (a*d-b*c)
inline bool betw (double l, double r, double x) {
return min(l,r) <= x + EPS && x <= max(l,r) + EPS;
}
inline bool intersect_1d (double a, double b, double c, double d) {
if (a > b) swap (a, b);
if (c > d) swap (c, d);
return max (a, c) <= min (b, d) + EPS;
}
bool intersect (pt a, pt b, pt c, pt d, pt & left, pt & right) {
if (! intersect_1d (a.x, b.x, c.x, d.x) || ! intersect_1d (a.y, b.y, c.y, d.y))
return false;
line m (a, b);
line n (c, d);
double zn = det (m.a, m.b, n.a, n.b);
if (abs (zn) < EPS) {
if (abs (m.dist (c)) > EPS || abs (n.dist (a)) > EPS)
return false;
if (b < a) swap (a, b);
if (d < c) swap (c, d);
left = max (a, c);
right = min (b, d);
return true;
}
else {
left.x = right.x = - det (m.c, m.b, n.c, n.b) / zn;
left.y = right.y = - det (m.a, m.c, n.a, n.c) / zn;
return betw (a.x, b.x, left.x)
&& betw (a.y, b.y, left.y)
&& betw (c.x, d.x, left.x)
&& betw (c.y, d.y, left.y);
}
}
`
ОЖИДАНИЕ РЕКЛАМЫ...
0
Ev3nt
3 года назад
0
Очень интересно и полезно, заслуженный лайк, хоть щас игру на основе отбрасывания лучшей пили, только какова скорость вычисления, а то я хотел кое-что замутить)
0
Msey
3 года назад
0
Ev3nt, там асимптотика линейная, так как считаем максимальный и минимальный элементы. А все остальное сворачивается в константы
0
ScorpioT1000
3 года назад
0
щас бы на c++ наполовину в процедурном стиле со структурами писать, наполовину юзать их как классы
0
Msey
3 года назад
0
ScorpioT1000, это не мое. Там реализация довольно старая, но переписывать это все как-то влом
Чтобы оставить комментарий, пожалуйста, войдите на сайт.