Объяснение алгоритма ccw
У меня возникли проблемы с пониманием алгоритма ccw (против часовой стрелки):
int ccw (Point P0, Point P1, Point P2) {
dx1 = P1.x - P0.x;
dx2 = P2.x - P0.x;
dy1 = P1.y - P0.y;
dy2 = P1.y - P0.y;
if (dy1 * dx2 > dy2 * dx1) return -1;
if (dx1 * dy2 > dy1 * dx2) return 1;
if ((dx1 * dx2 < 0) || (dy1 * dy2 < 0)) return 1;
if ((dx1 * dx1 + dy1 * dy1) < (dx2 * dx2 + dy2 * dy2)) return -1;
return 0;
}
Этот код он использовал, чтобы увидеть, пересекаются ли две линии:
bool intersect (Vector2D l1, Vector2D l2) {
return (((ccw(l1.start, l1.end, l2.start) * ccw(l1.start, l1.end, l2.end)) <= 0)
&& ((ccw(l2.start, l2.end, l1.start) * ccw(l2.start, l2.end, l1.start)) <= 0))
}
Я могу понять код внутри функции пересечения, но я не совсем понимаю код внутри функции ccw.
Почему не используется перекрестный продукт?
Решение
Код внутри ccw Функция написана довольно произвольно, но она использует то, что иногда очень неофициально называют 2D-версией перекрестное произведение. Для двух векторов (dx1, dy1) а также (dx2, dy2) этот продукт определяется как скалярное значение, равное
CP = dx1 * dy2 - dx2 * dy1;
(В формально правильной терминологии CP на самом деле знаковая величина классического трехмерного перекрестного произведения векторов (dx1, dy1, 0) а также (dx2, dy2, 0).) Очевидно, что это значение просто скаляр (точка) произведение, в котором один из векторов был заменен его перпендикулярным.
Если значение CP положительный, то кратчайший радиальный размах от (dx1, dy1) в (dx2, dy2) идет против часовой стрелки. отрицательный CP означает поворот по часовой стрелке. Ноль в CP указывает коллинеарные векторы. (Все это предполагает, что ось Y направлена вверх, а ось X направлена вправо.)
Очевидно, что CP > 0 условие эквивалентно dx1 * dy2 > dx2 * dy1 состояние и CP < 0 эквивалентно dx1 * dy2 < dx2 * dy1, Это именно то, что ваш ccw проверка функций по первым двум ifs.
Остальные ifМы имеем дело с коллинеарными ситуациями.
Если векторы указывают в противоположных направлениях (что определяется третьим if), то есть когда P0 лежит между P1 а также P2функция всегда возвращает 1, указывая против часовой стрелки. Ну, я думаю, это просто соглашение, принятое автором кода.
Наконец, если два вектора указывают в одном и том же направлении, то есть когда P0 лежит вне P1-P2 сегмент, решение основывается на длинах векторов (четвертый if). Если P1 ближе чем P2 в P0, заказ по часовой стрелке сообщается. В противном случае, если P2 ближе, против часовой стрелки сообщается. Это также просто соглашение, принятое автором кода.
И, судя по остальной части кода, речь идет не о пересечении двух линии. Речь идет о пересечении двух сегменты.
Другие решения