Учитывая точку и большое количество тетраэдров, как эффективно определить, в каком тетраэдре находится точка?

Предположим, мы определяем точку как набор из трех чисел с плавающей запятой, а тетраэдр — как набор из четырех точек.

Предположим, у нас есть тетраэдр и точка, мы можем определить, принадлежит ли точка тетраэдру, следуя решениям, описанным в Как проверить, находится ли точка в тетраэдре или нет? Ключевая идея заключается в том, чтобы определить, находится ли точка на внутренних сторонах тетраэдра четыре стороны тетраэдра.

Моя проблема. Учитывая точку и N тетраэдров, где N составляет около 7 миллионов, мне нужно определить, в каком тетраэдре находится точка. Мы позаботимся о производительности повторных тестов с большим количеством баллов.

Дополнительная информация:

  1. Можно просто проверить эти тетраэдры один за другим, используя методы, упомянутые выше. Но это может быть слишком медленно, учитывая мое большое количество тетраэдров.

  2. В постановке задачи есть конкретный момент. Эти тетраэдры получены из задачи МКЭ (метод конечных элементов) для решения задачи медицинской визуализации (они формируют мозг пациентов). Возможно, сам МКЭ не имеет отношения к вопросу, но мы могли бы использовать тот факт, что эти тетраэдры расположены рядом друг с другом и в пространстве, моделируемом этими тетраэдрами, нет «дыр».

  3. Тетраэдры не имеют пересечений, кроме как на соседней границе. Таким образом, этот вопрос должен иметь единственное решение, если только не на границе, и в этом случае ответом на мою проблему может быть любой из пересекающихся тетраэдров.

  4. Определенных порядков, в которых тетраэдры задаются на входе, нет. Нет никаких указаний на то, являются ли формы тетраэдров правильными или нет.

Любая идея по эффективному решению проблемы? Python предпочтительнее в решении этой проблемы.

Спасибо!


python performance vectorization finite-element-analysis tetrahedra
person zell    schedule 15.09.2020    source источник
comment
1. Есть ли порядок, в котором тетраэдры даны на входе? (Возможно, машина сканирует мозг послойно?) 2. Правильно ли я понимаю, что нас интересует только выполнение одного теста, а не повторные тесты? (моей первой мыслью было октодерево, но это может быть слишком дорого для одного теста) 3. Как насчет формы тетраэдров - большинство из них правильные или наклонные? 4. Я бы начал с тривиального (minx, miny, minz) ‹= (px, py, pz) ‹= (maxx, maxy, maxz), чтобы отсечь кандидатов, и только затем провел бы полный тест.   -  person Lesiak    schedule 15.09.2020
comment
Спасибо, что подумали об этом. Чтобы ответить на ваш вопрос: Нет конкретных порядков, в которых тетраэдры даны на входах. Нет никаких указаний на то, являются ли формы тетраэдров правильными или нет. И мы заботимся о выполнении повторных тестов.   -  person zell    schedule 16.09.2020

Ответы (2)


arrow_upward
3
arrow_downward

Вы можете сначала отфильтровать тетраэдры, оставив только те, для которых ограничивающий прямоугольный параллелепипед (параллельный осям X, Y и Z) содержит p. Это быстрее проверить:

Итак, найдите тетраэдры с точками t0, t1, t2 и t< sub>3 -- которые имеют следующее свойство относительно точки p:

  • ∃ i,j: tix ≤ px ≤ tjx< /суп>
  • ∃ i,j: tiy ≤ py ≤ tjy< /суп>
  • ∃ i,j: tiz ≤ pz ≤ tjz< /суп>

В среднем это оставит вам всего несколько тетраэдров (часто только один или два), которые вы затем используете для применения теста точки в тетраэдре.

person trincot    schedule 16.09.2020
comment
Большое спасибо! Состояние вашего фильтра мне понятно. Мне просто интересно, как ты добрался. В среднем у вас останется всего несколько тетраэдров (часто только один или два). Вы это поняли по опыту или по теории? - person zell; 17.09.2020
comment
Обдумывая это, первой идеей было отсортировать все тетраэдры по их наименьшей координате x, а затем стало ясно, что координата x точки должна быть не меньше x, принадлежащего окружающему ее тетраэдру. Более того, вы обнаружите, что это должно быть верно также для y и z и в обоих направлениях. Что касается среднего из одного или двух: это было просто обоснованное предположение при визуализации такого пространства. Конечно, могут быть крайние случаи, когда многие тетраэдры имеют одну и ту же точку, а может быть, даже все, и точка, которую нужно найти, может быть этой точкой. Но это только крайний случай, а не средний. - person trincot; 17.09.2020
comment
Я понимаю. Кроме того, я предполагаю, что ограничение фильтрации (minx, miny, minz) ‹= (px, py, pz) ‹= (maxx, maxy, maxz), которое Лесиак предложил в своих комментариях, на самом деле делает то же самое, что и ваше. Верно? - person zell; 17.09.2020
comment
Да, это кубовидный тест. Как я выразился, иногда можно сэкономить время: как только вы найдете один x среди углов тетраэдра, который не больше px, вы можете перейти к следующему требованию, а для вычисления minx нужно всегда искать во всех четырех углах. Очевидно, вы можете предварительно обработать тетраэдры и сохранить их минимальные/максимальные значения для x, y, z, и тогда это будет быстрее за счет некоторого пространства. - person trincot; 18.09.2020

