Как проверить пересечение двух отрезков через ориентации, аккуратно с коллинеарными случаями?
Нужно для двух отрезков AB и CD ответить true/false, пересекаются ли они (включая касание концами и наложение). Пишу через orient, но всё время ловлю баги на коллинеарных случаях, когда отрезки лежат на одной прямой. Как сделать правильно и в целых числах?
2 ответа
Стандартный приём — четыре ориентации плюс отдельная обработка коллинеарности. Основной случай: отрезки пересекаются, если C и D лежат по разные стороны от прямой AB, и одновременно A и B — по разные стороны от CD.
int orient(const P& a, const P& b, const P& c); // 1/-1/0
bool onSeg(const P& a, const P& b, const P& p) { // p на отрезке ab (уже коллинеарна)
return min(a.x,b.x) <= p.x && p.x <= max(a.x,b.x) &&
min(a.y,b.y) <= p.y && p.y <= max(a.y,b.y);
}
bool segInter(const P& a, const P& b, const P& c, const P& d) {
int o1 = orient(a,b,c), o2 = orient(a,b,d);
int o3 = orient(c,d,a), o4 = orient(c,d,b);
if (o1 != o2 && o3 != o4) return true; // общий случай
if (o1 == 0 && onSeg(a,b,c)) return true; // коллинеарные касания/наложения
if (o2 == 0 && onSeg(a,b,d)) return true;
if (o3 == 0 && onSeg(c,d,a)) return true;
if (o4 == 0 && onSeg(c,d,b)) return true;
return false;
}
Идея коллинеарных веток: если ориентация нулевая, точка лежит на прямой, и остаётся проверить, попадает ли она в bounding-box отрезка (onSeg). Это покрывает и касание концом, и частичное наложение. Всё в целых числах, без epsilon. Сложность O(1).
Самая частая ошибка — забыть, что o1 != o2 && o3 != o4 корректно работает только когда ни одна ориентация не нулевая. Если, скажем, o1 == 0 (C на прямой AB), то условие o1 != o2 может случайно выполниться или нет — поэтому коллинеарные случаи обязательно выносятся в отдельные if через onSeg, как в коде выше.
Если по условию касание концами НЕ считается пересечением (строгое пересечение), убери все ветки с onSeg и используй только строгий случай o1!=o2 && o3!=o4 — но тогда отрезки на одной прямой никогда не дадут true, что обычно и требуется в «строгой» постановке. Всегда уточняй по условию, считается ли касание.