Расположение точек в сетках тетраэдра
Существуют ли какие-либо проверенные структуры данных для определения местоположения точек в сетках тетраэдров, где все тетраэдры не пересекаются, но «соприкасаются» друг с другом? т.е. большинство граней являются гранями ровно двух тетраэдров.
Под расположением я подразумеваю, что хочу узнать, в каком из тетраэдров находится данная точка, или не находится ни в одном.
До сих пор я пробовал:
Простое дерево KD -. Это было слишком медленно для моих нужд, так как средняя глубина дерева была очень большой, и у меня все еще было много отдельных тетраэдров для тестирования в каждом листе.
Сетка, содержащая все пересекающиеся тетраэдры для каждой ячейки. Кажется, это работает намного лучше, но все еще недостаточно быстро. Во-первых, сетка содержала много пустых ячеек, потому что моя общая сетка не очень «квадратная». Во-вторых, большинство ячеек, которые действительно содержали тетраэдры, действительно содержали их много (10+ ). Я полагаю, это потому, что многие тетраэдры имеют общие вершины, и как только вершина находится в ячейке, все соседние с ней тетраэдры тоже.
Дополнительная информация о входных данных :Сетка обычно невыпуклая и может иметь отверстия или включения. Хотя последние два несколько маловероятны, мне приходится иметь с ними дело, что делает "ходьбу" невозможной без (дорого и сложно? )предварительная обработка.