search

CodingTrain / Suggestion-Box

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

Delaunay Triangulation #6

Open Flameingo opened 8 years ago

Flameingo commented 8 years ago

On this topic: https://en.wikipedia.org/wiki/Delaunay_triangulation

Trangulating a polygon means to split it up into smaller triangles. Your Program could generate some random points and triangulate the konvex hull of them.

Then the challenge would be to find out which triangles are needed to be flipped to make a delaunay trangulation out of it.

Next you could make a voronoi diagram, which tells you areas that are closest to one of the point. This is to be imagines like having multiples schools and finding the areas for each school to pull pupils from, based on travel distance. To do so, you would have to make lines that are perpendicular to the edges of the triangles of the delaunay triangulation and they are cut off by each other.

I think you would be able to do the delaunay triangulation in one ~15 min coding challenge, but the voronoi diagram might be a bit harder.

MAKIO135 commented 8 years ago

It could also be a subject to introduce p5js with addition of other libraries like delaunay.js

vvzen commented 8 years ago

That would be awesome, totally looking forward to this! :)

MAKIO135 commented 8 years ago

I've done a commented example on using P5js + delaunay.js: http://codepen.io/MAKIO135/pen/amwbvO

meiamsome commented 7 years ago

Perhaps these should be separated, keep this issue for Delaunay and use #232 for Voronoi as it is the clearest request for Voronoi CC so far.

shiffman commented 7 years ago

@meiamsome agreed, this will definitely need to be a two-part challenge. I'm excited to take a crack at it. One thing that is necessary for the algorithm is finding a "circumcircle" for 3 points, this could actually be a nice little challenge just itself too.

AcousticQuantum commented 7 years ago

I would love as well to have a tuto about Voronoi or Delaunay triangulation! Actualy I did a sketch in processing 2.2.1 to transform the video from the webcam in Delaunay triangulation... I have a good result except it is very very slow :( I found that one, http://kaizouman.github.io/js-delaunay-effect/ which is older than mine and specialy definitly faster than mine (and this one is live on the net!!!). So I wonder what's wrong in mine... I used the librairies "megamu mesh" and "quickhull3d" to do it. Here is the code I made, if someone have any suggestion, feel free to contact me... All the best :) DelaunayWebcam.txt

duskvirkus commented 5 years ago

I know this is a fairly old suggestion but I wanted to bring it back up because I've been struggling to find good resources on learning this. @shiffman if you ever do this coding challenge then Matt Jacobson has done some realtime and interesting circle packing using a delaunay triangulation which might be an interesting part 2.

shiffman commented 5 years ago

Hi @figraham thank you for the suggestion! Agree and maybe I can tackle it this month, live streams returning tomorrow!

duskvirkus commented 5 years ago

@shiffman Cool! Also I saw this JavaScript library which might be useful as a reference. I spent awhile trying to recreate it but the math is a little beyond me.

knectardev commented 4 years ago

hi @shiffman

re: but the math is a little beyond me.

Seriously daunting.

Is there any chance you would consider tackling this in collaboration with a maths specialist with familiarity on the subject? I would love to understand voronoi (for its massive creative / algorithmic art possibilities) with the benefit of your approach, i.e. us learning through you learning! :)

GiorgioRemindme commented 2 years ago

yes a tut on delunay triangulation would be freat! :)