Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

Здравствуйте, <Аноним>, Вы писали:

А> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
Первая задача — решение линейного уравнения.
Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

Здравствуйте, Lloyd, Вы писали:

L>Здравствуйте, <Аноним>, Вы писали:

А>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

А можно кодом? Я как-то сталкивался, но уже забыл. Решение там пару строк, что-то вроде (x1-x2)*(y1-y2).

Здравствуйте, Lloyd, Вы писали:

L>Здравствуйте, <Аноним>, Вы писали:

А>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

Глянь в поиске, было и не раз.

Здравствуйте, Аноним, Вы писали:

А> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

баян

Автор: Cruser
Дата: 01.02.07

Здравствуйте, Lloyd, Вы писали:

L>Здравствуйте, <Аноним>, Вы писали:

А>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

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

Здравствуйте, twisted_mind, Вы писали:

_>Здравствуйте, Lloyd, Вы писали:

L>>Здравствуйте, <Аноним>, Вы писали:

А>>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

L>>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>>Первая задача — решение линейного уравнения.
L>>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

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

А концы отрезка нужно подставлять в уравнение какой прямой? Можно кодом, плиз.

Здравствуйте, tinytjan, Вы писали:

T>Здравствуйте, Lloyd, Вы писали:

L>>Здравствуйте, <Аноним>, Вы писали:

А>>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

L>>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>>Первая задача — решение линейного уравнения.
L>>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

T>Глянь в поиске, было и не раз.

уже два часа копаюсь. Вариантов много, но по делу ничего нет . Либо не работает вообще, либо работает так медленно, что лучше бы вообще не работало. Помню, как-то сталкивался с хорошим способом в пару строк, но его уже не помню.

А> уже два часа копаюсь. Вариантов много, но по делу ничего нет . Либо не работает вообще, либо работает так медленно, что лучше бы вообще не работало. Помню, как-то сталкивался с хорошим способом в пару строк, но его уже не помню.

а подумать?

(hint: скалярное произведение)

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, twisted_mind, Вы писали:

_>>Здравствуйте, Lloyd, Вы писали:

L>>>Здравствуйте, <Аноним>, Вы писали:

А>>>> Есть 2 отрезка, каждый из которых задается парой точек. Как определить, пересекаются ли эти отрезки?

L>>>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>>>Первая задача — решение линейного уравнения.
L>>>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

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

А> А концы отрезка нужно подставлять в уравнение какой прямой? Можно кодом, плиз.

Первый отрезок в уравнение прямой для второго, а второй — для первого.

double x1, y1, x2, y2; // первый отрезок
double x3, y3, x4, y4; // второй отрезок

double A1 = y2 - y1; 
double B1 = x1 - x2; 
double C1 = - A1 * x1 - B1 * y1; 

double A2 = y4 - y3; 
double B2 = x3 - x4; 
double C2 = -A2 * x3 - B2 * y3;

double f1 = A1 * x3 + B1 * y3 + C1; 
double f2 = A1 * x4 + B1 * y4 + C1; 
double f3 = A2 * x1 + B2 * y1 + C2; 
double f4 = A2 * x2 + B2 * y2 + C2; 

bool intersect = (f1 * f2 < 0 && f3 * f4 < 0); // строгое пересечение
или
bool intersect = (f1 * f2 <= 0 && f3 * f4 <= 0); // с учетом касания (так на самом деле нельзя, нужно сравнивать с учетом погрешности, но я так написал для ясности)

Здравствуйте, twisted_mind, Вы писали:

_>Здравствуйте, Аноним, Вы писали:

_>Первый отрезок в уравнение прямой для второго, а второй — для первого.

_>

_>double x1, y1, x2, y2; // первый отрезок
_>double x3, y3, x4, y4; // второй отрезок

_>double A1 = y2 - y1; 
_>double B1 = x1 - x2; 
_>double C1 = - A1 * x1 - B1 * y1; 

_>double A2 = y4 - y3; 
_>double B2 = x3 - x4; 
_>double C2 = -A2 * x3 - B2 * y3;

_>double f1 = A1 * x3 + B1 * y3 + C1; 
_>double f2 = A1 * x4 + B1 * y4 + C1; 
_>double f3 = A2 * x1 + B2 * y1 + C2; 
_>double f4 = A2 * x2 + B2 * y2 + C2; 

_>bool intersect = (f1 * f2 < 0 && f3 * f4 < 0); // строгое пересечение
_>или
_>bool intersect = (f1 * f2 <= 0 && f3 * f4 <= 0); // с учетом касания (так на самом деле нельзя, нужно сравнивать с учетом погрешности, но я так написал для ясности) 

_>

Алгоритм неверный . Мне нужен вариант с учетом касания, так как у большинства отрезков длинна равна 2 пикселям. А набор отрезков (84,63), (85,63) и (94,63),(95,63) выдает true, хотя это не так.

