Erzeugen von Punkten in einem Bereich mit mindestens X Zwischenraumlänge dazwischen

Um Ihr Problem zu verstehen: Suchen Sie nach der optimalen Antwort (z. B. Hausaufgabe) oder nach einem sehr guten Algorithmus, der besser ist als das Erstellen zufälliger Punkte?

Im ersten Fall, ich fürchte, es ist ein sehr kompliziertes Problem, wenn Sie keine vorherigen Informationen über den Bereich A haben. Und ich glaube, dass es schwierig sein wird, einen Algorithmus zu finden, der schneller ist, als jeden einzelnen Fall zu erforschen .

Wenn Sie jedoch einige Vorabinformationen zu A haben, können die Dinge einfacher sein. Beispiel: Wenn es konvex ist , können Sie die Tatsache ausnutzen, dass das optimale Pflaster, wenn Ihr Raum unendlich ist, sechseckig ist . Das bedeutet, dass Sie Ihre Punkte (in X) an den Enden der Dreiecke platzieren müssen.

Also:

• berechne die konvexe Hülle (O (n * log (n)))
• berechne den Durchmesser (die zwei am weitesten entfernten Punkte deines Sets)
• Beginnen Sie, indem Sie einen der Punkte (des Durchmessers) zu X hinzufügen
• fügen Sie dann Punkte hinzu, die dem sechseckigen Pflaster entsprechen und die auf der konvexen Hülle bevorzugen

Dieser Algorithmus ist nicht optimal (es sei denn, Sie definieren ein sehr gutes "zugunsten der auf der konvexen Hülle" ...)

Edit: Mr. E's Kommentar erinnerte mich daran, dass das optimale Pflasterding von Kreisverpackung stammt. Hut ab vor ihm für die Präzision!

Allerdings habe ich einen anderen Algorithmus, der sehr nett aussieht und vielleicht sogar optimal ist! Er benötigt keine Bedingungen für A und ist ein bisschen teuer, aber nicht zu viel. Ja, ich weiß, es widerspricht dem, was ich gesagt habe, aber wen interessiert das? Ein guter Algorithmus ist nett genug.

Benennen Sie B mit der Menge der verfügbaren Punkte. Und C die Punkte, die die Extremitäten von B bilden. Zu Beginn ist B = A, und wenn A ein Quadrat ist, dann besteht C aus 4 Punkten (den Ecken). Sie müssen einfach rekursiv:

• berechne die beiden entferntesten Punkte von B. Dafür brauchst du nur die Punkte in C
• addiere zu X zufällig einen der Punkte (des Durchmessers)
• Entfernen Sie die Punkte von B, die jetzt nicht verfügbar sind. Sie müssen nur C dafür aktualisieren.

Ich weiß, dass wenn du in einem 1000x1000 Gitter arbeitest, C mit 4 Punkten beginnt, aber nachdem du einen Punkt zu X hinzugefügt hast, bedeutet das, dass C auf 1570 Punkte anwächst (ungefähr (pi / 2) 1000). Sie müssen bemerken, dass Sie nie in den Speicher B setzen, der groß ist (O (n ^ 2) wenn A in ein n Gitter gesetzt werden kann) Nur C, und ich glaube, dass an jedem Punkt die Größe von C ist O (n), was viel besser bleibt als O (n ^ 2). Und die Berechnung des Durchmessers bleibt O (Größe (C)) = O (n)

Hier sind meine Gedanken, ich denke, Sie müssen die Fläche in Quadrate mit Seitenlänge gleich Y teilen. Danach können Sie Rechtecke mit einer der Seiten kleiner als y übriglassen, es sei denn area = integer * y2. Jetzt können Sie maximal die Anzahl der Quadrate + Rechtecke generieren. Wenn X also mehr ist, können Sie die Methode mit einem Fehler beenden.

