Выбор ближайшего соседа в QGIS

14

У меня есть список, содержащий более 100 000 точек в формате lat / long, который я импортировал в qgis.

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

Мои требования следующие:

  • ни одна группа в штучной упаковке не должна иметь менее 100 и не более 200 баллов
  • ни одна точка не должна находиться в более чем одной группе
  • все точки должны быть основаны на ближайшем соседе

Как я могу добиться этого через QGIS?

Я предполагаю, что можно передать некоторый пользовательский код запроса и сохранить результаты или поля, созданные как шейп-файл, правильно? Может кто-нибудь объяснить, как это можно сделать и как будет выглядеть код?

Как уже упоминалось, моя цель состоит в том, чтобы отображать в виде слоя шейп-файла группу квадратных блоков, в которых внутри каждого блока есть не менее 100 свойств и не более 200.

NetConstructor.com
источник
6
Всем, кто отметил этот вопрос в «фаворите»: почему бы не сказать об этом тоже? Казалось бы, ваш любимый вопрос должен быть хорошим вопросом.
Подземье
1
Зачем тебе бокс? Если вы создаете ящики на основе количества, они в любом случае будут иметь разные размеры, поэтому вопрос о плитке исключен. Вероятно, легче группировать в многоугольники (то есть выпуклый корпус).
diciu
@diciu спасибо за ответ. Да, я думаю, что выпуклый корпус будет в порядке, так как я мог бы превратить их в коробки после этого. Какой код я должен использовать, чтобы сделать это с использованием подхода выпуклой оболочки?
NetConstructor.com
2
Если вы используете выпуклые корпуса, ваши ограничивающие рамки (охватывающие корпуса) будут перекрываться, и ваше требование о наличии точки в одном BBOX больше не будет удовлетворено. Выпуклые корпуса не работают как промежуточный шаг к BBOX, а скорее как замена. И даже тогда создание общего решения будет довольно сложным.
diciu

Ответы:

13

Я могу помочь вам в этом, предположив, что вы выяснили, как запросить (а) самую восточную половину набора точек и (б) самую северную половину набора точек. Из них вы, конечно, можете легко получить (с) самую западную половину или (d) самую южную половину. (Я не знаю QGIS, но один из способов сделать (а) в общем случае - запросить медианную координату x и затем выбрать все точки, координаты x которых превышают это. Решения для (b) - (d) аналогичны .)

Используя эту возможность, решение получается с простой рекурсией. Чтобы описать это, давайте предположим, что существует процедура Half, реализующая предыдущие операции, которая принимает два аргумента: первый - это набор точек, а второй - код, равный тому, trueкогда желательно разделение восток-запад, и равный в falseпротивном случае. Он возвращает два подмножества своего ввода, которые разбивают его по запросу.

Procedure Box(P: set of points, i: boolean, n: integer)
Begin
    If (Count(P) > 2*n) then
        {R,S} = Half(P,i)
        Q = Box(R,!i,n) + Box(S,!i,n)
    Else
        Q = {P}
    Endif
    Return Q
End

В этом псевдокоде R и S разбиение P; Box (R,! I, n) является разбиением R в ортогональном направлении , Box (S,! I, n) является разбиением S в ортогональном направлении, «+» означает формирование теоретико-множественного объединения, и {} обозначает набор. (При изменении направления разделения создаются поля, а не полосы.) Параметр n указывает минимальный размер группы в разделе; максимальный размер 2 н .

пример

Здесь, в качестве иллюстрации, приведен набор P из 12 891 случайных точек, разделенных Box(P,true,100)на группы размером от 100 до 200. Алгоритм создает 128 блоков, из которых 37 имеют 100 баллов, а 91 - 101 балл.

Whuber
источник
2
Алгоритм эффективен. Работая на одном ядре, он обработал в 10 раз больше точек (128 910) за 18 секунд. Он масштабируется как O (n log (n) log (n)) для n точек. (Можно было бы улучшить, чтобы убрать один из этих факторов log (n), но это вряд ли стоит того.)
whuber
1
@W Вы использовали лексикографическую сортировку для облегчения разделения координат точек?
2
@ whuber это круто
Дассуки
1
@Dan Лексическая сортировка поможет, но не обязательна. Обратите внимание, что медиана из n значений может быть найдена за время O (n) (не O (n log (n))), поэтому разбиение точек на половины восток-запад или север-юг является асимптотически a O (n ) вычисления.
whuber