Алгоритм локализации точки в невыпуклой триангуляции
При редактировании триангуляции она может потерять выпуклость или возыметь в себе дыру (но не может полностью разделиться на 2 и более островов). Встала необходимость локализации очень большого количества точек в заданных условиях, а реализованный алгоритм поиска (итерационный с динамическим массивом), ни в какую не хочет работать хотя бы быстрее перебора всех треугольников. Может кто-нибудь подсказать алгоритм?
Ответы (1 шт):
Автор решения: Inen
→ Ссылка
Придумал +- решение, так что оставлю тут описание, на случай если когда-нибудь, кто-нибудь столкнётся с подобным:
- Прежде всего определяется находится ли точка внутри внешнего контура триангуляции.
- С помощью примерного поиска находим треугольник неподалёку от нужной точки.
- Создаём отрезок между некой точкой внутри треугольника и искомой точкой, а лучше несколько для хоть какой-то точности при превышении пределов значимых цифр double. (Далее отрезок называется А).
- Проверяем пересечение между А и внешним контуром триангуляции.
- При наличии оного находим ребро с которым произошло последнее пересечение .
- Продолжаем поиск обычным итерационным алгоритмом из треугольника которому принадлежит ребро из пункта 5.
Дополнение:
- Данный алгоритм работает только если точно известно что точка лежит внутри триангуляции.
- Опыты в голове и наяву показали что после пункта 5 при определенном контуре поиск всё равно может наткнуться на внешний контур. Это правится повторением алгоритма.
- Изначально думал что придётся переделывать контур из простого списка с отрезками в полноценный объект-полилинию, оказалось что это только усложнит задачу. Так что при таком поиске желательно отображать внешний контур именно как список отрезков.
P.S. Ничего лучше за полгода что у меня висит эта проблема я не придумал и не нашёл. Спасибо за ответы.