TLDR: мне нужно создать объект Python для быстрого тестирования внутренней точки, аналогично SciPy ConvexHull
или DelaunayTriangulation
. Загвоздка в том, что я заранее знаю порядок, в котором должна строиться триангуляция точек: (6 точек, 8 треугольных граней, с определенным порядком каждой грани). По сути, я уже знаю, какой должна быть выпуклая оболочка, но мне нужно, чтобы она была в форме, которую я могу использовать с существующими (и оптимизированными!) библиотеками (например, Scipy пространственного). Как я могу это сделать?
Контекст: мне нужно построить треугольную призму (представьте себе стержень Toblerone — 2 торца, 6 боковых граней, все треугольные), чтобы провести тестирование внутренней точки. Поскольку у меня будет много таких призм, лежащих рядом друг с другом (смежных боковыми гранями, представьте, что многие стержни Тоблерона стоят на своих концах и рядом друг с другом), мне нужно быть осторожным, чтобы гарантировать, что ни одна область в пространстве не содержится в двух соседние призмы. Поперечное сечение призмы, как правило, не будет однородным, отсюда возможность перекрытия между соседними призмами, как показано на этой диаграмме приблизительно плоской грани между двумя соседними призмами:
____
|\ /|
| \/ |
| /\ |
|/__\|
Обратите внимание на две разные диагонали, построенные вдоль грани — в этом проблема. Одна призма может разделить грань на два треугольника с помощью диагонали \, а соседняя призма может вместо этого использовать /. Чтобы гарантировать отсутствие перекрытия между соседними призмами, мне нужно явно контролировать порядок, в котором формируются треугольники, чтобы они всегда использовали одну и ту же диагональ. Это я могу сделать: для каждой призмы, которую мне нужно построить, я заранее знаю, в каком порядке должны быть построены треугольные грани. Вот иллюстрация двух соседних призм с правильной общей диагональю между ними: соседние призмы, общая диагональ< /а>
Моя проблема связана с выполнением быстрого тестирования внутренней точки с этими призмами. Ранее я использовал подход, связанный с этим -выпуклая-оболочка-точки-cl/16898636#16898636">ответ: Delaunay(prism_points).find_simplex(test_points) >= 0
. Это быстро, потому что используется высокооптимизированный библиотечный код, но я не контролирую построение триангуляции, поэтому могут быть перекрытия.
Если я создам корпуса как явные np.array
объекты (вершины, грани), то я могу использовать свой собственный код для выполнения тестов (существует множество возможных подходов, я проецирую лучи и проверяю пересечение с каждой треугольной гранью). Проблема в том, что это примерно в 100 раз медленнее, чем подход find_simplex()
, упомянутый ранее. Хотя я уверен, что мог бы получить код немного быстрее, стоит отметить, что этот код уже достаточно оптимизирован для другого варианта использования с Cython - я не уверен, смогу ли я найти здесь всю дополнительную скорость, которая мне нужна. Что касается неизбежного «вам действительно нужен вопрос о скорости», пожалуйста, поверьте мне на слово. Это превращает 5-минутную работу в многочасовую.
Что мне нужно, так это создать объект, который я могу использовать с внешними оптимизированными библиотеками, сохраняя при этом контроль над треугольными гранями. Добавление дополнительного Cython в мой код, конечно, вариант, но такой высокооптимизированный код уже существует, использование которого было бы гораздо предпочтительнее.
Спасибо всем, кто может помочь.