Wie Liniensegmente durch Gitter erzeugen Punkte

Question

Ich versuche Gitterliniensegmente zu erzeugen, durch Gitter points.I 34 Punkte wie diese:

Die Bildgröße ist 720 * 480 mit 34 Raster Punkte und die Koordinaten sind hier:

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 

Ich habe versucht, die Hough Transform zu erkennen Gitterlinien. Aber ich brauche nur ein Bild, das die Lücken zwischen den Punkten wurden (wie diese) gefüllt:

so, dass ich die nächste Arbeit tun konnte. Die Verwendung von Hough Transformation ist ein wenig verschwendet.

Ich habe versucht, lineare Interpolation zu verwenden, um die Lücke zu füllen, aber ich muss die Endpunkte manuell finden. Daher möchte ich wissen, wie man die Gitterliniensegmente automatisch durch diese Gitterpunkte erzeugt.

Answer 1

für jeden Punkt am nächsten Punkt in N,S,E,W Richtungen finden und Fügen Sie eine Zeile zu einer Liste hinzu, wenn sie nicht bereits in der Liste vorhanden ist. Wenn n Anzahl der Punkte ist, sehe ich es mag:

1. loop i = <0,n-2>
2. loop j = <i+1,n-1>

3. für jede Achsenrichtung

   jede Zeile hinzufügen, die eine Größe hat |pnt[i1]-pnt[i1]| weniger oder gleich dann Rastergröße und gleichzeitig Richtung der Linie ist ähnlich zu tatsächlichen directio n NS oder WE so:

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

   liegt nahe 1 oder zumindest größere dann 0.75, wenn die Richtungsvektoren nicht genau sind. Als Richtungen können Sie beginnen mit:

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

   Die NS-Richtung mehr abgewichen ist, so sollten Sie wahrscheinlich größeren Spielraum für sie zum Vergleich verwenden.

   Sie können in Punktprodukt für Einheitsvektoren der Normierungen loszuwerden

Answer 2

Sie kennen bereits wichtige Punkte, also Hough Transformation ist ziemlich Overhead.

Wenn es nur 34 (oder sogar hunderte) Punkte gibt, bilden sie etwa 1000 Paare, und Sie können für jedes Paar eine Linie erstellen, dann diese Linien im Rho-Theta-Raum ohne komplexe Algorithmen gruppieren (dieser Ansatz ist quadratisch) . Sie haben 4 große Cluster, und es ist nicht schwer zu finden, welche Liniensegmente (Punkte) von diesen Clustern enden.

Für größere Datenmengen können Sie ersten Cluster in zufälliger Weise für kleine zufällige Punktteilmenge bilden, dann jeden Punkt auf die beste Linie paßt hinzuzufügen (linearer Ansatz)