SOS

Shane O'Sullivan's technical blog… really ties the room together

Fortune’s Sweep-Line Voronoi algorithm implemented in Java!

Posted by Shane O'Sullivan on April 5, 2007

Zhenyu Pan, a Masters student from York University, has reimplemented my C++ Voronoi generation algorithm (itself an adaptation of Steven Fortune’s sweep-line algorithm written in C) in Java.  A Voronoi diagram is a graph where each edge is equidistant from the two points in the graph closest to it. Voronoi Diagram

Background:

Quite a few years ago (2003) I completed a research masters in mobile robotics, concentrating on robotic navigation and map building.  As part of that research, and for about a year after it, I wrote many (many, many,many :-) ) thousands of lines of code to perform map building using sonars in numerous different ways, as well as performing a lot of different analysis techniques on them, one of which used Voronoi diagrams for spatial analysis.  If you’re interested, you can download my Masters Thesis here.

So as to not see my work fade away and die, I first of all wrote an application called Map Viewer that provides lots of the useful features for researchers in mobile robotics and map building.  Secondly, I started an open source project on Sourceforge called Map Manager, which is a standalone library that people can integrate into their own research.  This included the Voronoi code I wrote, all in C++.

Back to the present:

Well, while I’ve been getting a steady number of emails over the years of people using my code (not exactly a flood, 3 or 4 per month), this is the first time that anyone has contributed back.  Zhenyu Pan completely reimplemented my Voronoi C++ class in Java, and incorporated it into a Java Applet.  Needless to say, I am very impressed.

The algorithm was originally written by a researcher called Steven Fortune in C, and while very performant and intelligent, it followed in the grand tradition of all C programs in being completely incomprehensible.  I spent many a painful night converting into a marginally more understandable C++ class (also cleaning up the code, fixing memory leaks etc).  That Zhenyu has been able to convert it from C++ to Java is very impressive (C to C++ is not so tricky, since C++ is a superset of C), as the code made very liberal use of non-Java constructs such as double pointers.  His code, like mine and Stevens, runs extremely quickly, and seems to be very accurate and reliable.

I’ll be adding his code to the Map Manager open source project soon.  For now, I’ve put his applet on the web at http://mapviewer.skynet.ie/java , and he will soon be putting it up on his university’s website at http://www.cse.yorku.ca/~aaw .

A big thanks to Zhenyu for attempting such a challenging project, and for contributing back to the project.

About these ads

