Обнаружение прямоугольника из массива точек C#

Question

У меня есть изображение и массив точек изнутри изображения.

Некоторые точки близки друг к другу, некоторые из них не имеют «соседей». Я ищу способ найти суб-изображение, которое формируется точками, которые имеют много соседей, в конечном итоге с заданным максимальным расстоянием между ними.

Вот пример:

Как вы можете видеть на картинке, есть несколько точек, некоторые из них близки, некоторые из них не имеют каких-либо близких соседей. Я хочу найти прямоугольник, который находится, установив точку на изображении, где несколько точек находятся в очень близком диапазоне. Это всегда будет прямоугольник, и на одном изображении может быть несколько прямоугольников/пятен.

Я использую библиотеку AForge (C#) для некоторой обработки изображений. Искал алгоритмы, которые делают это, но не нашли многого. Я уверен, что есть алгоритм для этой цели, я его еще не нашел.

Любые предложения приветствуются.

Answer 1

Я не знаю библиотеку AForge, но если у вас не так много точек (например, в примере), простой алгоритм поиска ближайшего соседства будет просто замечательным.

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

• Эти соседи должны храниться в какой-то структуре данных (например, в массиве). Если соседей больше нет, повторите поиск, начиная с найденного соседа и так далее.

• Наконец, у вас будет множество районов, где вы просто выбираете самый большой набор (набор с наибольшим количеством точек).

• Затем просто вычислите прямоугольник вокруг этих точек (угловые точки).

Если предположить, что большинство точек расположены внутри прямоугольника, которого вы ищете, вы можете просто вычислить «центральную точку» все точки (в среднем). Начиная с этого момента, вы ищете ближайшую точку, и у вас есть поиск ближайшего соседа. В этом случае у вас будет только один набор точек, в которых вы можете снова построить прямоугольник.