Wie generieren Quadrate (zufällig befindet sich, gleich große, zufällig gedreht), die sich nicht überschneiden?

Habe ich gearbeitet, auf die Schaffung einer Schicht von zufällig gedreht und platziert Quadrate auf einem 1x1 Gitter. Ich war in der Lage, generieren Sie ein einzelnes Quadrat, das ist zufällig platziert und gedreht auf dem raster, aber ich bin mir nicht sicher, wie Sie Sie, den code zu verbessern, mehr zu erzeugen zufällige Quadrate, die nicht miteinander überschneiden. Aktuelle code unten gesehen:

Beispiel meiner Einer Randomisierten Platz

from math import cos, pi, sin
from random import randint
from matplotlib.mlab import frange
from matplotlib.pyplot import plot, axis, show

def flake_position_layer1(): #Determines the initial position of one corner of the square
    x0 = randint(0, 100) / 100
    y0 = randint(0, 100) / 100
    theta = randint(0, 90) * pi / 180 #Angle of rotation for the square
    return x0, y0, theta


def flake_shape(): #generates the other 3 corners of the square
    x0, y0, z, theta = flake_position_layer1()
    x1 = x0 + (0.1 * cos(theta))
    x2 = x1 + (0.1 * cos((90 * pi/180) + theta))
    x3 = x2 + (0.1 * cos((180 * pi/180) + theta))
    y1 = y0 + (0.1 * sin(theta))
    y2 = y1 + (0.1 * sin((90 * pi/180) + theta))
    y3 = y2 + (0.1 * sin((180 * pi/180) + theta))
    return x0, x1, x2, x3, y0, y1, y2, y3


def display(): #connects the 4 corners on a plot
    x0, x1, x2, x3, y0, y1, y2, y3 = flake_shape()
    return plot([x0, x1, x2, x3, x0], [y0, y1, y2, y3, y0])


display()
axis([0,1,0,1]) #1x1 grid
show()

Habe ich nicht ein CS-hintergrund (ich bin ein environmental engineering major) und ich bin sehr unerfahren mit Programmieren. Bitte geben Sie mir irgendwelche Empfehlungen, die Sie haben, für mich zu versuchen und dieses problem anzugehen mit!

  • Ist es möglich, zu prüfen, eine kreisförmige enveloppe rund um den Platz ? In einem solchen Fall können Sie das Zentrum der einzelnen Plätze und stellen Sie sicher, dass der Abstand zwischen den beiden center > 2*z.
  • Verwenden rejection sampling, mehr zu erzeugen Quadrate: if(current square overlaps) reject(); else add_square_to_list();
  • Wie groß tun, die Plätze werden müssen? Wenn Sie können, machen Sie weniger als ~70% (1/√2) die grid-Größe, die Sie nie überlappen.
