Предположим, вам дано уравнение линии (в 2d) и уравнения линий, которые образуют выпуклый многоугольник (многоугольник может быть неограниченным). Как определить, пересекает ли линия полигон?Как проверить, пересекает ли линия выпуклый многоугольник?
Кроме того, существуют ли вычислительные библиотеки геометрии, где такие задачи предопределенные? Я спрашиваю, потому что меня интересует не только 2D-версия, но и n-мерная геометрия.
В геометрии, как правило, see wikipedia ограничен полигон. То, что вы описываете, как правило, называется многогранник или многогранник see wikipedia
Есть несколько библиотек геометрии доступны, два, которые приходят на ум, импульс (многоугольник) и CGAL. Как правило, существует четкое разделение между вычислительными методами, которые имеют дело с 2d, 3d и N-d - по очевидным причинам.
Для вашей проблемы я бы использовал несколько двоичный подход к пространственному разделительному дереву. Я бы взял первую строку вашего «поли» и обрезал линию запроса против нее, создав луч. Луч начинался с пересечения двух линий и продолжался в направлении внутренней части полупространства, созданного первой линией «поли». Теперь я повторю процедуру с лучом и второй строкой «поли». (это может генерировать сегмент вместо луча). Если в какой-то момент начало луча (или теперь сегмент) лежит на внешней стороне рассматриваемой полилинейной линии и не пересекает ее, тогда ответ не будет - линия не пересекается ваш «поли». В противном случае он пересекается. Особое внимание уделяйте различным случаям с параллельными краями. Довольно прямо и работает для многомерных случаев.
Для 2D-футляра, я думаю, проблема немного упрощается.
Линия разделяет пространство на две области.
Если многоугольник присутствует только в одной из этих областей, то линия не пересекает его.
Если многоугольник присутствует в обеих областях, то линия пересекает его.
Итак:
Возьмите любой перпендикулярно к линии, что делает пересечение с линии происхождения.
Проецируйте каждую вершину многогранника на перпендикуляр.
Если эти выступы встречаются с обоими знаками, то полигон пересекает линию.
[Update следующего комментария elexhobby в.]
Забыл включает обработку неограниченного случая.
Я хотел добавить, что для создания открытой области можно создать «виртуальную вершину». Нам действительно нужно «направление» открытой местности. Мы можем считать это средним векторов для границ ребра открытой области.
Затем мы обрабатываем точечный продукт этого направления с нормалью и добавляем его к множеству вершинных проекций.
Я не совсем уверен, но я думаю, вы можете обратиться к этому с помощью двойственности. Сначала нормализуйте свои линейные уравнения как a.x+b.y=1, и рассмотрите набор точек (a,b).
Они должны образовывать выпуклый многоугольник, и я предполагаю, что новая строка может не соответствовать точке внутри многоугольника. Это легко проверить, подтвердив, что новая точка находится на одной стороне всех ребер. (Если вы не знаете порядок линий, сначала постройте выпуклую оболочку.)
Начнем с конечных полигонов.
Чтобы пересечь многоугольник, линия должна пересекать один из его ребер. Пересечение между линией и ребром возможно только в том случае, если две точки лежат по разные стороны от линии.
Это может быть легко проверено с помощью sign(cross_product(Ep-Lp,Ld)) для двух точек края. Ep - краевая точка, Lp - некоторая точка на линии, Ld - вектор направления линии, cross_product(A,B)=Ax*By-Ay*Bx.
Для решения бесконечных многоугольников мы можем ввести «бесконечные точки». Если у нас есть половина бесконечного края с точкой E1 и направлением Ed, ее «вторая точка» - это что-то вроде E1+infinity*Ed, где infinity «достаточно большое число».
Для «бесконечных точек» проверка будет немного отличаться: cross_product(Ep-Lp,Ld)= =cross_product(E1+infinity*Ed-Lp,Ld)= =cross_product(E1-Lp+infinity*Ed,Ld)= =cross_product(E1-Lp,Ld)+cross_product(infinity*Ed,Ld)= =cross_product(E1-Lp,Ld)+infinity*cross_product(Ed,Ld)
Если cross_product(Ed,Ld) равен нулю (линия параллельно краю), знак будет определяться первым компонентом. В противном случае второй компонент будет доминировать и определять знак.
Ну не совсем верно? Диаграмма слева имеет тот же знак для точечного произведения всех вершин с нормалью, но он пересекает многогранник. – elexhobby
@elexhobby. Спасибо - совершенно верно; Я имел это в виду, а затем забыл включить его. См. Править. – Keith