search

CodingTrain / Suggestion-Box

A repo to track ideas for topics
571 stars 86 forks source link

Crystal Voronoi diagram #1406

Open adamwilco opened 4 years ago

adamwilco commented 4 years ago

Voronoi Diagrams have been done, and they have their use, but crystal voronoi are a lot more fun and interesting. They simulate the growth of various crystals, where each crystal has its own starting point and growth rate.

So the input variables are the starting locations and the growth rates, and you can iterate through small steps in time to draw the diagram. If the crystals are sufficiently far away from one another, they will each be a circle with a radius equal to the time multiplied by the growth rate. The crystals cannot overlap, so when they get close enough to each other that their radius overlaps, their boundary can be either a curve or a straight line (a circle with infinite radius). image

They make for very interesting and useful charts, and it is a good coding challenge. In looking around, I haven't found any instances of sources similar to the Coding Train making these sorts of charts. I see them used in academic circles, but that is about it. I think making a Code Challenge for this would be both interesting for the viewers and generally useful to the wider coding community.

duskvirkus commented 4 years ago

Great suggestion! Relates to #6 and #232.

adamwilco commented 4 years ago

I used Delaunay triangulation to color in the regions, but I kept running into a problem where I wanted to draw the outer perimeter in counter clockwise and the inside holes clockwise, but I couldn't figure out how to reliably make it work. I kept running into issues where the hole would get too close to the outside edge and it would all break and turn into a big mess. Right now, I draw a load of line segments to create the chart (on the order of like 30,000 line segments), but I don't know how to link them all to create coherent regions I can use to fill with color or use to search (does my mouse fall into this site or that site?). At least not in a generalized case. I got it to work some of the time but not all of the time.