Алгоритмы, дискретная математика и пр.'s Journal (original) (raw)

3:08p

Алгоритм сортировки точек на полигональной сетке Здравствуйте.

Задача примерно такая. Есть границы расчётной области. Её надо поделить на ячейки. Желательно, чтобы ячейки имели поменьше периметра на единицу площади, а площадь была примерно одинаковой. Ну, то есть, чтобы не были вытянутыми и сильно разного размера. Потом надо набор расчетных частиц быстро рассортировать по номерам ячеек. Всё, никаких уравнений по узлам сетки строить не нужно.

Сейчас использую четырёхугольную сетку. Сетка делится на 4-х угольные мастер-ячейки, перемещение частиц между которыми отслеживается, а мастер-ячейка поделена на подъячейки равномерно. Подъячейка (номера строки и столбца) вычисляются делением координаты частицы на размер ячейки, если опустить подробности. Отслеживания перемещения частицы по подъячейкам, таким образом, не требуется. Боковые границы ячеек и подъячеек всегда вертикальные. Сортировка, таким образом, занимает O(N) времени, где N -- число частиц.

Однако, четырёхугольная сетка не всегда удобна. Хочу перейти на полигональную сетку. Соответственно, возникают алгоритмические вопросы:

Построить такую сетку, удобную во всех отношениях, и хранить её в памяти.
Как можно быстрее сортировать частицы по ячейкам. Частица движется равномерно по прямой или параболической траектории, и может пересекать до десятка подъячеек между сортировками.

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

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

Желательно, чтобы была большая свобода выбора количества подъячеек на большой треугольник, вернее, площади маленьких треугольников.

Есть ещё мелкая несущественная засада: границы расчетной области могут иметь большое число отрезков, но слишком сильно мельчить подъячейки нельзя. Поэтому, в случае треугольной сетки, в приграничных зонах нужно использовать какое-то особое разбиение, допускающего лёгкое объединение мелких ячеек в крупные. Но границ мало. Там можно и топорно подойти к вопросу -- использовать мелкие неразбитые мастер-ячейки и таблицу их объединения. Главное, чтобы приграничная сетка естественным образом стыковалась с основной.