Как определить, пересекаются ли две линии, и если они это делают, в какой точке x, y?
geometry
line-intersection
KingNestor
источник
источник
Ответы:
Есть хороший подход к этой проблеме, который использует векторные перекрестные произведения. Определите двумерное векторное перекрестное произведение v × w как v x w y - v y w x .
Предположим, что два отрезка проходят от p до p + r и от q до q + s . Тогда любая точка на первой строке представляется как p + t r (для скалярного параметра t ), а любая точка на второй строке - как q + u s (для скалярного параметра u ).
Две линии пересекаются, если мы можем найти t и u такие, что:
Скрестить обе стороны с S , получая
И так как s × s = 0, это означает
И, следовательно, решение для т :
Таким же образом, мы можем решить для U :
Чтобы уменьшить количество шагов вычисления, удобно переписать это следующим образом (помня, что s × r = - r × s ):
Сейчас есть четыре случая:
Если r × s = 0 и ( q - p ) × r = 0, то эти две линии коллинеарны.
В этом случае выразите конечные точки второго сегмента ( q и q + s ) через уравнение первого сегмента линии ( p + t r ):
Если интервал между t 0 и t 1 пересекает интервал [0, 1], то отрезки линии коллинеарны и перекрываются; в противном случае они коллинеарны и не пересекаются.
Обратите внимание, что если s и r указывают в противоположных направлениях, то s · r <0, и поэтому проверяемый интервал равен [ t 1 , t 0 ], а не [ t 0 , t 1 ].
Если r × s = 0 и ( q - p ) × r ≠ 0, то две прямые параллельны и не пересекаются.
Если r × s ≠ 0 и 0 ≤ t ≤ 1 и 0 ≤ u ≤ 1, два отрезка линии встречаются в точке p + t r = q + u s .
В противном случае два отрезка не параллельны, но не пересекаются.
Кредит: этот метод является двухмерной специализацией алгоритма пересечения трехмерных линий из статьи Рональда Голдмана «Пересечение двух линий в трехмерном пространстве», опубликованной в Graphics Gems , стр. 304. В трех измерениях обычный случай состоит в том, что линии наклонены (не параллельны и не пересекаются), и в этом случае метод дает точки ближайшего сближения двух линий.
источник
/ (r × s)
, но(r × s)
есть ли вектор, верно? Вектор(0, 0, rx * sy - ry * sx)
. А левая сторона аналогично вектору, параллельному оси z. Итак ... я просто делю компонент z на другой компонент z? Формула для т на самом деле|(q − p) × s| / |(r × s)|
?FWIW, следующая функция (в C) обнаруживает пересечения линий и определяет точку пересечения. Он основан на алгоритме Андре ЛеМота " Уловки гуру программирования игр для Windows ". Это не отличается от некоторых алгоритмов в других ответах (например, Гарет). Затем ЛеМот использует правило Крамера (не спрашивайте меня), чтобы решить сами уравнения.
Я могу засвидетельствовать, что это работает в моем слабом клоне астероидов, и, кажется, правильно справляется с крайними случаями, описанными в других ответах Elemental, Dan и Wodzu. Это также, вероятно, быстрее, чем код, опубликованный KingNestor, потому что это все умножение и деление, без квадратных корней!
Я предполагаю, что есть некоторый потенциал для деления на ноль, хотя в моем случае это не было проблемой. Достаточно легко изменить, чтобы избежать аварии в любом случае.
Кстати, я должен сказать, что в книге Лемота, хотя он, по-видимому, правильно понимает алгоритм, в конкретном примере он показывает неверные числа и делает неправильные вычисления. Например:
Это смущало меня часами . :(
источник
s
и вычисленияt
, проверьте взаимосвязь между двумя числителями и знаменателем. Только если линии подтверждены для пересечения, вам действительно нужно вычислить значениеt
(но неs
).Проблема сводится к этому вопросу: пересекаются ли две линии от A до B и от C до D? Затем вы можете задать это четыре раза (между линией и каждой из четырех сторон прямоугольника).
Вот векторная математика для этого. Я предполагаю, что линия от A до B является рассматриваемой линией, а линия от C до D является одной из прямоугольных линий. Моя запись такова, что
Ax
это «x-координата A» иCy
«y-координата C.» И «*
» означает точку-продукт, так напримерA*B = Ax*Bx + Ay*By
.Этот
h
номер является ключом. Еслиh
между0
и1
, линии пересекаются, в противном случае они не пересекаются. ЕслиF*P
ноль, конечно, вы не можете сделать расчет, но в этом случае линии параллельны и поэтому пересекаются только в очевидных случаях.Точная точка пересечения
C + F*h
.Смешнее:
Если
h
это точно0
или1
линии касаются в конечной точке. Вы можете считать это «пересечением» или нет, как считаете нужным.В частности,
h
сколько вам нужно умножить длину линии, чтобы точно коснуться другой линии.Следовательно, если
h<0
, это означает, что линия прямоугольника находится «позади» данной линии (с «направлением», являющимся «от А до В»), и еслиh>1
прямоугольная линия находится «перед» данной линией.Вывод:
A и C - векторы, указывающие на начало линии; E и F - векторы от концов A и C, которые образуют линию.
Для любых двух непараллельных линий на плоскости должна быть ровно одна пара скаляров
g
иh
такая, чтобы это уравнение выполнялось:Почему? Поскольку две непараллельные линии должны пересекаться, это означает, что вы можете масштабировать обе линии на некоторое количество и касаться друг друга.
( Сначала это выглядит как одно уравнение с двумя неизвестными! Но это не так, если учесть, что это двумерное векторное уравнение, что означает, что это действительно пара уравнений в
x
иy
.)Мы должны устранить одну из этих переменных. Самый простой способ -
E
обнулить термин. Чтобы сделать это, возьмем скалярное произведение обеих сторон уравнения, используя вектор, который укажет на ноль точку E. Этот вектор я назвалP
выше, и я сделал очевидное преобразование E.Теперь у вас есть:
источник
A + E*g = C + F*h
Две линии пересекаются тогда и только тогда, когда решение этого уравнения (при условии, что они не параллельны) имеет и то,g
и другое, иh
между 0 и 1 (в или исключая, в зависимости от того, считаете ли вы касание в конечной точке).Я попытался реализовать алгоритм, элегантно описанный Джейсоном выше; к сожалению, работая с математикой в отладке, я обнаружил много случаев, для которых она не работает.
Например, рассмотрим точки A (10,10) B (20,20) C (10,1) D (1,10), дающие h = .5, и все же из рассмотрения ясно, что эти сегменты не где-то рядом с каждым Другой.
Графики этого проясняют, что критерий 0 <h <1 только указывает, что точка пересечения будет лежать на CD, если она существует, но ничего не говорит о том, лежит ли эта точка на AB. Чтобы убедиться, что существует точка пересечения, вы должны выполнить симметричный расчет для переменной g, а требование для перехвата: 0 <g <1 И 0 <h <1
источник
Вот улучшение ответа Гэвина. Решение Marcp также похоже, но не откладывать деление.
На самом деле это также оказывается практическим применением ответа Гарета Риса, потому что эквивалентом перекрестного продукта в 2D является perp-dot-product, который используется в этом коде трижды. Переключение на 3D и использование перекрестного произведения, интерполяция s и t в конце, приводит к двум самым близким точкам между линиями в 3D. В любом случае, 2D решение:
В основном это откладывает деление до последнего момента и переносит большинство тестов до тех пор, пока не будут выполнены определенные вычисления, тем самым добавляя ранние выходы. Наконец, это также позволяет избежать деления на ноль, которое происходит, когда линии параллельны.
Вы также можете рассмотреть возможность использования теста эпсилон, а не сравнение с нулем. Линии, которые очень близки к параллельным, могут давать результаты, которые немного смещены. Это не ошибка, это ограничение по математике с плавающей точкой.
источник
s32_y
вместо того, чтобы описывать, что это такоеpoint2YDifference
?Вопрос C: Как вы определяете, пересекаются ли два отрезка?
Я искал ту же тему, и я не был доволен ответами. Поэтому я написал статью, в которой очень подробно объясняется, как проверить, пересекаются ли два отрезка с большим количеством изображений. Существует полный (и проверенный) Java-код.
Вот статья, обрезанная до самых важных частей:
Алгоритм, который проверяет, пересекается ли отрезок линии a с отрезком линии b, выглядит следующим образом:
Что такое ограничивающие рамки? Вот два ограничивающих прямоугольника из двух отрезков:
Если оба ограничивающих прямоугольника имеют пересечение, вы перемещаете отрезок линии a так, чтобы одна точка была в (0 | 0). Теперь у вас есть строка через начало координат, определенную как. Теперь передвиньте сегмент линии b таким же образом и проверьте, находятся ли новые точки сегмента линии b по разные стороны от линии a. Если это так, проверьте это с точностью до наоборот. Если это также имеет место, отрезки пересекаются. Если нет, они не пересекаются.
Вопрос A: Где пересекаются два отрезка?
Вы знаете, что два отрезка a и b пересекаются. Если вы этого не знаете, проверьте это с помощью инструментов, которые я дал вам в «Вопросе C».
Теперь вы можете пройти через некоторые случаи и получить решение по математике 7-го класса (см. Код и интерактивный пример ).
Вопрос B: Как вы определяете, пересекаются ли две линии?
Скажем , ваша точка
A = (x1, y1)
, точкаB = (x2, y2)
,C = (x_3, y_3)
,D = (x_4, y_4)
. Ваша первая строка определяется AB (с A! = B), а вторая - CD (с C! = D).Вопрос D: Где пересекаются две линии?
Проверьте с вопросом B, если они вообще пересекаются.
Линии a и b определены двумя точками для каждой линии. Вы можете применить ту же логику, что и в вопросе А.
источник
Один раз принятый здесь ответ неверен (с тех пор он не был принят, так что ура!). Это не правильно устраняет все непересекающиеся. Обычно это может работать, но это может не сработать, особенно в том случае, если 0 и 1 считаются действительными для h.
Рассмотрим следующий случай:
Линии в (4,1) - (5,1) и (0,0) - (0,2)
Это перпендикулярные линии, которые явно не пересекаются.
A = (4,1)
B = (5,1)
C = (0,0)
D = (0,2)
E = (5,1) - (4,1) = (- 1,0)
F = (0,2) - (0,0) = (0, -2)
P = (0,1)
h = ((4,1) - (0,0)) точка (0,1) / ((0 , -2) точка (0,1)) = 0
Согласно приведенному выше ответу, эти два отрезка линии встречаются в конечной точке (значения 0 и 1). Эта конечная точка будет:
(0,0) + (0, -2) * 0 = (0,0)
Таким образом, очевидно, что два отрезка линии встречаются в точке (0,0), которая находится на линии CD, но не на линии AB. Так что же не так? Ответ заключается в том, что значения 0 и 1 являются недопустимыми, и только иногда ПРОИЗОЙДЕТ, чтобы правильно предсказать пересечение конечной точки. Когда расширение одной линии (но не другой) будет соответствовать отрезку, алгоритм предсказывает пересечение отрезков, но это не правильно. Я полагаю, что при тестировании, начиная с AB против CD, а затем также с CD против AB, эта проблема будет устранена. Только если оба попадают между 0 и 1 включительно, можно сказать, что они пересекаются.
Я рекомендую использовать метод векторного перекрестного произведения, если вы должны предсказать конечные точки.
Дан
источник
Python-версия ответа iMalc:
источник
denom = float(...)
Нахождение правильного пересечения двух отрезков линии - нетривиальная задача с множеством краевых случаев. Вот хорошо документированное, работающее и протестированное решение на Java.
По сути, при нахождении пересечения двух отрезков может произойти три вещи:
Сегменты не пересекаются
Существует уникальная точка пересечения
Пересечение другой сегмент
ПРИМЕЧАНИЕ . В коде я предполагаю, что отрезок (x1, y1), (x2, y2) с x1 = x2 и y1 = y2 является допустимым отрезком. Говоря математически, линейный сегмент состоит из отдельных точек, но я позволю сегментам быть точками в этой реализации для полноты.
Код взят из моего репозитория github
Вот простой пример использования:
источник
Просто хотел упомянуть, что хорошее объяснение и явное решение можно найти в серии Numeric Recipes. У меня третье издание, и ответ на стр. 1117, раздел 21.4. Еще одно решение с другой номенклатурой можно найти в статье Марины Гавриловой. Надежное тестирование пересечения отрезков . Ее решение, на мой взгляд, немного проще.
Моя реализация ниже:
источник
Выше доступно множество решений, но я думаю, что решение ниже довольно просто и легко для понимания.
Два сегмента Vector AB и Vector CD пересекаются тогда и только тогда, когда
Более конкретно, a и b находятся на противоположной стороне сегмента CD, если и только если точно один из двух триплетов a, c, d и b, c, d находится в направлении против часовой стрелки.
Здесь CCW представляют против часовой стрелки, которая возвращает истину / ложь на основе ориентации точек.
Источник: http://compgeom.cs.uiuc.edu/~jeffe/teaching/373/notes/x06-sweepline.pdf Page 2
источник
CCW
определяется тест? С признаком внешнего продукта?C и Objective-C
Основано на ответе Гарета Риса
Многие функции и структуры являются частными, но вы должны довольно легко знать, что происходит. Это публично в этом репо https://github.com/hfossli/AGGeometryKit/
источник
Это хорошо работает для меня. Взято отсюда .
источник
Я попробовал некоторые из этих ответов, но они не сработали для меня (извините, ребята); после еще одного поиска в сети я нашел это .
С небольшой модификацией его кода у меня теперь есть эта функция, которая возвращает точку пересечения или, если пересечение не найдено, она возвращает -1, -1.
источник
Кажется, есть некоторый интерес к ответу Гэвина, для которого Кортиджон предложил версию javascript в комментариях, а iMalc предоставил версию с немного меньшим количеством вычислений . Некоторые указали на недостатки в различных предложениях кода, а другие прокомментировали эффективность некоторых предложений кода.
Алгоритм, предоставленный iMalc через ответ Гэвина, - это тот, который я сейчас использую в проекте javascript, и я просто хотел предоставить здесь очищенную версию, если она может кому-нибудь помочь.
источник
t = dx2 * dy3 - dx3 * dy2;
...t/d
приходит.crossProduct = (line1XDifference * line2YDifference) - (line2XDifference * line1YDifference)
аscaledResult = crossProduct / dotProduct
?p1x, p1y
и т. Д. Предназначены для описания точек по их значениям x и y, такp1x
что аббревиатура дляpoint1x
, аналогичноd1x
, на мой взгляд, аббревиатура для греческого письма,deltaX
или вы могли бы сказатьdifferenceInX
. (подробнее)Я думаю, что есть гораздо более простое решение этой проблемы. Сегодня у меня появилась другая идея, и она, кажется, работает отлично (по крайней мере, в 2D на данный момент). Все, что вам нужно сделать, это рассчитать пересечение между двумя линиями, а затем проверить, находится ли вычисленная точка пересечения в границах обоих отрезков. Если это так, отрезки пересекаются. Вот и все.
РЕДАКТИРОВАТЬ:
Вот как я вычисляю пересечение (я больше не знаю, где я нашел этот фрагмент кода)
происходит от
и это мой (упрощенный с целью ответа) класс BoundingBox:
источник
Это решение может помочь
источник
Я перенес приведенный выше ответ Криса на JavaScript. Перепробовав множество разных ответов, он дал правильные ответы. Я думал, что схожу с ума, что я не получаю очки, которые мне нужны.
источник
Я перепробовал много способов, а потом решил написать свой. Итак, вот оно:
Основываясь на этих двух формулах: (я упростил их из уравнения линий и других формул)
источник
Это основано на ответе Гарета Ри. Он также возвращает перекрытие отрезков, если они это делают. Кодируемый в C ++, V является простым векторным классом. Где перекрестное произведение двух векторов в 2D возвращает один скаляр. Это было проверено и прошло автоматическую систему тестирования моей школы.
источник
Вот базовая реализация линейного сегмента в C # с соответствующим кодом обнаружения пересечения. Для этого требуется двумерная векторная / точечная структура
Vector2f
, хотя вы можете заменить ее любым другим типом, имеющим свойства X / Y. Вы также можете заменитьfloat
на,double
если это лучше соответствует вашим потребностям.Этот код используется в моей библиотеке физики .NET, Boing .
источник
Программа на C ++ для проверки, пересекаются ли два заданных отрезка
источник
Основываясь на ответе @Gareth Rees, версия для Python:
источник
Если каждая сторона прямоугольника является линейным сегментом, а нарисованная пользователем часть является линейным сегментом, то вам нужно просто проверить нарисованный пользователем сегмент на предмет пересечения с четырьмя боковыми отрезками. Это должно быть довольно простым упражнением с учетом начальной и конечной точек каждого сегмента.
источник
На основании ответа t3chb0t:
источник
Я прочитал эти алгоритмы из книги "Геометрия с несколькими видами"
следующий текст, используя
'как транспонировать знак
* как точечный продукт
х в качестве перекрестного произведения, при использовании в качестве оператора
1. определение строки
точка x_vec = (x, y) 'лежит на прямой ax + by + c = 0
мы обозначаем L = (a, b, c) ', точка как (x, y, 1)' как однородные координаты
уравнение линии можно записать в виде
(x, y, 1) (a, b, c) '= 0 или x' * L = 0
2. пересечение линий
у нас есть две линии L1 = (a1, b1, c1) ', L2 = (a2, b2, c2)'
предположим, что x - это точка, вектор, и x = L1 x L2 (L1 - произведение L2).
будьте осторожны, x всегда является 2D-точкой, пожалуйста, прочитайте однородные координаты, если вы не уверены, что (L1xL2) - это вектор из трех элементов, а x - это 2D-координаты.
по тройному произведению мы знаем, что
L1 * (L1 x L2) = 0 и L2 * (L1 x L2) = 0 из-за L1, сопряженной плоскости L2
мы заменяем (L1xL2) вектором x, тогда имеем L1 * x = 0, L2 * x = 0, что означает, что x лежит как в L1, так и в L2, x является точкой пересечения.
будьте осторожны, здесь x - однородные координаты, если последний элемент x равен нулю, это означает, что L1 и L2 параллельны.
источник
Многие ответы обернули все вычисления в одну функцию. Если вам нужно рассчитать наклоны линий, y-перехваты или x-перехваты для использования в других местах вашего кода, вы будете выполнять эти вычисления с избыточностью. Я выделил соответствующие функции, использовал очевидные имена переменных и прокомментировал свой код, чтобы было легче следовать. Мне нужно было знать, пересекаются ли линии бесконечно за их конечными точками, поэтому в JavaScript:
http://jsfiddle.net/skibulk/evmqq00u/
источник