I'm working on exactly your problem for my honours project. I've found that the code here http://www.skynet.ie/~sos/mapviewer/voronoi.php is easier to use than Fortune's original C code. I've modified it to output vectors of the input points, the edges, and the end points of the edges. The end points for the edges are joined together, so if two lines end at the same point, the line class points to the same end point. I could send you my code if you'd like.
An easy way (but a bit slow) that I did it was to use the edge circumcircle property. From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle. So this makes for a pretty easy brute force algorithm. For each candidate edge you simply count the number of vertices in its circumcircle. Once you have your edges you can easily form triangles, or a Voronoi or what-have you.
I've actually read through this text and found that the technical language is over my head. As well, it doesn't provide step by step solutions to the problems, but rather general descriptions. I'm sure these descriptions are the only road map an experienced programmer with a formal education in upper-lever math would need. But I'm entirely self taught, so the nomenclature kills me.
So, in an effort to maximize the minimum angle, and taking advantage of the Delaunay property of circles, the easiest way to go about turning a random triangulation into a Delaunay one is to compare and correct adjacent triangles together. Something like:
for every pair of adjacent triangles
if they aren't delaunay
make them delaunay
, which is actually really nice. Not many other triangulation methods that I know of become correct just by correcting triangles piecewise like this.
The "make delaunay" step is the key here. It just so happens that the easiest way to make a non-Delaunay pair of adjacent triangles correct again is to turn the exterior vertices into interior vertices and vice versa
This makes 100% sense. I got it! I also solved the whole Point within a triangle business, but found that clicks out side of the triangle are much harder to handle! Right now I make a traingle with triangle edge with the nearest bisecting point. This works for the first few, but falls apart. I'm not sure how to solve for clicks outside of the trianlge.
i meant to go through edge of every polyogn and if its a huge/big/decent change in the angle which you were fololoowing you add a vertex for that polygon, you can always disable the issue with additional vertex for the poly by finding first change and begin from that. no random polies are generated
Do you have an example I could see?
I'm working on exactly your problem for my honours project. I've found that the code here http://www.skynet.ie/~sos/mapviewer/voronoi.php is easier to use than Fortune's original C code. I've modified it to output vectors of the input points, the edges, and the end points of the edges. The end points for the edges are joined together, so if two lines end at the same point, the line class points to the same end point. I could send you my code if you'd like.
This is a great link! Thank you so much! I'm not quite sure how this works though, because I don't understand the data types that are being used. I'm using edges and vertices as well. How is this solving for the edges?
I would greatly appreciate it if I could take a look at how you solved this!
I would greatly appreciate it if I could take a look at how you solved this!
https://www.dropbox.com/s/3nb5lkh8yybrlbs/voronoi%20stuff.zip?dl=0
That should contain everything I did related to voronoi/delauny. You might also need Vector2 and Vector3 classes. Everything from the link I posted should still work. Use is as follows:
float* xValues = new float[numNodes];
float* yValues = new float[numNodes];
for (int i = 0; i < numNodes; i++)
{
xValues[i] = RandomFloat(size);
yValues[i] = RandomFloat(size);
}
VoronoiDiagramGenerator vdg;
vdg.generateVoronoi(xValues, yValues, numNodes, 0, size, 0, size, 0.0f);
points = vdg.outputPoints;
edges = vdg.outputEdges;
edgeEndPoints = vdg.outputEndPoints;
You can access the delauny triangulation through:
points[i]->edges[j]->GetOppositePoint(points[i])
An easy way (but a bit slow) that I did it was to use the edge circumcircle property. From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle. So this makes for a pretty easy brute force algorithm. For each candidate edge you simply count the number of vertices in its circumcircle. Once you have your edges you can easily form triangles, or a Voronoi or what-have you.
Ok, I took a swing at this and got pure chaos. After about 5 points it really starts to go down hill.
Here's what I did:
Made All Possible Edges Between All Points
Made All Possible Unique Triangles Out of These Points
-In the Constructor of the Triangle Object I Solve for Circumcenter and Radius
Cull Out All Triangles* That Had a non-Triangle* Point Within the Circumecircle
Here's what I got [4 Points Left; 5 Points Middle; 6 Points Right: Red Dots Are Edge Midpoints and Green Circles are the Circumcircles]:
Just a quick question, do you want a Delaunay Triangulation, like your title suggests, or do you want a Voronoi mesh, like your post suggests? If you're calculating a Voronoi with the end goal of turning it into a Delaunay, then there are far easier ways to do it.
What do you mean with that? They're each others dual, and in memory, they're often stored in the exact same way.
An easy way (but a bit slow) that I did it was to use the edge circumcircle property. From some lecture notes they state (pg. 27, Def 28) that an edge is delaunay if it has at least 1 empty circumcircle. So this makes for a pretty easy brute force algorithm. For each candidate edge you simply count the number of vertices in its circumcircle. Once you have your edges you can easily form triangles, or a Voronoi or what-have you.
Ok, I took a swing at this and got pure chaos. After about 5 points it really starts to go down hill.
Here's what I did:
Made All Possible Edges Between All Points
Made All Possible Unique Triangles Out of These Points
-In the Constructor of the Triangle Object I Solve for Circumcenter and Radius
Cull Out All Triangles* That Had a non-Triangle* Point Within the Circumecircle
Here's what I got [4 Points Left; 5 Points Middle; 6 Points Right: Red Dots Are Edge Midpoints and Green Circles are the Circumcircles]:
When you say 'point' in your algorithm you mean vertex and not mid-point right? From your description your algorithm should work.
Try this:
- for every possible edge calculate its circumcircle (find the midpoint as you already have and then the radius)
- throw away every edge with more than 0 vertices in its circumcircle (use < and not <= as your original two points should be equal/on the circumcircle, or explicitly exclude the original two, also floating point math may mean you might need a small 'fudge'/epsilon factor here)
- create your triangles from the remaining edges
I think that should work. Or perhaps I hope 
When you say 'point' in your algorithm you mean vertex and not mid-point right? From your description your algorithm should work.
Try this:
- for every possible edge calculate its circumcircle (find the midpoint as you already have and then the radius)
- throw away every edge with more than 0 vertices in its circumcircle (use < and not <= as your original two points should be equal/on the circumcircle, or explicitly exclude the original two, also floating point math may mean you might need a small 'fudge'/epsilon factor here)
- create your triangles from the remaining edges
I think that should work. Or perhaps I hope
I feel like I am getting close! I am getting some funky spaces in the middle of bunches of triangles though. What do you think is causing this?
Here's the code I am using to solve for edges [my apologies ahead of time for lack of elegance]:
Ok so I see what I did wrong with the previous bit of code. I wasn't making triangles with each edges and every other point. I tried this and the only problem is that it degrades at higher numbers of points. It doesn't even look like the same program... What could be going wrong?
So now here's what I did:
-Made Every Edge Possible
-For Each Edge, Make A Triangle
+If that triangle's circumcircle doesn't contain any other points then add that to the list of triangles
Yeah so, after about 30 hours of trying to figure this out, I have thrown in the towel. I've decided to use Hexagons, which have the properties of Voronoi Polygons, so functionally this is fine. Perhaps, though, hexagons are not at attractive. Here's what I've got so far.
Sorry, I don't know how to edit the title, but I would say this problem has been forgone, not exactly solved haha
