Расчет площади накопления - программирование

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

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

Ответы

Ответ 1

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

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

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

Ответ 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]) );

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