InformationsquelleAutor Deputy McMunch | 2017-09-06
  1. 3

    Mathematischen hintergrund

    1. Algebra

    2. Ebene Geometrie

    • Einer Ebene besteht aus einer (unendlichen) Anzahl der Punkte: wir bezeichnen Sie einen Punkt durch seine Koordinaten, die genannt werden kann:

      • Abszisse oder horizontale Koordinate oder (einfach) x
      • ordinate oder vertikale Koordinate oder (einfach) y

    • Die Punkte in der Ebene, verteilt auf 2 Dimensionen

    • In der Ebene, jeder Punkt eindeutig durch seine x und y
    • Einige der Punkte in der Ebene, vielleicht haben einige gemeinsame Merkmale: z.B. eine Reihe von Punkten, die auf einer geraden Linie... ein Punkt auf einer geraden Linie erfüllt die Linie gerade Linie Gleichung (das ist ein Ausdruck, der im Allgemeinen definiert als ${Funktion (aus den vorhergehenden Absatz) Ergebnis} = ${value})
    • Also, kurz gesagt: für einen Punkt P0(x0, y0), wenn y0 == f(x0), der Punkt ist sich auf , dass gerade Linie (und mehr: je nach y0 wird größer /unteren als f(x0), P0 befindet sich oben /unten die gerade Linie in der xOy Flugzeug). Wieder möchte ich Ihnen mitteilen, dass für nicht-lineare Funktionen, y = f(x) gilt weiterhin (wie es die Allgemeine Gleichung Formel), aber auch andere Operatoren (z.B. <, >) nicht
      • ! Wichtiger Hinweis !: alles, was hier erörtert wird, betrifft eine Vielzahl von Funktionen (ich will nicht sagen, alle), aber ich bin die Begrenzung auf lineare Funktionen, um der Klarheit Willen
    • Eine gerade Linie wird bestimmt durch 2 verschiedene Punkte (z.B. P0(x0, y0), P1(x1, y1)) - die Gleichung für die gerade Linie wäre y = a * x + b (in unserem Beispiel: y = ((y0 - y1) /(x0 - x1)) * x + (y0 - x0 * ((y0 - y1) /(x0 - x1)))); !! Natürlich ist es erwähnenswert, die "vertikale" (parallel zu Oy) Linie !! nicht eine Funktion !!

    • Beispiel: 2 verschiedene parallel (nicht Bolyai 🙂 ) Linien: f0(x) = a * x + b0 und f1(x) = a * x + b1 (eine ist die gleiche für beide Linien - das ist der Zustand für Sie zu sein, parallel) und einem externen Punkt P0(x0, y0) (die natürlich nicht gehören zu einer der Linien). Wie Sie feststellen, ob P0 ist zwischen den 2 Zeilen? Gut, der Punkt muss oben sein (die untere) ein, und unter die andere (die höhere). Übersetzt in Mathematik (unter Berücksichtigung f0 wird die untere):

      • y0 > f0(x0) (y0 - f0(x0) > 0)
      • y0 < f1(x0) (y0 - f1(x0) < 0)

      Aus der obigen Beobachtungen (und es kann mehr Weisheit), das ist die Bedingung, dass die Koordinaten der Punkte erfüllen müssen: (y0 - f0(x0)) * (y0 - f1(x0)) < 0

    • Weiter: ein Quadrat besteht aus 2 Gruppen von parallelen Linien (Seiten); wenn ein Punkt zwischen den einzelnen Linien-pair-Mädchen, dann ist der Punkt in dem Quadrat.

    code.py:

    #!/usr/bin/env python3

import sys
from random import random, seed
from math import pi, sin, cos, sqrt
import matplotlib.pyplot as plt

pi_2 = pi / 2

MINX = MINY = 0
MAXX = MAXY = 1
DEFAULT_SIDE = 0.1
DEFAULT_SAFETY_MARGIN = DEFAULT_SIDE * sqrt(2)
MAX_SQUARES = 30

__global_generation_counter = 0


def get_func_deg1(p0, p1):
    (x0, y0), (x1, y1) = p0, p1
    if x0 == x1:
        return None
    a = (y0 - y1)/(x0 - x1)
    b = y0 - x0 * a
    return lambda x: a * x + b


def is_point_in_square(p, sq):
    x, y = p
    p0, p1, p2, p3 = sq
    side_func0 = get_func_deg1(p0, p1)
    side_func1 = get_func_deg1(p1, p2)
    side_func2 = get_func_deg1(p2, p3)
    side_func3 = get_func_deg1(p3, p0)
    if not side_func0 or not side_func1 or not side_func2 or not side_func3:
        xmin = min(p0[0], p2[0])
        xmax = max(p0[0], p2[0])
        ymin = min(p0[1], p2[1])
        ymax = max(p0[1], p2[1])
        return xmin <= x <= xmax and ymin <= y <= ymax
    return ((y - side_func0(x)) * (y - side_func2(x))) <= 0 and \
           ((y - side_func1(x)) * (y - side_func3(x))) <= 0


def squares_overlap(square0, square1):
    for p0 in square0:
        if is_point_in_square(p0, square1):
            return True
    for p1 in square1:
        if is_point_in_square(p1, square0):
            return True
    xc0 = (square0[0][0] + square0[2][0]) / 2
    yc0 = (square0[0][1] + square0[2][1]) / 2
    if is_point_in_square((xc0, yc0), square1):
        return True
    # The "reverse center check" not needed, since squares are congruent
    """
    xc1 = (square1[0][0] + square1[2][0]) /2
    yc1 = (square1[0][1] + square1[2][1]) /2
    if is_point_in_square((xc1, yc1), square0):
        return True
    """
    return False


def __generation_monitor():
    global __global_generation_counter
    __global_generation_counter += 1


def generate_random_point(minx=MINX, miny=MINY, maxx=MAXX, maxy=MAXY, safety_margin=DEFAULT_SAFETY_MARGIN):
    if maxx - minx < 2 * safety_margin or maxy - miny < 2 * safety_margin:
        print("MUEEE")
        safety_margin = 0
    x = safety_margin + random() * (maxx - minx - 2 * safety_margin)
    y = safety_margin + random() * (maxy - miny - 2 * safety_margin)
    __generation_monitor()
    return x, y


def generate_random_angle(max_val=pi_2):
    return random() * max_val


def generate_random_square(side=DEFAULT_SIDE, squares_to_avoid=()):
    while 1:
        restart = False
        x0, y0 = generate_random_point()

        angle = generate_random_angle()
        x1 = x0 + side * cos(angle)
        y1 = y0 + side * sin(angle)

        angle += pi_2
        x2 = x1 + side * cos(angle)
        y2 = y1 + side * sin(angle)

        angle += pi_2
        x3 = x2 + side * cos(angle)
        y3 = y2 + side * sin(angle)

        ret = (x0, y0), (x1, y1), (x2, y2), (x3, y3)
        for square in squares_to_avoid:
            if squares_overlap(ret, square):
                restart = True
        if restart:
            continue
        return ret


def square_to_plot(square):
    xs, ys = zip(square[0], square[1], square[2], square[3])
    return xs + (xs[0],), ys + (ys[0],)


def main():
    seed()
    squares = list()
    allow_overlapping = False # CHANGE to True to allow square to overlap
    for _ in range(MAX_SQUARES):
        #print("Generating:", _)
        if allow_overlapping:
            square = generate_random_square()
        else:
            square = generate_random_square(squares_to_avoid=squares)
        squares.append(square)
    plot_squares = tuple()
    for sq in squares:
        plot_squares += square_to_plot(sq)
    print("STATS:\n    Squares: {}\n    Allow  overlapping: {}\n    Generated values: {}".format(MAX_SQUARES, allow_overlapping, __global_generation_counter))
    plt.plot(*plot_squares)
    plt.axis([MINX, MAXX, MINY, MAXY])
    plt.show()


if __name__ == "__main__":
    print("Python {:s} on {:s}\n".format(sys.version, sys.platform))
    main()

    Hinweise:

    • Ich nicht die Arbeit mit matplotlib vor (tatsächlich, ich pip installed es für diese Aufgabe)

    • Allgemeine Bemerkungen:

      • Einem Punkt, dargestellt durch ein Tupel repräsentiert seine Koordinaten: (x, y)
      • Ein Quadrat ist ein Tupel, bestehend aus 4 Punkte (p0, p1, p2, p3)
    • get_func_deg1:
      • Gibt die Funktion beschreibt die Zeile, der 2 Punkte gegeben als Argumente
      • Wenn die 2 Punkte auf einer Linie, die parallel zu Oy (es gibt keine "normale" Funktion um es zu beschreiben), einfach wieder Keine
    • is_point_in_square:
      • Bestimmt, ob ein Punkt in einem Quadrat
      • Verwendet die Logik oben erläutert, außer
      • Für den speziellen Fall, wenn die eckigen Kanten sind parallel zu Ox und Oy, wenn es verwendet einige einfache arithmetische Operationen
    • squares_overlap:
      • Bestimmt, ob 2 Quadrate überschneiden (ich bin sicher, es gibt schnellere "algorithmen")
      • Überprüft, ob die 1st abgerundete Ecken im inneren sind die 2nd eine
      • Anders herum: überprüft, ob die 2nd abgerundete Ecken im inneren sind die 1st eine
      • Seit über 2 Prüfungen sind nicht genug (stellen Sie sich eine regelmäßige [Wikipedia]: Octagon und Vereinheitlichung der Scheitelpunkte jedes 2nd: es werden 2 Quadrate weder mit den Ecken in die andere, sondern teilen Ihre "zentrale" Bereiche), überprüfen Sie auch, dass one square center ist innerhalb des anderen
    • generate_random_point:
      • Erzeugt einen Punkt in der gegebenen bounding box
      • safety_margin bestimmt die (Mindest -) Abstand, den der erzeugte Punkt sollte sein, Weg von den Seiten des Begrenzungsrahmens, damit alle Platz haben wird dieser Punkt als eine Ecke passen würde, die vollständig in der bounding box
    • generate_random_angle:
      • Generiert einen zufälligen Winkel zwischen 0 und (π /2)
    • generate_random_square:
      • Generiert einen zufälligen Punkt einen zufälligen Winkel aus, und erstellt ein Quadrat, beginnend von dort mit der angegebenen Seite
      • squares_to_avoid ist eine Liste der Quadrate. Nach dem Quadrat erzeugt wird, wird geprüft, gegen jeden Platz aus, die Liste. Wenn die 2 Quadrate überschneiden, ist der Platz regeneriert
    • square_to_plot:
      • Wandelt ein Quadrat (aus einem Tupel von Punkten) zu matplotlib - format (2-Tupeln bestehend aus xs und ys mit 1st - element dupliziert als die Letzte)
    • main:
      • Die main-Funktion
    • __generation_monitor *:
      • Interne Funktion, die für das profiling eingesetzt
    • Um ändern Sie die Anzahl der Quadrate, ändern MAX_SQUARES

    Ausgabe:

    Wie generieren Quadrate (zufällig befindet sich, gleich große, zufällig gedreht), die sich nicht überschneiden?

    [cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q046081491]> "e:\Work\Dev\VEnvs\py_064_03.05.04_test0\Scripts\python.exe" code.py
STATS:
    Squares: 30
    Allow  overlapping: False
    Generated values: 1135

    * - Einige Worte über die Quadrate generation

    • Wie in der Ausgabe, für 30 Quadrate angezeigt, 1135 generiert wurden (bei diesem Lauf). Das ist, weil Sie überlappende
    • Wenn Sie aus dem main allow_overlapping = True, Generierten Werte in der Ausgabe wird mit der Anzahl der Quadrate (MAX_SQUARES)
    • Ob eine Erhöhung MAX_SQUARES zu Werten, sagen wir mal höher als 50, die Anzahl der generierten Werte werden exponentiell zunehmen (so wird die Zeit benötigt, um diese generieren), und die chance, dass das Programm geben Sie eine Endlosschleife (weil es nicht in der Lage erzeugen Sie ein Quadrat, das Nachholspiel nicht zu einem anderen) wachsen wird als gut
    InformationsquelleAutor CristiFati
  2. 1

    Okay, hier ist was ich habe kommen mit, mit ein wenig Hilfe von der formschöne Paket. Installations-Hilfe ist in der unten hier. Das ultimative Ergebnis:

    Wie generieren Quadrate (zufällig befindet sich, gleich große, zufällig gedreht), die sich nicht überschneiden?
    Wie generieren Quadrate (zufällig befindet sich, gleich große, zufällig gedreht), die sich nicht überschneiden?

    Code walkthrough

    • distance ist eine Hilfsfunktion, mit der Point Klasse von wohlgeformten zu finden, den Abstand zwischen zwei Koordinaten. Nur eine Hilfsfunktion für später.
    • Square Instanziierungen ein neues polygon. Es hat 4 Ecken, jeweils (x,y) - paar, die eine Koordinate für den Mittelpunkt, und einen skalaren Wert, der gleich der Hälfte der Entfernung seiner diagonalen.
    • test_overlap ist ziemlich selbsterklärend durch den Titel. Aber logisch, was es tut, ist dies: der Abstand von Mitte zu Mitte zwischen den beiden Formen. Dann finden Sie die Summe der halben Diagonale der einzelnen Formen. Wenn der center-to-center-Abstand größer als die Summe der Quadrate nicht überlappen.
    • Squares beginnt mit einem leeren container (leere Liste) und versucht, hinzufügen Plätze zu. Aber für jeden möglichen Neuzugang, es Premieren tests, dass es keine überschneidungen mit den bestehenden Plätzen.

    - Code

    import math
import random

from shapely.geometry import Polygon, Point


def distance(a, b):
    return Point(a).distance(Point(b))


class Square(object):
    def __init__(self):
        self.x0, self.y0 = random.random(), random.random()
        theta = random.randint(0, 90) * math.pi / 180  # Angle of rotation
        self.x1 = self.x0 + (0.1 * math.cos(theta))
        self.x2 = self.x1 + (0.1 * math.cos((90 * math.pi/180) + theta))
        self.x3 = self.x2 + (0.1 * math.cos((180 * math.pi/180) + theta))
        self.y1 = self.y0 + (0.1 * math.sin(theta))
        self.y2 = self.y1 + (0.1 * math.sin((90 * math.pi/180) + theta))
        self.y3 = self.y2 + (0.1 * math.sin((180 * math.pi/180) + theta))
        self.corners = ((self.x0, self.y0), (self.x1, self.y1), 
                        (self.x2, self.y2), (self.x3, self.y3))

    @property
    def center(self):
        """(x, y) of the center of the polygon."""
        return Polygon(self.corners).centroid.coords[0]

    @property
    def half_diag(self):
        """The distance of 1/2 the shape's diagonal (center-to-corner)."""
        p0, p1, p2, p3 = self.corners
        return 0.5 * distance(p0, p1) * math.sqrt(2)


