Diagramas de Voronoi¶

Exemplo básico de diagrama. Usando a biblioteca scipy.spatial.

Primeiro passo é a geração de pontos para criar o diagrama a partir destes pontos.

Baseado nos trabalhos de

https://readmedium.com/replicating-minecraft-world-generation-in-python-1b491bc9b9a4 https://github.com/BilHim/minecraft-world-generation

In [2]:

import numpy as np
from scipy.spatial import Voronoi, voronoi_plot_2d
import matplotlib.pyplot as plt

rng = np.random.default_rng(12345) # forma mais moderna de fazer random e seed 12345
points = 256*rng.random((100,2))   # retorna um array de 100 pares de valores. tamanho dos pontos vai até 256
# print(points)

plt.figure(figsize=(9.5, 5.5))
plt.plot(points[:, 0], points[:, 1], 'bo')
# plt.axis('off')
plt.show()

import numpy as np from scipy.spatial import Voronoi, voronoi_plot_2d import matplotlib.pyplot as plt rng = np.random.default_rng(12345) # forma mais moderna de fazer random e seed 12345 points = 256*rng.random((100,2)) # retorna um array de 100 pares de valores. tamanho dos pontos vai até 256 # print(points) plt.figure(figsize=(9.5, 5.5)) plt.plot(points[:, 0], points[:, 1], 'bo') # plt.axis('off') plt.show()

In [9]:

# Para criar o diagrama e plotar
vor = Voronoi(points)
fig = voronoi_plot_2d(vor)
fig.set_size_inches(9.5, 5.5)
# plt.axis('off')
plt.show()

# Para criar o diagrama e plotar vor = Voronoi(points) fig = voronoi_plot_2d(vor) fig.set_size_inches(9.5, 5.5) # plt.axis('off') plt.show()

In [10]:

# 2. Create the Voronoi diagram
vor = Voronoi(points)

# 3. Plot the Voronoi diagram
fig = voronoi_plot_2d(
    vor
    , show_vertices=False
    , show_points=False
    # , line_colors='orange'
    # , line_width=2
    # , point_size=5
)

pontos = vor.points

# 4. Add labels or customize the plot (optional)
# plt.plot(pontos[:, 0], pontos[:, 1], 'go')
plt.title('Voronoi Diagram Example')
# plt.xlabel('X-axis')
# plt.ylabel('Y-axis')
fig.set_size_inches(9.5, 5.5)
# plt.axis('off')
plt.show()

# 2. Create the Voronoi diagram vor = Voronoi(points) # 3. Plot the Voronoi diagram fig = voronoi_plot_2d( vor , show_vertices=False , show_points=False # , line_colors='orange' # , line_width=2 # , point_size=5 ) pontos = vor.points # 4. Add labels or customize the plot (optional) # plt.plot(pontos[:, 0], pontos[:, 1], 'go') plt.title('Voronoi Diagram Example') # plt.xlabel('X-axis') # plt.ylabel('Y-axis') fig.set_size_inches(9.5, 5.5) # plt.axis('off') plt.show()

In [11]:

# Para identificar partes do diagrama com os pontos de entrada, vértices e regiões:

# Coordinates of input points.
pontos = vor.points

# Coordinates of the Voronoi vertices.
vertices = vor.vertices

regioes = vor.regions
print(f"regiões:{regioes}")

# # The ridges are perpendicular between lines drawn between the following input points:
# vor.ridge_points
ridge = vor.ridge_points

# fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.5,5.5))

# ax1.plot(pontos[:, 0], pontos[:, 1], 'go')
# ax2.plot(vertices[:, 0], vertices[:, 1], 'bo')
# # plt.plot(ridge[:, 0], ridge[:, 1], 'ro')
# # plt.plot([item[:,0] for item in regioes[:, 0]], [item[:,1] for item in regioes[:, 1]])
# plt.show

# Para identificar partes do diagrama com os pontos de entrada, vértices e regiões: # Coordinates of input points. pontos = vor.points # Coordinates of the Voronoi vertices. vertices = vor.vertices regioes = vor.regions print(f"regiões:{regioes}") # # The ridges are perpendicular between lines drawn between the following input points: # vor.ridge_points ridge = vor.ridge_points # fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(9.5,5.5)) # ax1.plot(pontos[:, 0], pontos[:, 1], 'go') # ax2.plot(vertices[:, 0], vertices[:, 1], 'bo') # # plt.plot(ridge[:, 0], ridge[:, 1], 'ro') # # plt.plot([item[:,0] for item in regioes[:, 0]], [item[:,1] for item in regioes[:, 1]]) # plt.show

regiões:[[5, -1, 4], [], [13, -1, 1, 12], [19, 16, 15, 17, 18], [19, 6, 7, 16], [21, 0, -1, 20], [22, 15, 16, 7, 0, 21], [28, -1, 13, 14, 27], [41, 32, 39], [46, 4, 5, 44], [49, 22, 15, 17, 48], [60, 23, -1, 8, 10, 59], [65, 61, 62, 63, 64], [62, 51, 47, 11, 26, 61], [63, 50, 56, 54, 51, 62], [70, 68, 67, 69], [69, 40, 38, 37, 67], [68, 31, 12, 1, 36, 37, 67], [70, 30, 33, 32, 39, 40, 69], [76, 74, 73, 75], [76, 31, 12, 13, 14, 34, 74], [76, 31, 68, 70, 30, 75], [81, 78, 77, 79, 80], [78, 35, 73, 74, 34, 77], [79, 27, 14, 34, 77], [83, 42, 25, 58, 57, 82], [88, 84, 86, 85, 87], [86, 36, 37, 38, 84], [87, 9, 2, 85], [86, 36, 1, -1, 2, 85], [90, 54, 56, 55, 53, 52, 89], [94, 46, 44, 45, 91], [93, 6, 19, 18, 3, 11, 47, 92], [94, 46, 4, -1, 0, 7, 6, 93], [96, 57, 58, 95], [97, 82, 57, 96], [99, 60, 23, 98], [106, 66, 3, 11, 26, 29, 105], [111, 109, 108, 107, 110], [111, 29, 105, 104, 109], [111, 29, 26, 61, 65, 110], [114, 81, 78, 35, 112], [113, 72, 33, 30, 75, 73, 35, 112], [121, 117, 116, 118, 119, 120], [118, 64, 65, 110, 107, 116], [119, 50, 63, 64, 118], [120, 43, 42, 25, 55, 56, 50, 119], [121, 72, 33, 32, 41, 43, 120], [128, 123, 122, 124, 125, 126, 127], [123, 83, 42, 43, 41, 39, 40, 38, 84, 88, 122], [124, 9, 87, 88, 122], [128, 97, 82, 83, 123], [125, 8, -1, 2, 9, 124], [126, 10, 8, 125], [130, 89, 52, 24, 129], [133, 130, 129, 132], [137, 135, 134, 136], [136, 131, 133, 130, 89, 90, 134], [135, 92, 47, 51, 54, 90, 134], [137, 91, 94, 93, 92, 135], [139, -1, 28, 138], [142, 66, 3, 18, 17, 48, 141], [147, 144, 143, 145, 146], [144, 103, 101, 143], [146, 49, 22, 21, 20, 145], [147, 140, 141, 48, 49, 146], [149, 142, 66, 106, 148], [151, 104, 109, 108, 115, 114, 81, 80, 71, 150], [152, 148, 106, 105, 104, 151], [155, 153, 154], [155, 113, 72, 121, 117, 153], [154, 115, 108, 107, 116, 117, 153], [155, 113, 112, 114, 115, 154], [159, 157, 156, 158], [157, 131, 136, 137, 91, 45, 156], [159, 132, 133, 131, 157], [163, 59, 60, 99, 160], [164, 127, 128, 97, 96, 95, 162], [164, 127, 126, 10, 59, 163], [166, 161, 162, 95, 58, 25, 55, 53, 165], [168, 160, 99, 98, 167], [172, -1, 23, 98, 167], [169, 161, 162, 164, 163, 160, 168], [171, 24, 52, 53, 165, 170], [173, 158, 159, 132, 129, 24, 171], [173, 158, 156, 45, 44, 5, -1, 172], [177, 175, 174, 176], [176, 101, 103, 102, 100, 174], [175, 138, 28, 27, 79, 80, 71, 100, 174], [177, 139, 138, 175], [177, 139, -1, 20, 145, 143, 101, 176], [182, 180, 178, 179, 181], [179, 140, 147, 144, 103, 102, 178], [180, 150, 71, 100, 102, 178], [181, 149, 142, 141, 140, 179], [182, 152, 151, 150, 180], [182, 152, 148, 149, 181], [185, 183, 184], [185, 170, 165, 166, 183], [184, 169, 161, 166, 183], [185, 170, 171, 173, 172, 167, 168, 169, 184]]

Usando patch pra exibir¶

In [13]:

import matplotlib
from matplotlib.collections import PatchCollection
from matplotlib.patches import Polygon
import matplotlib.pyplot as plt

# verifica se algum dos vértices ultrapassa o tamanho do grid criado.
# 256 é o mesmo número usado no random
def checkVertices(vertices):
    for couple in vertices:
        if (any(x < 0 or x > 256 for x in couple)):
            return False
    return True

fig, ax = plt.subplots(1)

N = 3
nfloors = np.random.rand(N) # some random data

patches = []

cmap = plt.get_cmap('terrain')
colors = cmap(nfloors) # convert nfloors to colors that we can use later

patches = []
for region in regioes:
    if (region != []):
        vertices_ = vertices[region]
        if (checkVertices(vertices_)):
            polygon = Polygon(vertices_, closed=True)
            patches.append(polygon)

collection = PatchCollection(patches, cmap=matplotlib.cm.jet)

ax.add_collection(collection)

collection.set_color(colors)
collection.set_edgecolor('k')
collection.set_clim([3, 50])

ax.autoscale_view()
fig.set_size_inches(9.5, 5.5)
#ax.set_facecolor('xkcd:sea blue')
plt.axis('off')
plt.show()
# fig.savefig("map.png", dpi=fig.dpi, transparent=True)

import matplotlib from matplotlib.collections import PatchCollection from matplotlib.patches import Polygon import matplotlib.pyplot as plt # verifica se algum dos vértices ultrapassa o tamanho do grid criado. # 256 é o mesmo número usado no random def checkVertices(vertices): for couple in vertices: if (any(x < 0 or x > 256 for x in couple)): return False return True fig, ax = plt.subplots(1) N = 3 nfloors = np.random.rand(N) # some random data patches = [] cmap = plt.get_cmap('terrain') colors = cmap(nfloors) # convert nfloors to colors that we can use later patches = [] for region in regioes: if (region != []): vertices_ = vertices[region] if (checkVertices(vertices_)): polygon = Polygon(vertices_, closed=True) patches.append(polygon) collection = PatchCollection(patches, cmap=matplotlib.cm.jet) ax.add_collection(collection) collection.set_color(colors) collection.set_edgecolor('k') collection.set_clim([3, 50]) ax.autoscale_view() fig.set_size_inches(9.5, 5.5) #ax.set_facecolor('xkcd:sea blue') plt.axis('off') plt.show() # fig.savefig("map.png", dpi=fig.dpi, transparent=True)

Delaunay tessellation¶

Os pontos em vermelho são os pontos de entrada.

Os pontos azuis e linhas cinza são os vértices e as linhas do diagrama e Voronoi.

E as linhas verdes são a triangulação de Delaunay.

In [8]:

import numpy as np
from scipy.spatial import Delaunay
import matplotlib.pyplot as plt

# Compute the Delaunay triangulation
tri = Delaunay(points)

fig = voronoi_plot_2d(
    vor
    , show_vertices=True
    , show_points=True
    , line_colors='gray'
    , line_width=2
    , point_size=5, line_alpha=0.5
)

# Visualize the triangulation
plt.triplot(points[:, 0], points[:, 1], tri.simplices)
plt.plot(
    points[:, 0]
    , points[:, 1]
    , marker='o'
    , linestyle='None'
    , color='red'
    , markersize=10
    , alpha=0.7     
)


plt.plot(vertices[:, 0], vertices[:, 1], 'bo')

plt.title("Delaunay Triangulation")
# plt.xlabel("X-coordinate")
# plt.ylabel("Y-coordinate")
plt.show()

# Accessing triangle information
# print("Simplices (triangles):")
# print(tri.simplices)

import numpy as np from scipy.spatial import Delaunay import matplotlib.pyplot as plt # Compute the Delaunay triangulation tri = Delaunay(points) fig = voronoi_plot_2d( vor , show_vertices=True , show_points=True , line_colors='gray' , line_width=2 , point_size=5, line_alpha=0.5 ) # Visualize the triangulation plt.triplot(points[:, 0], points[:, 1], tri.simplices) plt.plot( points[:, 0] , points[:, 1] , marker='o' , linestyle='None' , color='red' , markersize=10 , alpha=0.7 ) plt.plot(vertices[:, 0], vertices[:, 1], 'bo') plt.title("Delaunay Triangulation") # plt.xlabel("X-coordinate") # plt.ylabel("Y-coordinate") plt.show() # Accessing triangle information # print("Simplices (triangles):") # print(tri.simplices)

Referências:

• Bilal Himite - Replicating Minecraft World Generation in Python
  • https://readmedium.com/replicating-minecraft-world-generation-in-python-1b491bc9b9a4
  • https://github.com/BilHim/minecraft-world-generation

Documentação:

Opções da função voronoi_plot_2d:

    points ndarray of double, shape (npoints, ndim)
        Coordinates of input points.

    verticesndarray of double, shape (nvertices, ndim)
        Coordinates of the Voronoi vertices.

    ridge_pointsndarray of ints, shape (nridges, 2)
        Indices of the points between which each Voronoi ridge lies.

    ridge_verticeslist of list of ints, shape (nridges, *)
        Indices of the Voronoi vertices forming each Voronoi ridge.

    regionslist of list of ints, shape (nregions, *)
        Indices of the Voronoi vertices forming each Voronoi region. -1 indicates vertex outside the Voronoi diagram. When qhull option “Qz” was specified, an empty sublist represents the Voronoi region for a point at infinity that was added internally.

    point_regionarray of ints, shape (npoints)
        Index of the Voronoi region for each input point. If qhull option “Qc” was not specified, the list will contain -1 for points that are not associated with a Voronoi region. If qhull option “Qz” was specified, there will be one less element than the number of regions because an extra point at infinity is added internally to facilitate computation.

Segunda Parte¶

In [ ]:

# Baseado no trabalho de:
# https://www.martinmcbride.org/post/2021/voronoi-diagrams-with-scipy/
from generativepy.drawing import make_image, setup
from generativepy.geometry import Circle, Polygon
from generativepy.color import Color
from scipy.spatial import Voronoi
import random

# Baseado no trabalho de: # https://www.martinmcbride.org/post/2021/voronoi-diagrams-with-scipy/ from generativepy.drawing import make_image, setup from generativepy.geometry import Circle, Polygon from generativepy.color import Color from scipy.spatial import Voronoi import random

In [ ]:

SIZE = 400
POINTS = 20

# Create a list of random points
random.seed(40)
points = [[random.randrange(SIZE), random.randrange(SIZE)]
          for i in range(POINTS)]
points.append((-SIZE*3, -SIZE*3))
points.append((-SIZE*3, SIZE*4))
points.append((SIZE*4, -SIZE*3))
points.append((SIZE*4, SIZE*4))


def draw(ctx, pixel_width, pixel_height, frame_no, frame_count):
    setup(ctx, pixel_width, pixel_height, background=Color(1))
    voronoi = Voronoi(points)
    voronoi_vertices = voronoi.vertices

    for region in voronoi.regions:
       if -1 not in region:
           polygon = [voronoi_vertices[p] for p in region]
           Polygon(ctx).of_points(polygon).stroke(line_width=2)


make_image("voronoi-lines.png", draw, SIZE, SIZE)

SIZE = 400 POINTS = 20 # Create a list of random points random.seed(40) points = [[random.randrange(SIZE), random.randrange(SIZE)] for i in range(POINTS)] points.append((-SIZE*3, -SIZE*3)) points.append((-SIZE*3, SIZE*4)) points.append((SIZE*4, -SIZE*3)) points.append((SIZE*4, SIZE*4)) def draw(ctx, pixel_width, pixel_height, frame_no, frame_count): setup(ctx, pixel_width, pixel_height, background=Color(1)) voronoi = Voronoi(points) voronoi_vertices = voronoi.vertices for region in voronoi.regions: if -1 not in region: polygon = [voronoi_vertices[p] for p in region] Polygon(ctx).of_points(polygon).stroke(line_width=2) make_image("voronoi-lines.png", draw, SIZE, SIZE)