Coding Challenge 181: Weighted Voronoi Stippling

TL;DR

Learn how to use the concept of Voronoi diagrams and Lloyd's relaxation algorithm to create stunning stippled images.

Transcript

This is actually a true story. I slept with this paper-- Weighted Voronoi Stippling under my pillow with the hope that it would absorb into my mind somehow. [MUSIC PLAYING] It's time for another coding challenge. I am very excited about this one. It is a high degree of difficulty, but if I've made it succeed, you know already. I don't know, but you... Read More

Key Insights

• 🔺 Voronoi diagrams divide a plane into regions based on proximity to seed points, while Delaunay triangulation constructs triangles with circumcircles related to the Voronoi diagram.
• 😥 Lloyd's relaxation algorithm optimizes the distribution of points in a Voronoi diagram by moving them towards the centroids of the polygons, resulting in evenly spaced points.
• 😥 Weighted Voronoi stippling involves assigning weights to seed points based on pixel intensities in an image, allowing for the creation of stippled images that reflect the underlying patterns.
• 📚 Libraries like d3.js and p5.js can be used together to implement these algorithms and create beautiful stippled images.
• 🫥 Experimentation with factors such as dot size, colors, and applying the technique to videos can lead to further creative possibilities.
• 👨‍💻 Cleaning up and optimizing the code is recommended for better performance and understanding.

Questions & Answers

Q: What is a Voronoi diagram and how is it related to Delaunay triangulation?

A Voronoi diagram is a tessellation that divides a plane into regions based on proximity to a set of seed points. Delaunay triangulation uses the same set of seed points to build a mesh of triangles, where each triangle has a circumcircle associated with it.

Q: How is the Delaunay triangulation calculated in the video?

The video demonstrates the use of a package inside the d3.js library to compute the Delaunay triangulation, specifically using the d3-delaunay triangulation package. The code showcases how to convert p5.js vectors into a format compatible with d3.js to compute the triangles.

Q: What is Lloyd's relaxation algorithm and how does it improve Voronoi stippling?

Lloyd's relaxation algorithm, also known as a relaxation algorithm, aims to optimize the distribution of points in a Voronoi diagram. By finding the centroids of each polygon and moving the seed points towards these centroids, the algorithm gradually spreads out the dots in a way that is visually pleasing.

Q: How is weighted Voronoi stippling achieved?

Weighted Voronoi stippling involves assigning weights to the seed points based on the brightness of the corresponding pixels in an image. The Lloyd's relaxation algorithm is then used to distribute the dots in a manner that reflects the image's underlying pattern, resulting in a stippled image with varying dot densities.

Summary & Key Takeaways

• The video explores the concepts of Voronoi diagrams and Delaunay triangulation to create a base for weighted Voronoi stippling.

• Lloyd's relaxation algorithm is then introduced to optimize the distribution of dots in the stippling, creating a more even and visually appealing result.

• The video demonstrates how to implement these concepts using the d3.js library in combination with p5.js.