Sweep line algorithm - Voronoi tessellation

Рет қаралды 74,577

11 жыл бұрын

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

Пікірлер: 32

@matthieujoannon73 8 жыл бұрын

Extremely satisfying to watch. 10/10 !

@jonneh8317 5 жыл бұрын

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 11 жыл бұрын

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

@CarrotCakeMake 2 жыл бұрын

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

@anuragpacholi Жыл бұрын

Protect this video at all costs.❤🎉

@headshot690 8 ай бұрын

NICE! WAIT A MINUTE/ ITS BEEN 10 YEARS!

@gabrielzenobi6928 Жыл бұрын

excellent work

@FahadAshraf1995 5 жыл бұрын

Thanks Kev!

@davidmaynard5181 6 жыл бұрын

That’s really pretty

@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

@FlareGunDebate 8 ай бұрын

aaaaaahhhhhyyyeeeeaaaahhhhhhh

@user-464cH3 4 ай бұрын

How it works!?

@curtiswfranks 4 жыл бұрын

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

@m31coding 3 жыл бұрын

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.

@Everlier 10 жыл бұрын

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

@m31coding 10 жыл бұрын

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 10 жыл бұрын

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.

@ibiixie 8 жыл бұрын

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 8 жыл бұрын

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 8 жыл бұрын

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

@colonthree 4 жыл бұрын

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

@fuzzytheduck6821 3 жыл бұрын

Bubbles be like

@sspark010 Жыл бұрын

0:00

@colinmcmahon5829 3 жыл бұрын

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

@rayhaoray 9 жыл бұрын

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

@wjrasmussen666 2 жыл бұрын

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 :)