33 Responses to “Fortune’s Sweep-Line Voronoi algorithm implemented in Java!”

  1. zzorn said

    Hi,

    Just wondering what the status of the Java Voronoi code is? I didn’t see it in the MapManager project CVS repository yet, and the linked university pages only seem to contain applets and pseudocode, no sources.

  2. Good question – I’ll send an email to the author too see how he’s getting on. Until he gets back to me, the code is available at http://mapviewer.skynet.ie/java/voronoi_java.zip

  3. zzorn said

    Ok, thanks.

  4. Christopher Willmot said

    Thanks very much for making this stuff available. The power-point and lecture notes on your website were the best presentation of the Fortune Sweep algorithm I’ve come across.

  5. Hi Christopher,

    You’re very welcome, glad it helped.

    Shane

  6. Seigneur said

    Wow, interesting…

    Congrats, and thanks for making it available, impressive stuff.

    I have few questions:

    - In the algorithm you get just the sides (lines) that makes the Voronoi’s diagram, or you can get polygons (areas) too?
    - In case that it only gets the sides (lines), it would be hard to implement a way to get polygons (areas)?

    *Sorry, but im not good at english… xD

  7. You’re very welcome. It doesn’t calculate the polygons, however it does calculate the set of edges. You can retrieve them using getNextVertexPair(). Make sure to set ‘genVectorInfo’ to true when calling the generateVoronoi() function.

    This will give you a list of edges. You could then write some logic that matched up all edges that form a polygon, using some kind of 2d map.

    Thanks

    Shane

  8. You’re very welcome. It doesn’t calculate the polygons, however it does calculate the set of edges. You can retrieve them using getNextVertexPair(). Make sure to set ‘genVectorInfo’ to true when calling the generateVoronoi() function.

    This will give you a list of edges. You could then write some logic that matched up all edges that form a polygon, using some kind of 2d map.

    Thanks

    Shane

  9. Daniel said

    Hi Shane.

    I tried to write a wrapper for your Voronoi code in order to save myself the huge effort of wading through Fortune’s C code myself. Thanks for putting your work online, by the way :-)
    I had to chop out the logger files since your preprocessor magic wouldn’t compile under my system (WinXP, DevCPP 4.9.9.2 with MinGW), but I redirected some of that to std::cout to check intermediate results.

    Now however to the critical point:
    I entered some test cases and in none of them any output was generated. I checked if the critical functions in your code were entered, and everything seems alright, but after the generateVoronoi function is done, there are no edges and no vertex pairs.

    I made the pushGraphEdge() function output a notifier whenever it is called to check if it only is an interface problem with my wrapper, but apparently indeed no edges are written. My main test case consisted of 4 points arranged basically like a Mercedes Benz star well inside the bounding box. Your infinite while loop counted up to 7 events, which is exactly what I’d expected from comparing with interactive voronoi tools found on the web.

    My wrapper is basically this:

    float minDist = 0.0;
    cout << “entering Shane O’Sullivan’s routine” << endl << endl;
    VoronoiDiagramGenerator vgen;
    bool success = vgen.generateVoronoi(xVal, yVal, pl.getNumberPoints(), float(minX), float(maxX), float(minY), float(maxY), minDist, true);
    cout << “SOS voronoi algorithm: ” << (success? “success” : “failure”) << endl;
    float x1, y1, x2, y2;
    //read all edges
    vgen.resetIterator();
    while(vgen.getNext(x1, y1, x2, y2) ){
    //returnValue.addEdge(x1, y1, x2, y2);
    cout << “found edge: ” << x1 << “,” << y1 << ” – ” << x2 << “,” << y2 << endl;
    }

    //read all vertex pairs
    vgen.resetVertexPairIterator();
    while(vgen.getNextVertexPair(x1, y1, x2, y2) ){
    cout << “found vertex pair: ” << x1 << “,” << y1 << ” – ” << x2 << “,” << y2 << endl;
    }

    Any glaring interface errors? Any idea what I did wrong?

  10. [...] Fortune’s Sweep-Line Voronoi algorithm implemented in Java! « SOS (tags: voronoi algorithms geometry robotics path planning navigation) [...]

  11. Keith Youngblood said

    Thank you! You are very kind for sharing your hard work.

    I plan to derive the logic that produces polygon data from the edge data. I would also like to do this by pairing the edges with the corresponding points they bisect so that adjacent cells(polygons) can share signals through this “boundary”.

  12. kheong sann Chan said

    Hi Shane,

    Thanks very much for sharing your C++ code. I am using your program to generate Voronoi cells to represent magnetic grains on a medium to model hi-density magnetic recording. I’m compiling my program and testing it with Valgrind to catch memory leaks. I’m picking some memory leaks that I think may be tied to your VoronoiDiagramGenerator.cpp. Sample output from Valgrind:
    ==30080==
    ==30080== 8 bytes in 1 blocks are definitely lost in loss record 1 of 14
    ==30080== at 0x40253C5: operator new(unsigned int) (vg_replace_malloc.c:214)
    ==30080== by 0x804D0BD: VoronoiDiagramGenerator::VoronoiDiagramGenerator() (VoronoiDiagramGenerator.cpp:37)
    ==30080== by 0x804BD9D: calcVoronoiVertices(media*) (createMedia_VoronoiGrains.cpp:605)
    ==30080== by 0x804BD00: calcVList(media*) (createMedia_VoronoiGrains.cpp:582)
    ==30080== by 0×8049810: main (main.c:120)
    ==30080==

    I think the memory leak may be quite small, Valgrind is reporting only 988 bytes lost at the end. I’m not sure how much of it is from my code, and how much of it is VoronoiDiagramGenerator.cpp.

    Unfortunately I am new to C++ and it’s memory allocation methods, otherwise I would send you a code-fix. As it is, I can only say that Valgrind is reporting some lost memory.

    • kheong sann Chan said

      BTW, I read back in posts and saw Seigneur’s question about calculating polygons and areas.
      That is just what I am doing now. I’m using another free library called ANN (approximate nearest neighbors) to efficiently find the nearest neighbor of each Voronoi Vertex (vv), where the search is over the set of voronoi nodes. Most vv’s should have 3 nearest neighbors that are equally near. I push each vv onto a list of vertices associated with each of the 3 nearest nodes. Each voronoi node, will have a list of vertices which make up its polygon, that I’ve been calling the vList.
      You have to sort those vertices such that they are in order of increasing (or decreasing) angle subtended at the node (or at any point inside the cell). Following the vertices around in this order will generate the polygon. Areas of the polygon can be calculated as a summation of areas of triangles formed by 2 vertices and the node, iterating over each pair of vertices comprising the edges of the polygon.

  13. [...] dis­cussed but rarely imple­mented. wblut.geom.WB_Voronoi2D is a bare-bones adap­ta­tion of Zhenyu Pan's JAVA transcription of Shane O’Sullivan’s [...]

  14. [...] dis­cussed but rarely imple­mented. wblut.geom.WB_Voronoi2D is a bare-bones adap­ta­tion of Zhenyu Pan’s JAVA tran­scrip­tion of Shane O’Sullivan’s C [...]

  15. Felix said

    shit – I just saw that I posted my email adress as name – can you *please* delete the comment to prevent it from being harvested?

    Thanks

  16. Felix said

    Thanks a lot.

    I am referring to the C++ code. I am using it for a video-installation that generates voronoi diagrams in real-time.
    Unfortunately, the process gets bigger at a rate that is almost as amazing as the speed of the calculation…
    Did you ever see this problem yourself?

    Thanks,

    Felix

  17. James Humphreys said

    Shane,

    A huge thankyou to you and Zhenyu for making this code available. I’ve been using it to generate maps of UK postcode sectors.

    I’ve taken Zhenyu’s Java version, refactored it somewhat and converted it to a Maven-based project. I’ve created a tiny Sourceforge project in case it’s useful to anyone else. It’s at https://sourceforge.net/projects/simplevoronoi/
    For now, it’s mostly just a dump of the code in its current state. Needs Unit test and basic documentation – to be added soon hopefully. I figured I might as well make the code publicly available in a neat format. If you have any comments or thoughts, leave a reply or drop me an email.

    Download link: http://sourceforge.net/projects/simplevoronoi/files/simplevoronoi-trunk-20110706.tar.gz/download

    I’ve included the licence info that’s been added over the years (Stephen Fortune, Shane O’Sullivan, , Zhenyu Pan).

    Thanks again for the code.

    James Humphreys

  18. Richard said

    Hi!
    first, I thank you for you work. I want to do the same as Keith Youngblood. I use the Java implementation. I there a way to get all the lines that correspond to a point. I also want to build polygons. There is no getVertexPair() in the Java implementation.

    Maybe you can get me some help. Inside voronoi_bd() where the sweep is done i plan to get the two Sites that correspond to a Edge and further process this information. As far as I understand, a edge is only created in the vector event?

    Many Thanks,
    Richard

  19. [...] dis­cussed but rarely imple­mented. wblut.geom.WB_Voronoi2D is a bare-bones adap­ta­tion of Zhenyu Pan’s JAVA tran­scrip­tion of Shane O’Sullivan’s C [...]

  20. eisprungkalender…

    [...]Fortune’s Sweep-Line Voronoi algorithm implemented in Java! « SOS[...]…

  21. Elumalai.G said

    Hello sir,
    i am implementing voronoi diagram in NS2. So kindly i need a sample code for voronoi construction in TCL or in C++. Pls help me to complete my project. Am expecting a possible answer from u.

  22. Dylan said

    How is it that we’ve never discussed voronoi before? My grad school research involved voronoi tesselations on quasi-2D foam…

  23. Thanks for finally talking about >Fortunes Sweep-Line Voronoi algorithm implemented in Java!
    SOS <Liked it!

  24. sudha said

    pls send ns2 coding for region splitting in voronoi diadram as soon as possible

  25. sudha said

    can u send ns2 coding for voronoi diagram?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

 
Follow

Get every new post delivered to your Inbox.

Join 533 other followers

%d bloggers like this: