StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Fortune's algorithm is O(n log n) - but your code will be O(n^2), if you try to reconstruct cells brute-force fashion as proposed by Alink. </p> <p>The starting point for my answer is that what you are using to generate the cells is not a library, but rather is just <a href="http://www.skynet.ie/~sos/mapviewer/voronoi.php" rel="nofollow noreferrer">a class written to neatly wrap up the code originally presented by Fortune himself</a>, and not actually a mature library. So, the author in fact hasn't anticipated your needs, and although the information you want has been computed, it isn't accessible. </p> <p>Internally, your input points are stored as instances of the "Site" struct, and the algorithm proceeds to create <a href="http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml" rel="nofollow noreferrer">half-edges</a>, each of which maintains a reference "vertex" <em>which is a pointer to the Site it encloses</em>. Stepping along half-edges you naturally circumnavigate the enclosed Site - exactly what you need. </p> <p>To access this data, I suggested modifying or extending the VoronoiDiagramGenerator class; I would do it by creating a hash table with Site pointers as the key and a single HalfEdge pointer as the value. Then, modify the generateVoroni method, inserting your new code immediately following the call to voronoi:</p> <pre><code>For each HalfEdge in ELHash Get table entry for current half edge's Site If site in table has null HalfEdge reference set current HalfEdge reference End If End For each </code></pre> <p>...and there is your dictionary. That single half-edge will allow you to "walk" the perimeter of the polygon enclosing the related site, which I think is what you asked for. Your next problem will be to efficiently discover <em>which</em> polygon encloses some new data point - but that is another question :-). I hope you'll consider sharing your completed class - it should be a significantly more useful than the base class.</p> <p>Edit: Here is an excellent presentation descibing all said above in pictures: <a href="http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt" rel="nofollow noreferrer">http://ima.udg.es/~sellares/ComGeo/Vor2D_1.ppt</a>:</p> <ul> <li>definition of Voronoy Diagram</li> <li>tree of of half-edges (see pics. below)</li> <li>Fortunes algorithm in pictures</li> </ul> <p>And here is a C# implementation which could help you to retrieve the dictionary, as proposed above: <a href="http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C" rel="nofollow noreferrer">http://www.codeproject.com/Articles/11275/Fortune-s-Voronoi-algorithm-implemented-in-C</a></p> <p><img src="https://i.stack.imgur.com/KnCi9.png" alt="Slide 31"> <img src="https://i.stack.imgur.com/AERhQ.png" alt="Slide 32"> <img src="https://i.stack.imgur.com/d8HIK.png" alt="Slide 33"> <img src="https://i.stack.imgur.com/ASjce.png" alt="Slide 34"></p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload