Нахождение выровненного осью прямоугольника в полигоне
Python рассматривает пустые строки как имеющие логическое значение «false» и непустые строки как имеющие логическое значение «true».
Таким образом, существует только два возможных результата выражения, то есть для пустая строка и для непустой строки.
Второе, что нужно заметить, это то, какое значение возвращает оператор «или» и «и». Python не возвращает только true или false значение, для строк и / или оператора он возвращает одну из строк (учитывая, что они имеют значение true или false). Python использует ленивый подход:
Для оператора «и», если значение left равно true, правильное значение проверяется и возвращается. если левое значение ложно, то оно возвращается
Для оператора «или», если первое значение истинно, оно возвращается. в противном случае, если второе значение ложно, затем возвращается второе значение
parameter = 'test'
print( parameter and (" " + parameter) or "" )
ouput: test
parameter = ''
print( parameter and (" " + parameter) or "" )
output: (пустая строка)
3 ответа
http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/
Имеет алгоритм для выпуклого, ссылки могли бы быть достойные внимания.
не уверенный, если это могло бы быть расширено на невыпуклый все же.
Одно решение состоит в том, чтобы разделить вогнутый полигон на выпуклые сегменты, тогда используют ссылку cobbal.
, Так как у Вас действительно есть две различных фундаментальных проблемы, Вы рассмотрели другие альтернативы тестовой задаче хита, такие как использование дерева BSP? Можно ускорить это далее путем наложения сетки по poly и построения дерева BSP для каждого квадрата сетки. Или kd-дерево с самое большее одним краем в каждом листе?
Редактирование: я уточню kd-дерево (из скуки, даже если это могло бы иметь какое-либо применение для кого-либо):
kd-деревья имеют следующие свойства:
- Они двоичные
- Каждое пространство разделений узла, не являющегося листом вдоль плоского перпендикуляра к оси, одной стороне на ребенка. Например, корень разделяет пространство на x < x0 и x> = уровни Дерева x0
- сменяются, разделяя вдоль различных осей, например, уровень 0 (корень) разделяет перпендикуляр к X, уровень 1-> Y, и т.д.
Для использования этого для обнаружения хита полигона, создайте дерево следующим образом:
- Выбор вершина для разделения вперед. (Preferrably где-нибудь близко к середине для сбалансированного дерева).
- Разделение другие вершины в два набора, один для любой стороны разделения. Вышеупомянутая вершина не входит ни в один набор.
- края Места в наборы также. Любой край, который пересекает строку разделения, входит в оба набора.
- дети Конструкции рекурсивно от вышеупомянутых групп.
, Если вершина разделения выбрана соответственно, дерево должно иметь глубину близко к журналу (N), где N является количеством вершин. Каждая вершина будет иметь самое большее один край, проходящий его. Сделать обнаружение хита:
- Находят лист, в который падает точка.
- , Если существует край в листе, сравните точку с ним. В противном случае должно быть очевидно, является ли точка внутри или снаружи (храните эту информацию в таких листах при построении дерева).
Только для ссылки, до сих пор все, что я имею, является грубой силой: сделайте сетку, и для точек на сетке, если они в полигоне, сделайте серию прямоугольников путем расширения каждого угла или стороны в свою очередь, пока это не поражает сторону. Тогда просто выберите самое большое.
самое простое (и очень эффективный) оптимизация только, чтобы протестировать, является ли узел решетки в полигоне, как только Вы проверили, что это не содержится в одном из прямоугольников, уже созданных, поскольку 'точка в прямоугольнике' проверка сверкает быстро.
По очевидным причинам, это довольно медленно и неточно, не говоря уже о неэлегантном:)