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 eine andere Version von Valtrs Algorithmus mit Numpy :)

import numpy as np
import numpy.typing and npt

def generateConvex(n: int) -> npt.NDArray[np.float64]:
    '''
    Generate convex shappes according to Pavel Valtr's 1995 alogrithm. Ported from
    Sander Verdonschot's Java version, found here:
    https://cglab.ca/~sander/misc/ConvexGeneration/ValtrAlgorithm.java
    '''
    # initialise random coordinates
    X_rand, Y_rand = np.sort(np.random.random(n)), np.sort(np.random.random(n))
    X_new, Y_new = np.zeros(n), np.zeros(n)

    # divide the interior points into two chains
    last_true = last_false = 0
    for i in range(1, n):
        if i != n - 1:
            if random.getrandbits(1):
                X_new[i] = X_rand[i] - X_rand[last_true]
                Y_new[i] = Y_rand[i] - Y_rand[last_true]
                last_true = i
            else:
                X_new[i] = X_rand[last_false] - X_rand[i]
                Y_new[i] = Y_rand[last_false] - Y_rand[i]
                last_false = i
        else:
            X_new[0] = X_rand[i] - X_rand[last_true]
            Y_new[0] = Y_rand[i] - Y_rand[last_true]
            X_new[i] = X_rand[last_false] - X_rand[i]
            Y_new[i] = Y_rand[last_false] - Y_rand[i]

    # randomly combine x and y and sort by polar angle
    np.random.shuffle(Y_new)
    vertices = np.stack((X_new, Y_new), axis=-1)
    vertices = vertices[np.argsort(np.arctan2(vertices[:, 1], vertices[:, 0]))]

    # arrange points end to end to form a polygon
    vertices = np.cumsum(vertices, axis=0)

    # center around the origin
    x_max, y_max = np.max(vertices[:, 0]), np.max(vertices[:, 1])
    vertices[:, 0] += ((x_max - np.min(vertices[:, 0])) / 2) - x_max
    vertices[:, 1] += ((y_max - np.min(vertices[:, 1])) / 2) - y_max

    return vertices

Answer 2

Hier ist eine C++11-Umsetzung des Algorithmus von Pavel Valtr, der in Mangaras Antwort mit einigen ähnlichen Tricks wie lewiswolf's Antwort und mehr Zufälligkeit durch getrennte Teilung der X- und Y-Koordinaten.

#include <algorithm>
#include <iostream>
#include <random>

struct randPoly {
  int RND_MAX = 655369;
  std::random_device dev;
  std::mt19937 rng;
  std::uniform_int_distribution<std::mt19937::result_type> random_numer;
  std::uniform_int_distribution<std::mt19937::result_type> random_logic;

  randPoly() : rng(dev()), random_numer(0, RND_MAX), random_logic(0, 1) {}
  virtual ~randPoly() {}

  int generate(const int n, const double r0, std::vector<double>& poly_x,
               std::vector<double>& poly_y) {
    auto gen = [&]() { return random_numer(rng); };
    // initialize random samples and sort them
    int m = n / 2;
    std::vector<int> x(n), y(n), vx(n), vy(n), idx(n);
    std::vector<double> a(n);
    std::generate(x.begin(), x.end(), gen);
    std::generate(y.begin(), y.end(), gen);
    std::iota(idx.begin(), idx.end(), 0);
    std::sort(x.begin(), x.end());
    std::sort(y.begin(), y.end());
    // divide samples and get vector component
    int x0 = x[0], x1 = x0;
    for (int k = 1; k < n - 1; ++k) {
      if (random_logic(rng)) {
        vx[k - 1] = x[k] - x0;
        x0 = x[k];
      } else {
        vx[k - 1] = x1 - x[k];
        x1 = x[k];
      }
    }
    vx[n - 2] = x[n - 1] - x0;
    vx[n - 1] = x1 - x[n - 1];
    int y0 = y[0], y1 = y0;
    for (int k = 1; k < n - 1; ++k) {
      if (random_logic(rng)) {
        vy[k - 1] = y[k] - y0;
        y0 = y[k];
      } else {
        vy[k - 1] = y1 - y[k];
        y1 = y[k];
      }
    }
    vy[n - 2] = y[n - 1] - y0;
    vy[n - 1] = y1 - y[n - 1];
    // random pair up vector components and sort by angle
    std::shuffle(vy.begin(), vy.end(), rng);
    for (int k = 0; k < n; ++k) {
      a[k] = std::atan2(vy[k], vx[k]);
    }
    std::sort(idx.begin(), idx.end(),
              [&a](int& lhs, int& rhs) { return a[lhs] < a[rhs]; });
    // form the polygon by connencting vectors
    double x_max = 0, y_max = 0, x_min = 0, y_min = 0;
    x[0] = y[0] = 0;
    for (int k = 1; k < n; ++k) {
      x[k] = x[k - 1] + vx[idx[k - 1]];
      y[k] = y[k - 1] + vy[idx[k - 1]];
      if (x[k] > x_max) {
        x_max = x[k];
      } else if (x[k] < x_min) {
        x_min = x[k];
      }
      if (y[k] > y_max) {
        y_max = y[k];
      } else if (y[k] < y_min) {
        y_min = y[k];
      }
    }
    // center and resize the polygon
    poly_x.resize(n);
    poly_y.resize(n);
    double x_offset = -(x_max + x_min) / 2.0;
    double y_offset = -(y_max + y_min) / 2.0;
    double scale = r0 / std::max(x_max - x_min, y_max - y_min);
    for (int k = 0; k < n; ++k) {
      poly_x[k] = scale * (x[k] + x_offset);
      poly_y[k] = scale * (y[k] + y_offset);
    }
    return 0;
  }
};

int main(int, char**) {
  randPoly rp;
  std::vector<double> poly_x, poly_y;
  rp.generate(8, 2.0, poly_x, poly_y);
  for (int k = 0; k < poly_x.size(); ++k) {
    std::cout << poly_x[k] << "  " << poly_y[k] << std::endl;
  }
}

Beispiel in Rviz gezeigt

Answer 3

Ihr ursprünglicher Ansatz ist richtig - die Berechnung der konvexen Hülle ist die einzige Möglichkeit, Zufälligkeit, Konvexität und Ganzheitlichkeit zu erfüllen.

Die einzige Möglichkeit, den Algorithmus zu optimieren, um "mehr Punkte" zu erhalten, besteht darin, die Punkte kreisförmig anzuordnen, anstatt sie völlig zufällig zu verteilen. Die Punkte sollten sich eher an den "Rändern" des Quadrats befinden als in der Mitte. In der Mitte sollte die Wahrscheinlichkeit ~0 sein, da das Polygon konvex sein muss.

Eine einfache Möglichkeit wäre die Festlegung eines Mindestradius für die Anzeige der Punkte - vielleicht C/2 oder C*0,75. Berechnen Sie den Mittelpunkt des C-Quadrats, und wenn ein Punkt zu nahe ist, verschieben Sie ihn vom Mittelpunkt weg, bis ein Mindestabstand erreicht ist.