Giter Club home page Giter Club logo

discretevoronoi.jl's Introduction

DiscreteVoronoi

A package for computing discrete approximations of Voronoi diagrams. All Voronoi diagram calculating functions are in-place.

Currently, to use this package you need to declare your sites as a Vector{SVector{2,Int}} and your grid as a Matrix{SVector{2,Int}} and hence there is a strong dependency on StaticArrays.

using DiscreteVoronoi
using StaticArrays

# Testing
n = 50
p = 10
grid = zeros(SVector{2,Int}, n, n)
sites = [SVector{2,Int}(rand(1:n, 2)) for _ in 1:p]
redac_voronoi!(grid, sites)

There are currently three ways of computing discrete Voronoi diagrams exported, they are all completely allocation free and called in the same way:

  • *_voronoi!(grid::Matrix{SVector{2,Int}}, sites::Vector{SVector{2,Int}} is the generic function call for all of the following functions,
  • naive_voronoi! simply compares all cells to all sites and chooses the closest
  • jfa_voronoi! uses the jump flooding algorithm, which is explained in more detail here
  • dac_voronoi! employs a divide-and-conquer method first detailed here.
  • redac_voronoi! (reduce-divide-and-conquer) additionally runs a site elimination algorithm before each recursive step. This elimination algorithm aims to reduce the amount of unnecessary work performed by the algorithm in subsequent recursions by removing seeds that are far away from the corners.

Which algorithm you should use for the fastest execution time depends somewhat on the task at hand. The best thing to do is to try all above for your usecase and decide from benchmarks. As a rule of thumb, the larger the grid is the better the divide-and-conquer methods will be in comparison. Particularly if the number of sites scales with the size of the grid (n^2) faster than log(n) (natural log), then redac_voronoi! will be much faster than dac_voronoi!.

Additionally, the package exports some helper functions for analysing Voronoi diagrams and writing your own algorithms:

  • find_closest_site and find_closest_site! finds the closest site to a specified cell in the Lp sense, the latter writing it directly to the grid if it hasn't already been calculated.
  • get_corners and get_quadrants take the top-left (TL) and bottom-right (BR) corners of a rectangle and return the TL and BR corners, and non-overlapping quadrants (calculated by integer division) respectively.
  • label_voronoi_grid takes a grid of SVector{2, Int} and labels each unique value with an integer in a new grid of the same size so it can be visualised.
  • voronoi_equality can be used to test equality of resulting Voronoi diagrams taking into account that some sites may be the same distance from certain cells and so there are multiple valid/correct diagrams that could be produced.

Work in progress:

  • Implementing a hybrid version of redac_voronoi! and dac_voronoi! that switches to naive_voronoi! once a certain size is reached.
  • Currently, I have not implemented multithreaded (or GPU in the case of JFA) versions of these algorithms on the main branch, but the legacy branch contains versions of the algorithms that do have this capability.

Contributions:

discretevoronoi.jl's People

Contributors

goerch avatar jacobusmmsmit avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.