Identifizieren und Sortieren mehrerer Kreise auf der Ebene 2d mit Python

Question

Ich habe mehrere Punkte, die viele Kreise auf einer 2d-Ebene bilden und müssen sie für die weitere Berechnung identifizieren und sortieren. Ich habe die [x, y] -Koordinaten jedes Punktes und eine Zahl, die jeden Punkt repräsentiert.

Alle Punktnummern in einem Kreis sollten in einer Liste sortiert sein. und dann sollten Punktnummern des nächsten Kreises folgen. Sagen wir, jeder Kreis besteht aus 6 Punkten. Sie sollten zuerst und dann nächste 6 Punkte des benachbarten Kreises folgen.

Ich habe festgestellt, dass Convex Hull eine Möglichkeit ist, geschlossene Polygone zu identifizieren. Dies ist ähnlich, aber ich möchte, dass mehrere konvexe Hüllen in derselben Ebene identifiziert werden. Ich denke, das sollte in Python möglich sein. Kann mir bitte jemand weiterhelfen?

Edit:

1. die Kreise nicht überlappen
2. die Kreise alle gleich groß sind, das heißt gleichen Radius
3. jeder Kreis hat die gleiche Anzahl von Punkten.
4. sie sind gleichmäßig verteilt Löcher. der Lochradius ist sehr spezifisch - 10 mm und das gesamte Array ist rechteckig. eine Platte mit einer Anordnung von gleichmäßig beabstandeten Löchern - wenn auch - Reihe von Löchern sind gestaffelt.

Bauplan: Kreise auf einem Teller anrichten. Jeder Kreis ist durch 10 Punkte definiert. Wir haben die (x, y) Koordinaten dieser Punkte

Answer 1

Zu wissen, die Besonderheiten von Ihrem bearbeiten können einige Abkürzungen für die Aufnahme. Lassen Sie mich neu zu formulieren/schließen, ein paar Dinge:

1. Löcher sind in Zeilen/Spalten die und vertikal/horizontal sind nicht überlappen
2. Löcher sind alle Standard-Breite/Höhe (gleiche Durchmesser)
3. x- oder y-Wert für den ‚ersten‘ Punkt jeden Loch in einer gegebenen Zeile/Spalte das gleiche sein wird (unter der Annahme Ihrer FEM eine konsistente Orientierung Loch verwendet)

Mit diesen Beobachtungen in mi nd, ich würde etwas naives wie das folgende versuchen (pseudocode outline), bevor ich die bereits erwähnten Algorithmen in den Kommentaren implementiere. Dies führt offensichtlich nicht zum Ausführen von Code, sondern bringt hoffentlich das Konzept in eine andere Richtung - im Allgemeinen erstellt es Spalte "Bins" von Punkten (Col 1, Col 2) und teilt diese in Row Bins auf (die dann alle Punkte in einem gegebenen Loch repräsentieren).

## sort points into an array by x, then y 
# while unmapped_points.count > 0 
    ## Determine the lowest 'x' value (far left) 
    ## Create a column 'bin' of all points with x <= (x_min + diameter) 
    # while column_bin.count > 0 
     # Determine lowest 'y' value (bottom edge of hole) 
     # Create a row (hole) 'bin' of all points with y <= (y_min + diameter) 
     # Update y_curr to minimum y from remaining points in column 
    # Update x_curr to minimum x from all remaining points 

Wenn wir noch weniger allgemeinen Fall und fügen Sie eine weitere Bedingung:

4. Initial Offsets und Spalten-/Zeilenabstand sind bekannt

Sie dann könnte überspringen die Punkte direkt Start Spalten-/Zeilengrenzen und nur Fenster zu finden:

# Hole1 = points where (p.x >= x1_offset and p.x <= x1_offset + diameter) and (p.y >= y1_offset and p.y <= y1_offset + diameter) 

Obwohl, wenn die layo ut bereits bekannt ist, können Sie auch nur Mittelpunkte und Schleife berechnen durch die Punkte innerhalb des bekannten Radius zu finden:

# points where sqrt((p.x - c.x)^2 + (p.y - c.y)^2) < radius 

Aber ich den Abstand unter der Annahme, ist nicht bekannt - sonst könnte man nur die Punkte erzeugen, ohne etwas zu wissen über das FEA-Modell durch Schleifen durch jeden Mittelpunkt und Berechnen von Offsets mit dem bekannten Radius und gleichmäßig inkrementierten Winkeln.