Пушыстый (_winnie) wrote,
Пушыстый
_winnie

Categories:

Геометрические Алгоритмы. Пересечение двух отрезков на плоскости.

Пусть есть два отрезка A,B и C,D. Надо понять, пересекаются ли они, и если да, то где именно. Во всех исходниках и книжках, которые я смотрел, это было сделано с кучей ненужного мусора, не смотря на то, что вроде бы очень простая и распространённая задача. Обычно как делают:
Параметризуют первый отрезок как A + (B-A)*u, u <= [0, 1], второй как C + (D-C)*v, v <= [0, 1]

Получается уравнение

A + (B-A)*u = C + (D-C)*v

Если переписать покомпонентно

Ax + (Bx-Ax)*u = Cx + (Dx-Cx)*v
Ay + (By-Ay)*u = Cy + (Dy-Cy)*v

То есть обычное уравнение из двух неизвестных.

Считают обычно по правилу крамера, потом смотрят, лежат ли корни в пределах от 0 до 1. Если определитель равен нулю, то считают что отрезки параллельны и не пересекаются.
Примечание: Или лежат на одной прямой, в этом случае лучше считать что не пересекаются. Так как любое дрожание начальных параметров приведёт к изменению решения, а дрожание такое есть всегда из-за неточности float, и часто бессмыслено выделять особый случай, который если и получится, то только если случайно float округлится до нужных значений. Если нам надо от алгоритма надо bool-значение "(Не)пересекаются", а не три энума "пересекаются в точке", "пересекаются по прямой", "не пересекаются", то проще считать второй случай сразу третьим.

Иногда сравнивают определитель сразу с 0, иногда пытаются ввести взятое с потолка EPSILON. Получается много if, взятое с потолка EPSILON (0.001 ? 0.0001 ?), непонятная работа если мы всё-таки начинаем делить большие числа на число чуть больше EPSILON, неправильная работа если не только числитель, но и знаменатель дроби меньше EPSILON.

Тут нужно не "разделять и властвовать", решая подзадачи (Ага, линейное уравнение. 1) решим 2) Ага, надо проверить что результат от 0 до 1), а решать задачу целиком.


Если у нас есть отрезок P + Q*t, то тогда нормаль к прямой проходящей через этот отрезок это perp(Q) = (-Qy, +Qx), а её уравнение это ((-Qy*x + Qx*y) - (-Qy*Px + Qx*Py) = 0). Переобозначив -Qy как A, и тп, получим привычное уравнение прямой (A*x + B*y + D == 0) Это же уравнение записанное как неравенство даст уравнение полуплоскости. Если подставить какую-то точку (x,y) в выражение A*x + B*y + С, то если оно получилось положительным - значит точка с одной стороны прямой, а если отрицательным - то с другой. Если ноль - значит, ровно на прямой. Степень отклонения от нуля этого выражения - это то, насколько точка далеко от прямой (это длина проекции отклонения на нормаль к прямой). Если оно почти ноль - значит, точка почти на прямой. Если выражение в два раза больше - значит точка в два раза дальше от прямой.



Мы не будем решать уравнение, а затем смотреть, лежат ли корни u и v там где нам надо, в промежутке 0-1. Определим сразу есть ли пересечение, сначала записав уравнение обоих отрезков, а затем посмотрев в каких полуплоскостях лежат концы отрезков. Если оба отрезка пересекают прямую своего отрезка-напарника (то есть концы лежат в разных полуплоскостях этой прямой), значит пересечение есть. Если концы какого-то отрезка лежат в одной полуплоскости - значит пересечения нет. Так как это выражение A*x + B*y + D характеризует насколько точка удалена от плоскости, то значит для двух концов отрезка два значения показывают на какие части делится отрезок пересечением. А это нам сразу даёт чему равно u или v в точке пересечения - u делит отрезок [0, 1] точно так же как точка пересечения делит отрезок AB, который задаётся как A + (B-A)*u.


Код:

    bool intersection(Point2f start1, Point2f end1, Point2f start2, Point2f end2, Point2f *out_intersection)
    {
        Point2f dir1 = end1 - start1;
        Point2f dir2 = end2 - start2;

        //считаем уравнения прямых проходящих через отрезки
        float a1 = -dir1.y;
        float b1 = +dir1.x;
        float d1 = -(a1*start1.x + b1*start1.y);

        float a2 = -dir2.y;
        float b2 = +dir2.x;
        float d2 = -(a2*start2.x + b2*start2.y);

        //подставляем концы отрезков, для выяснения в каких полуплоскотях они
        float seg1_line2_start = a2*start1.x + b2*start1.y + d2;
        float seg1_line2_end = a2*end1.x + b2*end1.y + d2;

        float seg2_line1_start = a1*start2.x + b1*start2.y + d1;
        float seg2_line1_end = a1*end2.x + b1*end2.y + d1;

        //если концы одного отрезка имеют один знак, значит он в одной полуплоскости и пересечения нет.
        if (seg1_line2_start * seg1_line2_end >= 0 || seg2_line1_start * seg2_line1_end >= 0) 
            return false;

        float u = seg1_line2_start / (seg1_line2_start - seg1_line2_end);
        *out_intersection =  start1 + u*dir1;

        return true;
    }
_Winnie C++ Colorizer



Итак, мы тут не делим, если не надо делить. И поэтому не делим на ноль. Нет никаких дурацких эпсилонов.
В следующий раз - отрезок и окружность, квадратное уравнение. В следующий раз мы не будем считать дискриминант и два корня, если этого не надо.


Смотри ещё: • Угол между двумя векторами
Смотри ещё: • Проверка точки внутри многоугольника
Tags: geom-prog, math, release, soft-dev
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 42 comments
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →
Previous
← Ctrl ← Alt
Next
Ctrl → Alt →