А> Алгоритм неверный . Мне нужен вариант с учетом касания, так как у большинства отрезков длинна равна 2 пикселям. А набор отрезков (84,63), (85,63) и (94,63),(95,63) выдает true, хотя это не так.

Тогда, конечно, не работает, когда все 4 точки лежат на одной прямой.
А случай, когда пересекаются не в одной точке, а по отрезку, что должен давать? Если тоже true, могу предложить такой вариант:

double sqr(double x) { return x * x; }

...

if (f1 == 0 && f2 == 0 && f3 == 0 && f4 == 0)
{
    double l1 = sqrt(sqr(x1 - x2) + sqr(y1 - y2));
    double l2 = sqrt(sqr(x3 - x4) + sqr(y3 - y4));
    return sqr((x1 + x2) - (x3 + x4)) + sqr((y1 + y2) - (y3 + y4)) < sqr(l1 + l2); 
}

Т.е. сравниваем расстояние между серединами отрезков с суммой половин их длин (только двойки сократились).

    return sqr((x1 + x2) - (x3 + x4)) + sqr((y1 + y2) - (y3 + y4)) <= sqr(l1 + l2);

Здравствуйте, twisted_mind, Вы писали:

А>> Алгоритм неверный . Мне нужен вариант с учетом касания, так как у большинства отрезков длинна равна 2 пикселям. А набор отрезков (84,63), (85,63) и (94,63),(95,63) выдает true, хотя это не так.

_>Тогда, конечно, не работает, когда все 4 точки лежат на одной прямой.
_>А случай, когда пересекаются не в одной точке, а по отрезку, что должен давать? Если тоже true, могу предложить такой вариант:

Нужно просто определить, что отрезки пересекаются, то есть у них есть хотябы одна общая точка. Нужно на вход передавать 2 отрезка (4 точки) и если у них есть хотябы одна общая точка, то возвращать true, иначе false.

А> Нужно просто определить, что отрезки пересекаются, то есть у них есть хотябы одна общая точка. Нужно на вход передавать 2 отрезка (4 точки) и если у них есть хотябы одна общая точка, то возвращать true, иначе false.

Тогда с учетом отдельной проверки для случая, когда все точки лежат на одной прямой, которую я приводил выше, должно работать.

Здравствуйте, twisted_mind, Вы писали:

А>> Нужно просто определить, что отрезки пересекаются, то есть у них есть хотябы одна общая точка. Нужно на вход передавать 2 отрезка (4 точки) и если у них есть хотябы одна общая точка, то возвращать true, иначе false.

_>Тогда с учетом отдельной проверки для случая, когда все точки лежат на одной прямой, которую я приводил выше, должно работать.

Всем спасибо. Нашел в одной книге пример, работает как часы. Выглядит он так:

public static bool IsLinePartsIntersected(Point a, Point b, Point c, Point d)
        {
            double common = (b.X - a.X)*(d.Y - c.Y) - (b.Y - a.Y)*(d.X - c.X);

            if (common == 0) return false;

            double rH = (a.Y - c.Y)*(d.X - c.X) - (a.X - c.X)*(d.Y - c.Y);
            double sH = (a.Y - c.Y)*(b.X - a.X) - (a.X - c.X)*(b.Y - a.Y);

            double r = rH / common;
            double s = sH / common;

            if (r >= 0 && r <= 1 && s >= 0 && s <= 1)
                return true;
            else
                return false;
        }

Здравствуйте, <Аноним>, Вы писали:

А> Всем спасибо. Нашел в одной книге пример, работает как часы. Выглядит он так:
А как он работает понимаешь?

Здравствуйте, SeLarin, Вы писали:

SL>Здравствуйте, <Аноним>, Вы писали:

А>> Всем спасибо. Нашел в одной книге пример, работает как часы. Выглядит он так:
SL>А как он работает понимаешь?

В книжке подробно расписан вывод этой формулы Вкурил

Здравствуйте, <Аноним>, Вы писали:

А> Всем спасибо. Нашел в одной книге пример, работает как часы. Выглядит он так:

Нет, как минимум, если оба отрезка лежат на горизонтали или вертикали и пересекаются, то ошибается...

Здравствуйте, Lloyd, Вы писали:

L>Задача сводится к нахождению точки пересечения линий, проведенных через эти точки, и находится ли точка пересечения 'внутри' отрезков.
L>Первая задача — решение линейного уравнения.
L>Вторая — проверяешь входит ли точка пересечения в прямоугольник заданный парой точек каждого отрезка.

Блин, сколько раз уже поднимался этот вопрос, и который раз я сталкиваюсь с подобным заблуждением! Ну нельзя так! Отрезки и прямые задаются параметрически. Уравнение прямой, ax+by+c=0 — это на самом деле уравнение гиперплоскости, и в данном случае его использование нецелесообразно.

И, кстати, всегда вижу решение данной задачи в виде формул для координат. На самом деле там всё сводится к частному двух псевдоскалярных произведений — учёт этого факта может дать более компактный код.