Come generare casualmente trova piazze (di uguali dimensioni) su un 1×1 griglia casuale di angolo di rotazione senza che si intersecano l’un l’altro?

Ho lavorato sulla generazione di un layer in modo casuale ruotato e posizionato piazze su una griglia 1×1. Sono stato in grado di generare un’unica piazza che è posizionati in modo casuale e ruotato sulla griglia di partenza, ma non sono sicuro di come migliorare il codice per generare più casuale piazze che non si intersecano tra di loro. Corrente codice che vedete sotto:

Esempio della mia Uno studio Randomizzato Piazza

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()

Non ho un CS di sfondo (io sono di ingegneria ambientale maggiore) e io sono molto inesperto con la codifica. Per favore datemi tutte le raccomandazioni che si possono avere per me per cercare di affrontare questo problema!

È possibile considerare una circolare enveloppe intorno alla piazza ? In questo caso, è possibile salvare il centro di ogni piazze e verificare che la distanza tra il centro è > 2*z.
Utilizzare il rifiuto di campionamento per generare più piazze: if(current square overlaps) reject(); else add_square_to_list();
A quanto i quadrati devono essere? Se si può fare a meno di ~70% (1/√2) la dimensione della griglia, che sarà mai sovrapporsi.

OriginaleL’autore Deputy McMunch | 2017-09-06

3 Replies
  1. 2

    Di matematica

    1. Algebra

    2. Geometria Piana

    • Un piano si compone di un infinito numero di punti: andiamo a vedere un punto mediante le sue coordinate che può essere definito come:
      • ascissa o coordinata orizzontale o (semplicemente) x
      • ordinata o coordinata verticale o (semplicemente) y
    • I punti nel piano sono distribuite su 2 dimensioni
    • In aereo, ogni punto può essere identificato univocamente dal suo x e y
    • Alcuni dei punti del piano potrebbe avere alcune caratteristiche in comune: ad esempio, un sacco di punti che si trovano su una linea retta… un punto che si trova su una linea retta che soddisfa la linea retta equazione (che è un’espressione generalmente definito come ${funzione (dal paragrafo precedente) risultato} = ${valore}).
    • Così, in breve: per un punto P0(x0, y0), se y0 == f(x0), il punto di è trova che linea retta (e più: a seconda y0 essere maggiore/inferiore di f(x0), P0 si trova sopra/sotto la retta nel xOy piano)
      • ! Nota Importante !: tutto discusso qui si applica a una serie di funzioni (non voglio dire tutti), ma sto limitando a funzioni lineari, per amor di chiarezza
    • Una linea retta è determinata da 2 distinti punti: ad esempio (P0(x0, y0), P1(x1, y1)): l’equazione retta sarebbe y = a * x + b (nel nostro esempio: y = (y0 - y1) /(x0 - x1) * x + (y0 - x0 * ((y0 -y1) /(x0 - x1)))); !! Naturalmente, che vale la pena di menzionare la “verticale” (parallelo a Oy) linea di !! non è una funzione !!.
    • Esempio: avendo 2 distinti parallelo (non Bolyai 🙂 ) linee: f0(x) = a * x + b0 e f1(x) = a * x + b1 (a è la stessa per entrambe le linee – questa è la condizione per essere parallelo) e un punto esterno P0(x0, y0) (che, ovviamente, non appartiene a nessuna delle linee). Come determinare se P0 è tra le 2 linee? Bene, il punto deve essere al di sopra (basso) uno e sotto l’altro (quello più alto). Tradotto in matematica (considerando f0 di essere il più in basso):

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

      Dalle precedenti osservazioni (e ci può essere più di saggezza, questa è la condizione che il punto deve soddisfare: (y0 - f0(x0)) * (y0 - f1(x0)) < 0

    • Di andare avanti: un quadrato da 2 gruppi di linee parallele (lati); se un punto è tra ciascuna delle linee di coppia, quindi il punto è in piazza.

    Codice:

    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):
            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__":
        main()

    Note:

    • Non ho lavorato con matplotlib prima (in realtà, ho pip installed è per questo compito)
    • Ho usato VirtualEnved Python 3.5 su Vincere
    • Osservazioni di carattere generale:
      • Un punto è rappresentato da una tupla che rappresentano le coordinate: (x, y)
      • Una piazza è una tupla composta da 4 punti (p0, p1, p2, p3)
    • get_func_deg1:
      • Restituisce la funzione che descrive la riga che contiene i 2 punti passati come argomenti
      • Se i 2 punti si trovano su una linea che è parallela a Oy (non c’è la funzione “normale” per descriverla), semplicemente restituire None
    • is_point_in_square:
      • Determina se un punto è all’interno di un quadrato
      • Utilizza la logica spiegato sopra, ad eccezione di
      • Per il caso speciale in cui i bordi quadrati sono paralleli Bue e Oy quando si utilizza alcune semplici operazioni aritmetiche
    • squares_overlap:
      • Determina se 2 piazze sovrapposizione (sono sicuro che ci sono più veloci “algoritmi”)
      • Verifica se i 1san piazza angoli sono all’interno delle 2nd
      • In un altro modo: verifica se i 2nd piazza angoli sono all’interno del 1san
      • Dato 2 controlli non sono sufficienti (immaginate un regolare [Wikipedia]: Ottagono e unificante dei suoi vertici ogni 2nd: ci saranno 2 piazze di non avere neppure i suoi angoli, ma condividere la loro “centrale” aree), controllare anche che una piazza del centro è all’interno di uno
    • generate_random_point:
      • Genera un punto in una determinata casella di delimitazione
      • safety_margin specifica (minimo) distanza generato punto dovrebbe essere lontano da qualsiasi del riquadro i lati, in modo che ogni quadrato che avrà come punto di un angolo, sarebbe adatta completamente nel riquadro
    • generate_random_angle:
      • Genera casualmente un angolo compreso tra 0 e (π /2)
    • generate_random_square:
      • Genera un punto casuale, casuale angolo, e costruisce un quadrato a partire da lì, utilizzando la specifica lato
      • squares_to_avoid è riportato un elenco delle piazze. Dopo la piazza è generato è controllato contro ogni quadrato da quella lista. Se il 2 piazze si sovrappongono, la piazza è rigenerato
    • square_to_plot:
      • Converte una piazza (da una tupla di punti) per matplotlib formato (2 tuple composto di xs e ys con 1san elemento duplicato come l’ultimo)
    • main:
      • La funzione principale
    • __generation_monitor: *
      • Funzione interna usato per definire
    • Per modificare il numero di piazze, modificare MAX_SQUARES

    Uscita:

    Come generare casualmente trova piazze (di uguali dimensioni) su un 1x1 griglia casuale di angolo di rotazione senza che si intersecano l'un l'altro?

    (py35x64_test) c:\Work\Dev\StackOverflow\q46081491>python a.py
    STATS:
        Squares: 30
        Allow  overlapping: False
        Generated values: 1135

    *: Poche parole sulle piazze generazione

    • Come si è visto in uscita, per 30 visualizzato piazze, 1135 sono stati generati (in questo periodo). Che è perché essi sono stati sovrapposti
    • Se la modifica da main allow_overlapping = True, valori Generati in uscita corrisponde al numero di piazze (MAX_SQUARES)
    • In caso di aumento della MAX_SQUARES di valori diciamo superiore a 50, il numero di valori generati aumenterà in modo esponenziale (così il tempo necessario per generare loro), e la possibilità che il programma entra in un ciclo infinito (perché non sarà in grado di generare una piazza che non somigli a un altro) si svilupperà

    OriginaleL’autore CristiFati

  2. 1

    Bene, ecco quello che ho creato con un piccolo aiuto da shapely pacchetto. Installazione di un aiuto a fondo. Il risultato finale:

    Come generare casualmente trova piazze (di uguali dimensioni) su un 1x1 griglia casuale di angolo di rotazione senza che si intersecano l'un l'altro?
    Come generare casualmente trova piazze (di uguali dimensioni) su un 1x1 griglia casuale di angolo di rotazione senza che si intersecano l'un l'altro?

    Codice di procedura dettagliata

    • distance è una funzione di supporto utilizzando il Point classe da formosa per calcolare la distanza tra le due coordinate. Solo una funzione di supporto per più tardi.
    • Square istanze di un nuovo poligono. Ha 4 angoli, ogni (x,y) coppia di coordinate per il suo centro, e un valore scalare pari alla metà della distanza della sua diagonale.
    • test_overlap è abbastanza auto esplicativo, dal titolo. Ma logicamente ciò che fa è questo: trovare la distanza da centro a centro tra le due forme. Poi trovare la somma di mezza diagonale di ogni forma. Se il centro-a-distanza dal centro è maggiore della somma, le piazze non si sovrappongono.
    • Squares inizia con un contenitore vuoto (lista vuota) e tenta di aggiungere piazze. Ma per ogni nuova aggiunta, prime prove, che non vi è alcuna sovrapposizione con le attuali piazze.

    Codice

    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])  

    Esempio

    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()

    Come generare casualmente trova piazze (di uguali dimensioni) su un 1x1 griglia casuale di angolo di rotazione senza che si intersecano l'un l'altro?

    Installazione shapely

    Installazione Anaconda, distribuzione, se non già. Poi basta usare conda-forge per installare formosa. Da cmd eseguire:

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

    Palese lacuna

    A un certo punto, il vostro contenitore di piazze ottiene riempita e non c’è il minimo spazio a sinistra per aggiungere nuove forme. Anche se c’è spazio disponibile, la funzione è sostanzialmente di prova-e-errore, quindi ci vorrà molto tempo ad alta forma conta. Che accade intorno a 20-25 piazze (1).0x1.0 box) al momento.

    OriginaleL’autore Brad Solomon

  3. 1

    Avete bisogno di una funzione per determinare se due cubi si intersecano.

    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)

    OriginaleL’autore Ian

Lascia un commento