Один из способов представления пространственных объектов в виде иерархической древовидной структуры, основанный на декомпозиции пространства на квадратные участки, или квадратные блоки, квадранты (quarters, quads), каждый из которых делится рекурсивно на 4 вложенных до достижения некоторого уровня - числа Мортона (Morton orders), обеспечивающего требуемую детальность описания объектов, эквивалентную разрешению растра; обычно используется как средство снижения времени доступа, повышения эффективности обработки и компактности хранимых данных по сравнению с растровыми представлениями, являясь, образно выражаясь, "интеллектуализированным" растром. Обычно используется схема пространственной нумерации (индексирования) элементов К.п., известная как матрица Мортона (Morton matrix), основанная на кривых Пиано (Peano curves) и числах Пиано (Peano keys). Аналогичные древовидные структуры типа трихотомических деревьев (tri tree) могут строиться также на множестве треугольных элементов модели TIN. Менее известны гексотомические деревья (hextree), основанные на разделении пространства на шестиугольники (гексагоны). Предложены и используются расширения К.п. на многомерные случаи, в том числе трехмерный случай в форме т.н. октотомического дерева или октарного дерева (octatree).
RSS
Реклама
