#algorithm #computational-geometry
Вопрос:
Предположим, у меня миллион треугольников: как я могу разделить эти треугольники на 1000 групп (произвольного размера), чтобы 1000 минимальных ограничивающих прямоугольников этих групп имели как можно меньше попарных перекрытий? Подойдет хорошая эвристика.
Справочная информация: Я распараллеливаю алгоритм геометрического алгоритма, в котором два потока не могут работать в одном и том же месте, и вышеуказанные группы должны быть рабочими единицами с как можно меньшим количеством зависимостей друг от друга. Мой подход до сих пор заключается в сортировке треугольников на кривой Гильберта и создании новой группы каждые 1000 элементов. Но, конечно, при этом учитывается только центр ограничивающих прямоугольников, а не их размер.
Комментарии:
1. Как происходит распределение треугольников? Примерно однородный или несколько мультимодальный?
2. Треугольники расположены на поверхности 3D-объекта. Их размер может сильно варьироваться.
3. О, так у вас есть полная триангуляция поверхности, а не просто несколько треугольников, плавающих вокруг несвязно?
4. Да, так оно и есть.
5. Что исключает наличие одной ограничительной рамки для всего, а затем 999 ограничительных рамок для отдельных треугольников? Там будет 999 перекрытий, что, вероятно, лучше, чем иметь 1000 ящиков, перекрывающихся несколькими соседями каждый.