Расчет площади накопления

Question

Я ищу ГИС / Геометрический алгоритм:

У меня есть 1000 точек, случайно распределенных на большой территории (например, в городе). Как я могу узнать все маленькие области, которые имеют более 15 точек? Как на картинке ниже:

Каждая точка имеет свои координаты широты и долготы. Небольшая площадь менее 200 х 200 м.

Answer 1

Вы должны взглянуть на структуры RTREE.См. http://en.wikipedia.org/wiki/R-tree

У вас есть такие алгоритмы, например, в движке SQlite3.См. http://www.sqlite.org/rtree.html

Наша версия с открытым исходным кодом уже включает расширение RTREE для Delphi 6 вплоть до XE, скомпилировано по умолчанию с версии Rev.1,8 .

Answer 2

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

for i := 0 to 999 do
  for j := 0 to 999 do
    if i<>j then
      Point[i].Score := Point[i].Score + ( 1 / Distance(Point[i], Point[j]) );

Точки возле центра каждой области накопления будут иметь наивысший балл.