Как создать сегменты линии от точек сетки

Question

Я пытаюсь создать сегменты линии сетки по сетке points.I имеют 34 очков, как это:

Размер изображения 720 * 480 с 34 сетки точки и координаты находятся здесь:

323.708 205.925 
382.585 206.75 
320.296 216.596 
381.729 217.499 
271.118 227.4 
286.04 227.643 
301.208 227.631 
316.538 228.165 
332.195 228.323 
348.114 228.828 
364.194 229.139 
380.893 229.356 
397.731 230.219 
414.795 230.634 
432.307 231.407 
312.507 241.026 
379.886 242.892 
307.735 254.944 
378.838 257.705 
251.514 268.437 
268.271 269.035 
285.124 269.701 
302.801 270.563 
320.684 271.637 
339.107 272.332 
358.067 273.122 
377.46 274.347 
397.01 275.033 
416.814 276.199 
437.558 277.354 
297.437 288.028 
375.766 292.266 
291.296 307.268 
374.233 313.316 

Я пробовал преобразование Хафа для определения линий сетки. Но мне просто нужно изображение, что промежутки между точками были заполнены (как это):

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

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

Answer 1

для каждой точки найти ближайшую точку в N,S,E,W направлениях и добавьте строку в список, если она еще не указана в списке. Если n этого числа точек я вижу это похоже:

1. петля i = <0,n-2>
2. петля j = <i+1,n-1>

3. для каждого направления оси

   добавить любую строку, которая имеет размер |pnt[i1]-pnt[i1]| меньше или равный размер сетки, и в то же время направление линии похоже на фактическое directio п NS или WE так:

   abs(dot(direction/|direction|,(pnt[i1]-pnt[i1])/|pnt[i1]-pnt[i1]|)) 
   

   близка к 1 или по крайней мере больше, то 0.75 если векторы направления не являются точными. Как направлений вы можете начать с:

   NS = (0.0, 1.0) 
   WE = (1.0. 0.0) 
   

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

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

Answer 2

Вы уже знаете важные моменты, поэтому преобразование Хафа довольно накладное.

Если есть только 34 (или даже сотни) точек, они образуют около 1000 пар, и вы можете построить линию для каждой пары, а затем сгруппировать эти строки в пространстве rho-theta без каких-либо сложных алгоритмов (этот подход квадратичен) , У вас будет 4 больших кластера, и нетрудно найти, какие сегменты линий (точек) из этих кластеров заканчиваются.

Для больших наборов данных вы можете сформировать начальные кластеры случайным образом для малых случайных точек подмножества, а затем добавить каждую точку к лучшей линии он подходит (линейный подход)