Um mit dem Erzeugen der Punkte zu beginnen, beginnen Sie mit dem letzten (unten rechts), kleinsten Rechteck. Wählen Sie einen zufälligen Punkt, und suchen Sie einen Punkt in seinem oberen und linken Rechteck, so dass sie Y vom ersten Punkt entfernt sind, und beginnen Sie, einen Punkt in einem Rechteck / Quadrat nur dann zu füllen, wenn sein unmittelbares rechts und unmittelbares unteres Quadrat / Rechteck ist gefüllt. Daher füllst du das erste Quadrat am Ende aus.

Während Sie den zufälligen Punkt erzeugen, müssen Sie sich nur um die Entfernung von maximal zwei Punkten kümmern, einen Punkt im unmittelbaren rechten Quadrat / Rechteck und den Punkt im unmittelbaren unteren Quadrat / Rechteck. Natürlich, wenn Sie mehr als X Punkte bekommen, können Sie entweder anhalten oder einige wenige Punkte ignorieren, um X Punkte übrig zu lassen

Um die Dinge zufälliger zu gestalten, können Sie beginnen, die Quadrate von Seite Y von jeder der vier Seiten zu tauchen (hier war es oben links), so dass der Startpunkt jedes Mal anders ist.

Wenn Sie sich auf Integer beschränken, dann gibt es einen Algorithmus, der funktioniert. Verfolgen Sie einfach die Anzahl der Standorte, die in jeder Zeile oder Spalte verfügbar sind, und berechnen Sie diese Werte für jede Zeile oder Spalte in der Nähe des neuen Punkts neu. Der Schlüssel hier ist, dass der ausgewählte zufällige Ort nur unter den verfügbaren Punkten ausgewählt wird, nicht das gesamte Gitter.

Das bringt eine Menge Komplexität in RemoveLocationsWithinDistance , aber das sollte nicht zu sein. Es wird ein 2-dimensionales quadratisches Array von Booleans der Größe Y benötigt.

Wenn Sie eine zufällige Verteilung wünschen, können Sie die Antwort "Ist ein Punkt weniger als y von diesem Punkt entfernt" in O (1) beantworten, indem Sie Ihr Gitter in Zellen der Größe y diskretisieren. Dann muss jeder Punkt P, der weniger als y von einem anderen Punkt Q entfernt ist, in einer von 9 Zellen sein, die an Zellen von Q angrenzen. Sie können also einfach eine Hash-Tabelle verwenden und 9 Prüfungen durchführen. Außerdem kann jede Zelle höchstens 2 Punkte enthalten.

Mit einer solchen Datenstruktur können Sie dann Stichproben mit Zurückweisung durchführen, um Ihren Platz zu füllen. Solange y im Vergleich zur Gesamtfläche relativ klein ist, werden Sie schnell Erfolg haben.

Sie könnten eine Molekulardynamik Technik verwenden.

Beginne mit einer großen Box und streue deine Punkte durch ein reguläres Gitter, mit Abstand & gt; Y.

Behandeln Sie nun jeden Punkt als ein sphärisches Teilchen, das mit den anderen Punkten durch ein abstoßendes Potential wie den abstoßenden Lennard-Jones interagiert, wobei die Parameter so gewählt sind, dass der effektive Durchmesser jedes Teilchens Y ist.

Geben Sie den Partikeln zufällige Geschwindigkeiten und lösen Sie die Bewegungsgleichungen mit einem diskreten Solver (sagen Sie Geschwindigkeit-Verlet, muss es nicht genau sein). Die Abstoßung zwischen den Partikeln wird die Partikel Y auseinander halten. Wenn Sie die Partikelpositionen aktualisieren, verkleinern Sie die Box jedes Mal ein wenig, bis Sie die gewünschte Größe erreicht haben. (Oh, die Box kann mit periodischen Randbedingungen oder einem repulsiven Feld mit kurzer Reichweite behandelt werden.)

Natürlich müssen Sie sicher sein, dass Sie alle Ihre Partikel in die Box passen können. In 2D ist die optimale Packung von Kreisen bekannt, siehe kepler Problem. Habe ich nicht gehört, dass das 3D-Kepler-Problem jetzt ebenfalls gelöst wurde?