Одно из решений состоит в том, чтобы разбить вогнутый многоугольник на выпуклые сегменты, а затем использовать связь Коббала.
Поскольку у вас действительно есть две разные фундаментальные проблемы, рассматривали ли вы другие альтернативы задаче проверки попадания, такие как использование дерева BSP? Вы можете ускорить это дальше, наложив сетку на поли и построив дерево BSP для каждого квадрата сетки. Или kd-дерево с не более чем одним ребром в каждом листе?
Редактировать: Я разработаю kd-дерево (без скуки, даже если оно кому-нибудь пригодится):
kd-деревья имеют следующие свойства:
- Они двоичные
- Каждый неконечный узел разделяет пространство вдоль плоскости, перпендикулярной оси, по одной стороне на каждого дочернего элемента. Например. корень разбивает пространство на x = x0
- Уровни дерева по очереди разделяются по разным осям, например, уровень 0 (корень) разделяется перпендикулярно X, уровень 1 -> Y и т. д.
Чтобы использовать это для обнаружения попадания многоугольника, постройте дерево следующим образом:
- Выберите вершину для разделения. (Желательно где-то близко к середине для сбалансированного дерева).
- Разбить другие вершины на два набора, по одному для каждой стороны разбиения. Вышеупомянутая вершина не входит ни в один набор.
- Поместите ребра в наборы. Любое ребро, которое пересекает линию разделения, входит в оба набора.
- Рекурсивно строите детей из вышеперечисленных групп.
Если расщепленная вершина выбрана надлежащим образом, глубина дерева должна быть близка к log (N), где N - количество вершин. Каждый листовой узел будет иметь не более одного ребра, проходящего через него. Для определения попадания:
- Найдите лист, в который попадает точка.
- Если на листе есть ребро, сравните точку с ним. В противном случае должно быть очевидно, находится ли точка внутри или снаружи (сохраняйте эту информацию в таких листьях при построении дерева).