arrow_upward
2
arrow_downward

Если вы планируете протестировать множество точек на одном и том же наборе тетраэдров, я бы определенно пошел на шаг предварительной обработки и построил пространственную структуру для тетраэдров.

В своем комментарии я упомянул октодерево, но зная, что тетраэдры заполняют пространство (без отверстий), я думаю, что нет необходимости в адаптивном подразделении пространства, и лучше всего разделить его на равные части.

  1. Разделите пространство на равные квадраты (назовем их SpaceBoxes).
  2. В каждом SpaceBox сохраните список тетраэдров, которые сталкиваются с прямоугольником.
  • Чтобы ускорить его, я бы проверил ограничивающую рамку тетраэдра, а не сам тетраэдр.
  • Обратите внимание, что этот шаг может быть выполнен относительно дешево — вы знаете, что SpaceBox имеют одинаковые размеры, вы знаете их положение, поэтому, учитывая ограничивающую рамку тетраэдра, легко найти кандидатов SpaceBox.

Теперь, имея эту пространственную структуру:

Для точки, подлежащей проверке p

  • найти соответствующий SpaceBox O(1)
  • у вас есть все тетраэдры, которые сталкиваются с SpaceBox, так что это кандидаты на проверку
  • первое тестовое столкновение p с ограничивающей рамкой каждого тетраэдра
  • только потом, с самим тетраэдром

Обратите внимание, что производительность теста в основном зависит от количества тетраэдров в каждом SpaceBox.

Предполагая, что пространство является кубом:

  • разделение каждого края на 16 частей дает вам 16 ^ 3 = 4096 SpaceBox.
  • имея N = 7000000, должно быть примерно 1709 тетраэдров-кандидатов для проверки.

Кроме того, с точки зрения реализации как предварительная обработка, так и тестирование нескольких точек выглядят как проблемы с параллельными данными, поэтому может помочь многопроцессорная обработка.

person Lesiak    schedule 16.09.2020
comment
Большое спасибо! Как бы вы сравнили свой метод фильтрации с предложенным ниже тринкотом? Я чувствую, что тринкот кажется проще в реализации, и тринкот упоминает, что после фильтрации можно получить только 1-2 тетраэдра (вы получите .1709 кандидатов). Как бы вы сравнили эффективность двух подходов? - person zell; 17.09.2020
comment
Кроме того, под коробкой вы имели в виду 3D-куб? Кроме того, я не уверен, какое ребро вы имели в виду, подразделяя каждое ребро на 16 частей? Но я думаю, что понял вашу идею - сначала предварительно обработайте. - person zell; 17.09.2020
comment
Кстати, я просто понимаю, что ограничение фильтрации тринкота должно быть таким же, как вы предложили в своих комментариях ранее, то есть (minx, miny, minz) ‹= (px, py, pz) ‹= (maxx, maxy, maxz) . Как вы думаете, ваша идея SpaceBox была бы более эффективной? - person zell; 17.09.2020
comment
1. Под коробкой я подразумеваю трехмерный куб (или прямоугольный параллелепипед, в зависимости от размеров всего пространства). 2. разделение каждого ребра на 16 частей - я предположил, что пространство трехмерно. Вы делите каждое измерение на 16 частей, таким образом, вы получаете 16 ^ 3 SpaceBoxes 3. (minx, miny, minz) ‹= (px, py, pz) ‹= (maxx, maxy, maxz) действительно является тестом на принадлежность к ограничивающая рамка (или ограничивающий параллелепипед, если вы предпочитаете это имя) - person Lesiak; 18.09.2020
comment
4. ответ тринкота - это именно то, что я предложил в первоначальном комментарии - пройти через все 7 миллионов тетраэдров, но вместо проверки столкновения с тетраэдром (что требует некоторых численных расчетов) сначала выполните тест столкновения ограничивающей рамки. Таким образом, мы надеемся, что вы сможете протестировать с настоящими тетраэдрами пару, прошедшую тест ограничивающей рамки. Минус — для следующей точки нужно повторить 7 миллионов проверок ограничивающего прямоугольника. - person Lesiak; 18.09.2020
comment
5. Моя идея состоит в том, чтобы уменьшить количество проверок ограничительной рамки для каждого повторного теста, поэтому для каждой точки вы выполняете только ~ 1700 (с 4096 прямоугольниками) проверок ограничительной рамки и получаете то же отфильтрованное количество кандидатов, которые прошли тест ограничительной рамки. 6. Обязательно начните сначала с теста ограничивающей рамки, прежде чем добавлять этап предварительной обработки. Как вы заметили (и я упомянул в начальном комментарии), это тривиально реализовать. возможно, вы получите желаемое ускорение с помощью этой простой модификации. - person Lesiak; 18.09.2020