Sweep line algorithm - Voronoi tessellation

Steven Fortune's sweep line algorithm for constructing a Voronoi tesselation. I use this algorithm in every timestep of a hydrodynamical simulation.
The code is publicly available: github.com/m31coding/Havoc

[@matthieujoannon73]

Extremely satisfying to watch. 10/10 !

[@jonneh8317]

Holy shit, I've been struggling to understand what goes on in Fortune's Algorithm as most visualizations just jump from event to event.
This, without any words at all, explains everything perfectly. Thank you, friend.

[@subarnachatterjee3586]

hmm.. nice one.. although it lacks expalnations, the diagrammatic approach is very clean..

[@CarrotCakeMake]

Glad I found this before spending too much time reading stuff.

[@gabrielzenobi6928]

excellent work

[@FahadAshraf1995]

Thanks Kev!

[@davidmaynard5181]

That’s really pretty

[@anuragpacholi]

Protect this video at all costs.❤🎉

[@headshot690]

NICE!
WAIT A MINUTE/
ITS BEEN 10 YEARS!

[@TranquilSeaOfMath]

Nice animation.

[@markus_knoedel]

Great. Although I don't know how to write the codd for this. But great to watch.

[@m31coding]

The code is finally publicly available: github.com/m31coding/Havoc

[@Everlier]

How do you approximate straight lines correctly after casting the parabolas?

[@m31coding]

Hey,
thank you for your interest. Two things: The movie is just a visualization, in the actual algorithm the sweep line jumps from event to event. Secondly, the intersection of two parabolas traces a perfectly straight line.

[@Everlier]

Kevin Schaal
Yeap, i understand that line is straight. But it straight perfectly only with perfect precision of floating point calculation. Thats was my poin of intrest.
By the way, discreteness of calculation situations is make the thing clearer for me.
Thanks for feedback.

[@curtiswfranks]

How are the parabolas(?) determined at each point in time?

[@m31coding]

The parabolas are determined such that every point along the line has the same distance to the mesh generating point (red) and the sweep line (blue). For the Euclidian distance metric the results are parabolas, for the Manhattan metric the results are V-shapes of straight lines.

[@ibiixie]

I'm thinking of using this for city generation and road generation in my game, however I can't find any good videos/websites to explain how to implement it...

[@m31coding]

Hi,
you may find an explanation in my diploma thesis which can be found on my homepage. Moreover, I can recommend the book "Computational Geometry - Algorithms and Applications".
best regards,
Kevin

[@ibiixie]

Kevin Schaal Alright, will check those out! Thank you :D

[@colonthree]

I'm using it for my mesh generator now. It's really good. :3c

[@colinmcmahon5829]

Tiny Bubbles, it's an Aero!
So, what are you doing after the Game?

[@FlareGunDebate]

aaaaaahhhhhyyyeeeeaaaahhhhhhh

[@rayhaoray]

I'm trying to implement this method. Do you mind to share your code? That would be very helpful! Thanks

[@m31coding]

github.com/m31coding/Havoc

[@fuzzytheduck6821]

Bubbles be like

[@user-464cH3]

How it works!?

[@wjrasmussen666]

any chance of getting source code?

[@m31coding]

It is finally available: github.com/m31coding/Havoc

[@wjrasmussen666]

@@m31coding Thank you so much. I see you have PHD and that you earned it. Thanks, the code samples are always helpful. If I create anything interesting, I will let you know!

[@m31coding]

@@wjrasmussen666 Sounds good, have fun :)

[@sspark010]

0:00