Как работает инструмент Сортировать

Инструмент Сортировать может сортировать по атрибутам и пространственным характеристикам. После пространственной сортировки повышается эффективность пространственных или геометрических операций.

Для пространственной сортировки объектов (т.е по местоположению), используйте параметр Поля, чтобы указать поле геометрии входных данных (обычно называемое Shape). Использование поля Shape включает параметр Метод пространственной сортировки. Параметр Метод пространственной сортировки поддерживает следующие опции сортировки: Левый верхний, Правый верхний, Левый нижний, Правый нижний и Пеано.

Пространственная сортировка

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

Опцию сортировки Правый верхний можно продемонстрировать, взяв в качестве входных данных равномерно распределенный набор точек.

Пространственная сортировка с опцией Правый верхний

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

Ниже приведена иллюстрация того, как верхний и правый компоненты сортировки работают вместе.

Иллюстрация сортировки, чтобы различать верхнюю и правую

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

Пространственная сортировка Пеано

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

Иллюстрация сортировки Пеано

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

Ниже приведены преимущества алгоритма заполнения пространства:

  • Он быстрый.
  • Он не требует расчета расстояний между местоположениями.
  • Он распараллеливаемый.

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