Wie erzeugt man ein zufälliges konvexes Polygon?

Question

Ich versuche, eine Methode zur Erzeugung zufälliger konvexer 2D-Polygone zu entwickeln. Es muss die folgenden Eigenschaften haben:

• Koordinaten sollten ganze Zahlen sein;
• das Polygon soll innerhalb eines Quadrats mit den Ecken (0, 0) und (C, C) liegen, wobei C gegeben ist;
• das Polygon sollte eine Anzahl von Scheitelpunkten haben, die nahe an einer bestimmten Zahl N liegt.

Erzeugen Sie z. B. zufällige Polygone, die 10 Eckpunkte haben und innerhalb des Quadrats [0..100]x[0..100] liegen.

Was diese Aufgabe schwierig macht, ist die Tatsache, dass die Koordinaten ganze Zahlen sein müssen.

Der Ansatz, den ich ausprobiert habe, war, eine zufällige Menge von Punkten im gegebenen Quadrat zu erzeugen und die konvexe Hülle dieser Punkte zu berechnen. Aber die resultierende konvexe Hülle hat im Vergleich zu N nur sehr wenige Scheitelpunkte.

Irgendwelche Ideen?

Answer 1

Hier ist der schnellste mir bekannte Algorithmus, der jedes konvexe Polygon mit gleicher Wahrscheinlichkeit erzeugt. Die Ausgabe hat genau N Scheitelpunkte, und die Laufzeit ist O(N log N), so dass er auch große Polygone sehr schnell erzeugen kann.

• Erzeugen Sie zwei Listen, X y Y von N zufälligen ganzen Zahlen zwischen 0 und C. Achten Sie darauf, dass es keine Duplikate gibt.
• Sortieren X y Y und speichern ihre maximalen und minimalen Elemente.
• Teilen Sie die anderen (nicht maximalen oder minimalen) Elemente nach dem Zufallsprinzip in zwei Gruppen ein: X1 y X2 y Y1 y Y2 .
• Fügen Sie die minimalen und maximalen Elemente am Anfang und Ende dieser Listen wieder ein ( minX zu Beginn von X1 y X2 , maxX am Ende, usw.).
• Finden Sie die fortlaufenden Differenzen ( X1[i + 1] - X1[i] ), bei der zweiten Gruppe wird die Reihenfolge umgekehrt ( X2[i] - X2[i + 1] ). Speichern Sie diese in Listen XVec y YVec .
• Randomisieren (mischen) YVec und behandeln jedes Paar XVec[i] y YVec[i] als 2D-Vektor.
• Sortieren Sie diese Vektoren nach dem Winkel und legen Sie sie dann aneinander, um ein Polygon zu bilden.
• Verschieben Sie das Polygon zu den ursprünglichen Min- und Max-Koordinaten.

Eine Animation und eine Java-Implementierung finden Sie hier: Generierung zufälliger konvexer Polygone .

Dieser Algorithmus basiert auf einer Arbeit von Pavel Valtr: " Wahrscheinlichkeit, dass n Zufallspunkte in konvexer Lage sind ." Discrete & Computational Geometry 13.1 (1995): 637-643.

Answer 2

Unter @Mangara Antwort Es gibt JAVA-Implementierung falls jemand an einer Python-Portierung interessiert ist

import random
from math import atan2

def to_convex_contour(vertices_count,
                      x_generator=random.random,
                      y_generator=random.random):
    """
    Port of Valtr algorithm by Sander Verdonschot.

    Reference:
        http://cglab.ca/~sander/misc/ConvexGeneration/ValtrAlgorithm.java

    >>> contour = to_convex_contour(20)
    >>> len(contour) == 20
    True
    """
    xs = [x_generator() for _ in range(vertices_count)]
    ys = [y_generator() for _ in range(vertices_count)]
    xs = sorted(xs)
    ys = sorted(ys)
    min_x, *xs, max_x = xs
    min_y, *ys, max_y = ys
    vectors_xs = _to_vectors_coordinates(xs, min_x, max_x)
    vectors_ys = _to_vectors_coordinates(ys, min_y, max_y)
    random.shuffle(vectors_ys)

    def to_vector_angle(vector):
        x, y = vector
        return atan2(y, x)

    vectors = sorted(zip(vectors_xs, vectors_ys),
                     key=to_vector_angle)
    point_x = point_y = 0
    min_polygon_x = min_polygon_y = 0
    points = []
    for vector_x, vector_y in vectors:
        points.append((point_x, point_y))
        point_x += vector_x
        point_y += vector_y
        min_polygon_x = min(min_polygon_x, point_x)
        min_polygon_y = min(min_polygon_y, point_y)
    shift_x, shift_y = min_x - min_polygon_x, min_y - min_polygon_y
    return [(point_x + shift_x, point_y + shift_y)
            for point_x, point_y in points]