def test_overlap(square1, square2):
    """Do two shapes overlap?  

    Note this is a 'conservative' test.  May return True if they do not
    (false positive), but will never return False if they do (false negative).
    """

    # Distance between two centers
    ctc = distance(square1.center, square2.center)
    # Sum of half-diagonals
    halfdiags = square1.half_diag + square2.half_diag
    res = ctc < halfdiags
    return res


class Squares(object):
    def __init__(self):
        self.squares = []

    def add_square(self):
        new_square = Square()
        if not self.squares:
            # Initial empty list/container - just add without any tests
            self.squares.append(new_square)
        else:
            while True:
            # Test that new_square overlaps with existing
                res = [test_overlap(square, new_square) for square in self.squares]
                if any(res):
                    # We have at least 1 case of overlap (1 True)
                    new_square = Square()
                else:
                    # Safe to add
                    self.squares.append(new_square)
                    break

    def plot_squares(self):
        for square in self.squares:
            (x0, y0), (x1, y1), (x2, y2), (x3, y3) = square.corners
            plt.plot([x0, x1, x2, x3, x0], [y0, y1, y2, y3, y0])

    Beispiel

    import itertools
%matplotlib inline
for _ in itertools.repeat(None, 10):
    # Add 10 squares; you could also just build this into the class
    sqs.add_square()
sqs.plot_squares()

    Wie generieren Quadrate (zufällig befindet sich, gleich große, zufällig gedreht), die sich nicht überschneiden?

    Installieren shapely

    Installieren Sie das Anaconda-Verteilung, wenn Sie nicht bereits. Dann verwenden Sie einfach conda-forge zu installieren, formschön. Von cmd run:

    conda config --add channels conda-forge
conda install shapely

    Eklatanten Mangel

    An einem bestimmten Punkt Ihres Containers der Quadrate gefüllt wird, bis und es gibt einen minimalen Raum gelassen, um neue Formen. Auch wenn genügend Raum vorhanden ist, die Funktion ist im Grunde trial-and-error, so wird lange dauern hohe Form zählt. Das passiert bei rund 20-25 Plätzen (im 1.0x1.0-Feld) im moment.

    InformationsquelleAutor Brad Solomon
  3. 1

    Benötigen Sie eine Funktion, um zu bestimmen, ob zwei Würfel schneiden.

    from math import cos, pi, sin
from random import random
from matplotlib.mlab import frange
from matplotlib.pyplot import plot, axis, show,axes

LEN = 0.1


def rotate(point, theta):
    x = point[0]
    y = point[1]
    x_ = x * cos(theta) + y * sin(theta)
    y_ = - x * sin(theta) + y * cos(theta)
    return x_, y_


class CUBE(object):
    def __init__(self, x, y, theta):
        self.corner = [(LEN / 2, LEN / 2),
                       (-LEN / 2, LEN / 2),
                       (-LEN / 2, -LEN / 2),
                       (LEN / 2, -LEN / 2)
                       ]
        self.theta = theta
        self.x = x
        self.y = y
        for i in range(4):
            self.corner[i] = rotate(self.corner[i], theta)
            self.corner[i] = (self.corner[i][0] + x,
                              self.corner[i][1] + y)


def is_include(cube, point):
    point = [point[0] - cube.x, point[1] - cube.y]
    point = rotate(point, -cube.theta)
    if (point[0] < -LEN / 2
            or point[0] > LEN / 2
            or point[1] < -LEN / 2
            or point[1] > LEN / 2
            ):
        return False
    else:
        return True


def is_intersect(cube1, cube2):
    if (any([is_include(cube1, point) for point in cube2.corner])
            or any([is_include(cube2, point) for point in cube1.corner])
            or is_include(cube1, (cube2.x, cube2.y))):
        return True
    else:
        return False


def plot_cube(cube,n):
    plot(
        [cube.corner[i][0] for i in [0, 1, 2, 3, 0]],
        [cube.corner[i][1] for i in [0, 1, 2, 3, 0]])
    ax = axes()
    ax.text(cube.x,cube.y,str(n))


def display(cubelist):  # connects the 4 corners on a plot
    for i,cube in enumerate(cubelist):
        plot_cube(cube,i)
    axis([0, 1, 0, 1])  # 1x1 grid
    show()


cubelist = []

for i in range(100):
    x0 = random()
    y0 = random()
    theta = random() * pi
    cube = CUBE(x0, y0, theta)
    if any(is_intersect(cube,cb) for cb in cubelist):
        continue
    else:

        cubelist.append(cube)

display(cubelist)
    InformationsquelleAutor Ian
Schreibe einen Kommentar