mb-geometry
Recreational Ruby tools for geometry. This ranges from simple functions like area calculation and line intersection, to Delaunay triangulation and Voronoi partitions. This is companion code to my educational video series about code and sound, and this code was featured in a video about Voronoi diagrams and Delaunay triangulations. I've also written more about this code on my blog.
XRES=960 YRES=540 bin/voronoi_transitions.rb /tmp/polygon.gif \
test_data/3gon.yml 30 60 \
test_data/square.yml 30 60 \
test_data/pentagon.json 30 60 \
test_data/zero.csv 30 0
You might also be interested in mb-sound, mb-math, and mb-util.
This code is reasonably well-tested, but I recommend using it for non-critical tasks like fun and offline graphics, and not for making important decisions or mission-critical data modeling.
Examples
Check out all of the scripts in bin/
; they usually have a header comment
describing what they do.
Video or GIF of Voronoi transitions
The bin/voronoi_transitions.rb
script will turn a sequence of Voronoi
diagrams into an animation with smooth transitions.
See the documentation for MB::Geometry::Generators.generate
in
lib/mb/geometry/generators.rb
for the syntax of the Voronoi diagram file
format (.json, .yml, or .csv), with examples in test_data/
. Also check out
the MB::Geometry::VoronoiAnimator
class.
Shuffling points
XRES=640 RANDOM_SEED=10 bin/voronoi_transitions.rb /tmp/shuffle.gif \
test_data/lines.json 0 \
__shuffle 60
60fps video transitions
XRES=960 YRES=540 bin/voronoi_transitions.rb /tmp/polygon.mp4 \
test_data/3gon.yml 30 15 \
test_data/square.yml 30 15 \
test_data/pentagon.json 30 15 \
test_data/zero.csv 30 0
Static SVG image from Voronoi diagram
From the shell:
bin/voronoi_to_svg.rb test_data/pentagon.json /tmp/pentagon.svg
From code:
require 'mb-geometry'
# The Hash must be inside an Array to prevent it being interpreted as keyword args
# Rotation is in degrees
v = MB::Geometry::Voronoi.new([{ generator: :polygon, sides: 5, rotate: 30 }]) ; nil
v.save_svg('/tmp/pentagon_from_code.svg')
# You can save the Delaunay triangulation instead:
v.save_delaunay_svg('/tmp/pentagon_delaunay.svg')
Voronoi diagram from image
You can generate a JSON points file for a Voronoi diagram from a PNG (or other) image, then generate a pixel-art SVG from that (16x16 or smaller images recommended):
bin/png_to_voronoi.rb image.png image.json
bin/voronoi_to_svg.rb image.json image.svg
Input | Output |
---|---|
Voronoi points file format
The bin/triangulate.rb
, bin/voronoi_to_svg.rb
, and
bin/voronoi_transitions.rb
tools all use a common file format to describe a
Voronoi partition. Any JSON, YAML, or CSV file that parses to an Array of X
and Y coordinates is supported. There is also an abbreviated syntax for
generating polygons or random points. The file format is documented below in
the Voronoi points file format section. See
MB::Geometry::Generators#generate_from_file for more info.
Raw array of points
JSON:
[
[-1, 1],
[1.5, -0.5],
[-1, 0],
]
YML:
- [-1, 1]
- - 1.5
- -0.5
- [-1, 0]
CSV:
-1,1
1.5,-0.5
-1,0
Raw array of point hashes
Point hashes may include a name and a color for a point.
JSON:
[
{ "x": -1, "y": 1, "name": "A", "color": [0.1, 0.2, 0.5, 0.9] },
{ "x": 1.5, "y": -0.5, "name": "B", "color": [0.6, 0.2, 0.5, 0.9] },
{ "x": -1, "y": 0, "name": "C", "color": [0.3, 0.8, 0.4, 0.9] }
]
bin/voronoi_to_svg.rb /tmp/hashes.json /tmp/hashes.svg
Generators
See the source code and files under test_data/
for details. Generators
include :random
, :segment
, :polygon
, :grid
, :points
, and :multi
.
Random points
Colors and names may be specified in separate Arrays. Colors will be reused in a loop if there are more points than colors.
The anneal
option controls how many times points are moved toward their
cell's center. The bounding_box
option controls the maximum space in which
the points may expand. See MB::Geometry::Voronoi#anneal
.
YML:
generator: :random
count: 10
seed: 3
anneal: 1
bounding_box: [-3, -2, 3, 2]
colors:
- [0.1, 0.2, 0.5, 0.9]
- [0.5, 0.3, 0.2, 0.9]
names:
- "P0"
- "P1"
- "P2"
- "P3"
- "P4"
- "P5"
- "P6"
- "P7"
- "P8"
- "P9"
LABELS=1 bin/voronoi_to_svg.rb /tmp/random_points.yml /tmp/random_points.svg
Multiple generators combined
YML:
generator: :multi
generators:
# Line segment generator
- generator: :segment
count: 5
from: [-3, -0.1]
to: [-2, -1]
# Polygon generator
- generator: :polygon
sides: 7
radius: 0.5
rotate: 45
clockwise: true
# Random points generator
- generator: :random
count: 10
seed: 3
xmin: 1.5
xmax: 3.25
ymin: -1.5
ymax: 1.5
anneal: 1
# Another segment
- generator: :segment
count: 5
from: [-3, 0.1]
to: [-2, 1]
Delaunay triangulation
The Voronoi diagrams generated by this code are all derived from Delaunay
triangulation. There are three backends for Delaunay triangulation that can be switched by
setting the DELAUNAY_ENGINE
and DELAUNAY_DEBUG
environment variables.
-
DELAUNAY_ENGINE=rubyvor
-- Uses the RubyVor Gem's C extension for Delaunay triangulation. This is very fast, and the default. -
DELAUNAY_ENGINE=delaunay
-- My pure Ruby implementation of Lee and Schacter's 1980 divide and conquer algorithm. SeeREADME-Delaunay.md
andlib/mb/geometry/delaunay.rb
for more info. This is reasonably fast. -
DELAUNAY_ENGINE=delaunay_debug DELAUNAY_DEBUG=1
-- The same pure Ruby implementation, but with lots of debugging output and each step of the algorithm dumped to a .json file in /tmp (or the directory specified by theJSON_DIR
environment variable, if set). This is slow.
Pure Ruby algorithm
The triangulate.rb
command prints each input point's neighbors and the final
list of triangles in Ruby Hash syntax.
DELAUNAY_ENGINE=delaunay bin/triangulate.rb test_data/square.yml
Rubyvor gem algorithm
DELAUNAY_ENGINE=rubyvor bin/triangulate.rb test_data/square.yml
Simple geometric functions
See MB::Geometry
.
Area of a polygon
MB::Geometry.polygon_area([[0, 0], [1, 0], [1, 1], [0, 1]])
# => 1.0
Installation and usage
This project contains some useful programs of its own, or you can use it as a Gem (with Git source) in your own projects.
Standalone usage and development
First, install a Ruby version manager like RVM. Using the system's Ruby is not recommended -- that is only for applications that come with the system. You should follow the instructions from https://rvm.io, but here are the basics:
gpg2 --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3 7D2BAF1CF37B13E2069D6956105BD0E739499BDB
\curl -sSL https://get.rvm.io | bash -s stable
Next, install Ruby. RVM binary rubies are still broken on Ubuntu 20.04.x, so
use the --disable-binary
option if you are running Ubuntu 20.04.x.
rvm install --disable-binary 2.7.3
You can tell RVM to isolate all your projects and switch Ruby versions
automatically by creating .ruby-version
and .ruby-gemset
files (already
present in this project):
cd mb-geometry
cat .ruby-gemset
cat .ruby-version
Now install dependencies:
bundle install
You will also want ffmpeg if you want to make GIFs or videos:
# Debian/Ubuntu
sudo apt-get install ffmpeg
# macOS (might not be exactly right, but this is the gist)
brew install ffmpeg
Using the project as a Gem
To use mb-geometry in your own Ruby projects, add this Git repo to your
Gemfile
(plus the Git repos of other pre-release gems it depends on):
# your-project/Gemfile
gem 'mb-geometry', git: 'https://github.com/mike-bourgeous/mb-geometry.git'
gem 'mb-math', git: 'https://github.com/mike-bourgeous/mb-math.git'
gem 'mb-util', git: 'https://github.com/mike-bourgeous/mb-util.git'
Testing
Run rspec
, or play with the included scripts under bin/
.
Contributing
Pull requests welcome, though development is focused specifically on the needs of my video series.
License
This project is released under a 2-clause BSD license. See the LICENSE file.
See also
Dependencies
- RubyVor; unfortunately the homepage link is no longer valid, but the RubyVor source code is still available.
References
See README-Delaunay.md
for Delaunay tringulation references.