def _to_vectors_coordinates(coordinates, min_coordinate, max_coordinate):
    last_min = last_max = min_coordinate
    result = []
    for coordinate in coordinates:
        if _to_random_boolean():
            result.append(coordinate - last_min)
            last_min = coordinate
        else:
            result.append(last_max - coordinate)
            last_max = coordinate
    result.extend((max_coordinate - last_min,
                   last_max - max_coordinate))
    return result

def _to_random_boolean():
    return random.getrandbits(1)

Answer 3

Diese Liste ist nicht ganz vollständig, aber sie kann Ihnen einige Anregungen geben.

Aussteigen, wenn N < 3. Erzeugen Sie einen Einheitskreis mit N Scheitelpunkten, und drehen Sie ihn zufällig um [0..90] Grad.

Ziehen Sie jeden Scheitelpunkt nach dem Zufallsprinzip vom Ursprung aus nach außen und verwenden Sie das Vorzeichen des Kreuzprodukts zwischen jedem Paar benachbarter Scheitelpunkte und dem Ursprung, um die Konvexität zu bestimmen. Dies ist der Schritt, bei dem es einen Kompromiss zwischen Geschwindigkeit und Qualität gibt.

Nachdem Sie Ihre Scheitelpunkte eingerichtet haben, suchen Sie den Scheitelpunkt mit dem größten Abstand zum Ursprung. Teilen Sie jeden Scheitelpunkt durch diesen Wert, um das Polygon zu normalisieren, und skalieren Sie es dann wieder um (C/2) nach oben. Verschieben Sie es nach (C/2, C/2) und wandeln Sie es wieder in eine Ganzzahl um.

Answer 4

Ein einfacher Algorithmus würde lauten:

1. Beginnen Sie mit einer zufälligen Linie (ein Polygon mit zwei Scheitelpunkten und zwei Kanten)
2. Nehmen Sie eine beliebige Kante E des Polygons
3. Erstelle einen neuen Zufallspunkt P auf dieser Kante
4. Nehmen Sie eine Linie L, die senkrecht zu E durch den Punkt P verläuft. Berechnen Sie den maximalen Versatz von P, wenn die Konvexität nicht gebrochen ist, indem Sie den Schnittpunkt zwischen der Linie T und den Linien berechnen, die durch die beiden an E angrenzenden Kanten definiert sind.
5. Versetzen Sie den Punkt P zufällig in diesem Bereich.
6. Wenn nicht genügend Punkte vorhanden sind, wiederholen Sie den Vorgang ab 2.

Answer 5

Ich habe auch die Ruby-Portierung gemacht, dank der beiden @Mangaras Antwort y @Azat's Antwort :

#!/usr/bin/env ruby
# frozen_string_literal: true

module ValtrAlgorithm
  module_function def random_polygon(length)
    raise ArgumentError, "length should be > 2" unless length > 2

    min_x, *xs, max_x = Array.new(length) { rand }.sort
    min_y, *ys, max_y = Array.new(length) { rand }.sort
    # Divide the interior points into two chains and
    # extract the vector components.
    vec_xs = to_random_vectors(xs, min_x, max_x)
    vec_ys = to_random_vectors(ys, min_y, max_y).
      # Randomly pair up the X- and Y-components
      shuffle
    # Combine the paired up components into vectors
    vecs = vec_xs.zip(vec_ys).
      # Sort the vectors by angle, in a counter clockwise fashion. Remove the
      # `-` to make it clockwise.
      sort_by { |x, y| - Math.atan2(y, x) }

    # Lay them end-to-end
    point_x = point_y = 0
    min_polygon_x = min_polygon_y = 0
    points = []
    vecs.each do |vec_x, vec_y|
      points.append([vec_x, vec_y])
      point_x += vec_x
      point_y += vec_y
      min_polygon_x = [min_polygon_x, point_x].min
      min_polygon_y = [min_polygon_y, point_y].min
    end
    shift_x = min_x - min_polygon_x
    shift_y = min_y - min_polygon_y
    result = points.map { |point_x, point_y| [point_x + shift_x, point_y + shift_y] }
    # Append first point to make it a valid linear ring
    result << result.first
  end

  private def to_random_vectors(coordinates, min, max)
    last_min = last_max = min
    ary = []
    coordinates.each do |coordinate|
      if rand > 0.5
        ary << coordinate - last_min
        last_min = coordinate
      else
        ary << last_max - coordinate
        last_max = coordinate
      end
    end
    ary << max - last_min << last_max - max
  end
end