Как стать автором
Обновить

Комментарии 8

НЛО прилетело и опубликовало эту надпись здесь

Предупреждаю, данный метод не учитывает некоторые пограничные случаи

Какие?

и вхождение отрезков друг в друга.

Почему?

И почему часть комментариев на русском, а часть на английском?

Задача о нахождении отрезков не такая простая как кажется на первый взгляд, легко пропустить какой-то крайний случай, так что советую покрыть ваше решение тестами. К оформлению решения есть ряд замечаний. Код оформлен небрежно, в одном месте есть пробел перед = в другом нет, пробелы иногда перед запятой а не после (!) - надо бы использовать какой-то линтер. Названия методов crs и scl слишком короткие. Вместо названия fromDifferentSides по смыслу больше подходит atDifferentSides. Последнюю простыню кода можно убрать под спойлер. По окончанию статьи так и не понятно какой мне метод брать, ваш или какой-то из двух других по ссылкам, или в комментариях по ссылкам? :) В любом случае на фоне засилия гугло-переводов на хабре, всегда приятно видеть когда человек пытается разобраться сам.

Кмк, на фоне качества выбранного алгоритма недостатки оформления теряются, как муха на фоне слона.

Ведь есть же гораздо более простой и эффективный метод: точка пересечения одновременно удовлетворяет уравнениям двух прямых

Line1: C + alfa1*(D-C)

Line2: A + alfa2*(B-A)

alfa1*(D.x-C.x) - alfa2*(B.x-A.x) = A.x-C.x

alfa1*(D.y-C.y) - alfa2*(B.y-A.y) = A.y-C.y

И все, что требуется для нахождения пересечения двух отрезков- это убедиться, что эта система имеет решение и хотя-бы одно из этих решений удовлетворяет условия alfa1, alfa2 in [0.0 .. 1.0 ]

Решение единственное, если (D.x-C.x)*(B.y-A.y)-(D.y-C.y)*(B.x-A.x) <> 0. надо проверить, что alfa1,alfa2 удовлетворяют требованиям 0.0<=a<=1.0.

Отрезки коллинеарные, если Det = (D.x-C.x)*(B.y-A.y)-(D.y-C.y)*(B.x-A.x) = 0, надо проверить, что один отрезок лежит целиком левее или целиком правее другого. если да- то пересечения нет, если нет- то отрезки перекрываются и пересечений много.

Такое решение реализуется в виде простой функции, не требует создания кучи объектов, не грузит гарбажколлектор, и укладывается в 20 строк кода. А тут - куски решения раскиданы по пяти методам, каждый из которых делает непойми что и непойми зачем, а на выходе еще и "пограничные случаи". (Пограничные случаи- это когда Abs(Det) < eps=1,0e-12*(L2_norm(A-B)+L2_norm(C-D)) - но пересечение отрезков на float-числах- при малых eps- это несколько лотерея или тема отдельной большой статьи).

Раз уж скриншоты из GeoGebra, а она open source, не стоит ли для начала заглянуть «под капот» оной и посмотреть на имеющееся решение?

Думаю, это пригодится разработчикам игр.

Исходя из того, что


Предупреждаю, данный метод не учитывает некоторые пограничные случаи и вхождение отрезков друг в друга.

Крайне сомневаюсь в том что это будет иметь практическую ценность.
Ведь именно корректная обработка пограничных случаев и представляет основной интерес.

Приятно видеть попытки разобраться в линейной алгебре на плоскости, это поможет не только в разработке игр, но и при создании разметки изображений.

А теперь расскажу о простом для понимания, но несколько дорогом для cpu (задействуется извлечение корня) алгоритме о пересечении отрезков. Поехали.

Первым делом зададим точки A, B, C, D на двумерной плоскости, А и В задают первый отрезок, C и D - второй.

Основная идея - привести систему к вырожденному случаю, когда точка А' имеет координаты (0, 0), а точка В' лежит на оси ОХ.

Первым делом вычтем из точек В, С и D точку А, так мы достигнем первого условия. Теперь нужно повернуть точки С и D вокруг точки А (точку В поворачивать не нужно, её координаты будут (length(A, B), 0)). Для этого воспользуемся матрицей поворота, для неё нужны синус и косинус угла линии AB, благо их легко вычислить, зная длину AB и расстояние по оси ОХ и ОY между точками А и В.

После умножения точек С и D на матрицу поворота мы получим С' и D' в локальных координатах отрезка АВ.

Задача о пересечении становится тривиальной:

  1. Точки С' и D' с разных сторон оси ОХ, или одна из точек близка к отрезку А'В' на некоторую эпсилон.

Теперь когда точки С' и D' с разных сторон оси ОХ мы можем найти точку пересечения С'D' и ОХ:

  1. Найдем расстояние по ОХ между С' и D' (cdLy)

  2. Найдём параметр alpha, поделив координату Y точки С' на расстояние по OY точек С' и D'.

  3. Найдём координату X точки М' (пересечение), помножив cdLy на alpha. Координата X должна оказаться больше или равна 0 и меньше или равна длине АВ, в противном случае отрезки не пересекаются.

  4. Вернём точку М' в мировое пространство, помножив её на инверсную матрицу поворота (в данном случае нужно всего лишь поменять знаки). По факту здесь можно умножить кординату X точки М' на синус и косинус угла линии АВ.

  5. После этого к точке М нужно прибавить координаты точки А.

Весьма долгий путь, зато общий. Так можно найти расстояние от отрезка до точки (а заодно самую ближайшую точку на отрезке к заданной точке), то же можно провернуть с лучом или линией, приведя их к форме отрезка и убрав проверки на ось ОY и/или длину АВ.

Подобный подход можно использовать для пересечения отрезка и треугольника в трёхмерном пространстве. В таком случае пусть треугольник будет АВС, а отрезок DE. Аналогично нужно из точек B, C, D и Е отнять точку А и помножить на матрицу треугольника АВС (тангент - сторона АВ, нормаль - векторное произведение АВ и АС, битангент - тангент х нормаль, получится матрица TBN. Все вектора T, B, N нужно нормализовать). После этого задача опять тривиальна: точка А' лежит в начале координат, точка В' на оси ОХ, а точка С' выше оси ОХ. Найти точку пересечения в этом случае тривиально, описывать не стану.

Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории