Brute Force Voronoi Algorithm

brute_force_voronoi.jl

using Colors
using LazySets
using Luxor

########################
# FUNCTION DEFINITIONS #
########################

"""
    make_drawing(width, height, img_path, bkg_color, origin_p)

Creates a Luxor `Drawing` object with given width and height dimensions.
Saves the image to whatever path of choosing.
Allows one to set the background color of an image.
Finally, one can set Luxor's reference origin point
"""
function make_drawing(width, height, img_path, bkg_color, origin_p)
    d = Drawing(width, height, img_path)
    background(bkg_color)
    origin(origin_p)
    return d
end

"""
Converts a coordinate pair in the traditional Cartesian coordinate system to a `Point` in Luxor's coordinate system.
"""
cart2luxor(p) = Point(p.x, -p.y)
cart2luxor(p::Array) = Point(p[1], -p[2])
cart2luxor(x, y) = Point(x, -y)

"""
Converts a Luxor `Point` to a coordinate pair in the traditional Cartesian coordinate system.
"""
luxor2cart(p::Point) = [p.x, -p.y]

"""

"""
distance(p1::Array, p2::Array) =
    sqrt((p2[1] - p1[1])^2 + (p2[2] - p1[2])^2)

#############
# CONSTANTS #
#############

width = 500
height = 500
path = "twitch.png"
color = RGBA(0.0, 0.0, 0.0)
op = Point(width / 2, height / 2)

seeds = [
    [rand((-width / 2):(width / 2)), rand((-height / 2):(height / 2))] for _ in 1:500
]
jump = 1

########
# MAIN #
########

my_draw = make_drawing(width, height, path, color, op)

println("Finding points and distances")

pts = []
distances = []
for x in (-width / 2):jump:(width / 2),
    y in (-height / 2):jump:(height / 2)

    push!(pts, [x, y])
    push!(distances, distance.(seeds, Ref([x, y])))

end

println("Finding what polygons belong where")

fields = [Vector{Vector{Float64}}(undef, 0) for _ in 1:length(seeds)]

for idx in 1:length(pts)
    min = findmin(distances[idx])[1]
    indices = findall(x -> x == min, distances[idx])
    for f in indices
        push!(fields[f], pts[idx])
    end
end

println("Finding convex hulls of polygons")

hulls = convex_hull.(fields) .|> x -> cart2luxor.(x)

println("Drawing polygons")

for i in 1:length(seeds)
    # color_start = [
    # colorant"#000000",
    # colorant"#141414",
    # colorant"#1B1B1B",
    # colorant"#FFFFFF",
    # colorant"#F3F3F3",
    # colorant"#E1E1E1",
    # ]
    color_start = [
    colorant"#F8B195",
    colorant"#F67280",
    colorant"#C06C84",
    colorant"#6C5B7B",
    colorant"#355C7D",
    ]
    sethue(rand(color_start))
    # setblend(myblend)
    poly(hulls[i], action = :fill, close = true)
end

println("Drawing polygon outlines")

setline(3)
sethue("black")
poly.(hulls, action = :stroke, close = true)

finish()

Creates images like this!

Hi Jacob! I like this image very much. Good job!

That lazy sets stuff looks tricky though - definitely more maths than I have... :)

You might be interested in seeing how you could do this using just Luxor. I uploaded a git here showing Delaunay and Voronoi integrations.

I love playing with all the different color schemes too!

A problem with my code is that it occasionally hangs. 🤣🤣🤣 I don't know why, perhaps some floating-point rounding.

Hey @cormullion !

This is AMAZING and super beautiful work!
Yours is way more computationally efficient than mine which is outstanding!
I also encountered the hanging - I agree, probably due to some sort of overflow or rounding.

The issue that I was running into with my initial, non-brute force algorithm, was I could not figure out how to bound voronoi diagrams over a specific area - such as a 500 x 500 square.
I had trouble getting the voronoi shapes at the edges of such a diagram.
It appears that using the Delaunay triangulation approach automatically solves this bounding problem.
Is that the case?

And yea, the LazySet stuff was used just for me to get the convex hull of a given polygon using the Jarvis March algorithm - I was lazy and didn't feel like implementing it!
I should though at some point for learning how to approach this better!

Thanks Jacob! I’m sorry my code left you hanging occasionally. 😀

After spending some time hunting bugs I decided to jettison the Jarvis and go for the Graham algorithm. Which might be a bit faster. So I’m hoping the code no longer hangs on Luxor#master now. 🤞🤞🤞