|
Hi,
thanks for your interest in my problem. I understand what you say and you are right for the image I posted. I made a more precise one now.
P are points
M are mids between two points
blue lines point to right data
green lines point to left data
V is the voronoi point (VVertexA)
Rays are drawn by hand so far. Starting at V.
https://www.dropbox.com/s/fqxkg9im5e5bnmk/voronoi_ray_problem2.png[^]
My Problem is how to get the correct direction of the ray vector.
|
|
|
|
|
Ah, I remember.
The right solution was posted a long time by ckaut:
On an unbounded edge, only one point, let's call is 'center', is set. Comput a vector
diff = (left_data+right_data)/2 - center
and paint a line from center to center + N * diff (where N is large enough to go out of your viewing area.
For this it does not matter if left and right are correctly assigned.
BTW: I haven't looked at the code in a while, but it seems like I added
VoronoiEdge.FixedPoint (=center) and VoronoiEdge.DirectionVector (=diff, normalized)
for exactly this purpose Sorry for not documenting it better.
|
|
|
|
|
Yes this looks like a very easy solution and this was what I already tried.
But it's only the solution for the half of this problem.
If the center (V) is within the triangle of the three Points (P) then this way is right (correct for this problem[^]).
But if the center (V) is outside the triangle then it fails too (still fails in this problem[^]). Ray13 should be the other direction here.
|
|
|
|
|
Uh, that's true. Appearantly I did not see this case during debugging.
This will probably need a bit more smarts in the Algorithm itself to correctly assign left and right data points, but I might not have time for that in the near future.
Feel free to give it a shot: in FortuneVoronoi.cs, ProcessDataEvent, left/right data is assigned, but after that there are some special cases for how to insert the new tree nodes. My guess is that left/right data points should be assigned based on the same if/else distinguation. Give it a try!
|
|
|
|
|
This was a nasty trap ;(
I saw this example (Visualization of the 2D Voronoi Diagram and the Delaunay Triangulation[^]) of an implementation of your algorithm. I downloaded both (yours and the example) and picked the wrong one. What I didn't see is that this example is using an old and buggy version of your code.
With the code from this article here I finally got the correct rays by drawing a line using the DirectionVector and the FixedPoint. I better only post a class below how I did it. If anyone is interested in my full example code you can email me, because I don't want anyone to run into the same problems again by republishing another version of this code.
Thanks a lot for your help.
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using BenTools.Mathematics;
namespace FortuneVoronoiVisualisation
{
class Visualisation
{
public static Bitmap GetVoronoiMap(int width, int height, HashSet<Vector> datapoints)
{
Bitmap bmp = new Bitmap(width, height);
VoronoiGraph graph = Fortune.ComputeVoronoiGraph(datapoints);
Graphics g = Graphics.FromImage(bmp);
for (int w = 0; w <= width; w = w + 20)
g.DrawLine(Pens.AntiqueWhite, w, 0, w, height);
for (int h = 0; h <= height; h = h + 20)
g.DrawLine(Pens.AntiqueWhite, 0, h, width, h);
foreach (Vector v in datapoints)
{
g.FillEllipse(Brushes.Red, (int)v[0] - 2, (int)v[1] - 2, 4, 4);
g.DrawEllipse(Pens.Red, (int)v[0] - 2, (int)v[1] - 2, 4, 4);
}
foreach (Vector v in graph.Vertizes)
g.DrawEllipse(Pens.Indigo, (int)v[0] - 2, (int)v[1] - 2, 4, 4);
foreach (VoronoiEdge edge in graph.Edges)
{
try
{
if (!edge.IsPartlyInfinite)
{
g.DrawLine(Pens.Gray, (int)edge.VVertexA[0], (int)edge.VVertexA[1],
(int)edge.VVertexB[0], (int)edge.VVertexB[1]);
}
else
{
if (!edge.IsInfinite)
{
Vector VVertexB = edge.FixedPoint + edge.DirectionVector*edge.VVertexA.SquaredLength;
g.DrawLine(Pens.Blue, (int) edge.VVertexA[0], (int) edge.VVertexA[1],
(int) VVertexB[0], (int) VVertexB[1]);
}
else
{
Vector VVertexA = edge.FixedPoint -
edge.DirectionVector*Math.Sqrt(Math.Pow(width, 2) + Math.Pow(height, 2));
Vector VVertexB = edge.FixedPoint +
edge.DirectionVector*Math.Sqrt(Math.Pow(width, 2) + Math.Pow(height, 2));
g.DrawLine(Pens.Blue, (int)VVertexA[0], (int)VVertexA[1],
(int)VVertexB[0], (int)VVertexB[1]);
}
}
}
catch (Exception e)
{
}
}
return bmp;
}
public static Bitmap GetDelaunayTriangulation(int width, int height, HashSet<Vector> datapoints)
{
Bitmap bmp = new Bitmap(width, height);
VoronoiGraph graph = Fortune.ComputeVoronoiGraph(datapoints);
Graphics g = Graphics.FromImage(bmp);
foreach (Vector v in datapoints)
{
g.FillEllipse(Brushes.Red, (int)v[0] - 2, (int)v[1] - 2, 4, 4);
g.DrawEllipse(Pens.Red, (int)v[0] - 2, (int)v[1] - 2, 4, 4);
foreach (VoronoiEdge edge in graph.Edges)
if (edge.LeftData == v)
g.DrawLine(Pens.Black, (int)edge.LeftData[0], (int)edge.LeftData[1], (int)edge.RightData[0], (int)edge.RightData[1]);
}
return bmp;
}
}
}
|
|
|
|
|
Just a note to say I get the same thing unfortunately.
|
|
|
|
|
In most cases you have 2 infinite edges per area. Just find the crossing point of them and choose direction from this point to the VVertixA (or the midpoint between Left and Right points) of the edge.
|
|
|
|
|
Hi,
Can somebody provides sample code,how to call this function. I am trying following code & getting error as invalid cast
Vector V1 = new Vector(2,2);
Fourtune.ComputeVoronoiGraph(V1);
Quick help would be appreciated.
Thanks
Sunil Terkar
|
|
|
|
|
You need to put your values into a List.. like
List<vector> v=new List<vector>();
v.add(myVector);
//more points added
feed v into ComputeVoronoiGraph
Cheers
Wayne
|
|
|
|
|
Hi great code!
I am trying to change your algorithm to fit the needs of sharpmap.geometries.point.
Sharpamap is a GIS .net .
http://sharpmap.codeplex.com/[^]
As you can imagine I am having some difficulties.
any ideas on the steps i should take ?
|
|
|
|
|
What problems do you have? Contact me by direct message if you want
B.
|
|
|
|
|
i've a problem of virsion with the code diagrm voronoi
i've the virsion 2005 please help me!
|
|
|
|
|
MMMM, very good code! Thank's. I want make class for visualization 2D Voronoi diagram and building Delaunay triangulation.
|
|
|
|
|
Thanks, for the code. Now I'm stuck, I'm trying to make polygons as the input instead of data points for Voronoi diagram. Please help!
|
|
|
|
|
Hi,
as far as I know, the Fortune algorithm is fixed to data points. Dealing with polygon has some nasty possible side-cases (what if they overlap?).
I would suggest this solution:
- Get all points of all polygons
- Compute the voronoi-graph on all points
- 'merge' regions where two neighboring points belong to the same polygon (i.e. remove voronoi edge -> this may also lead to the removal of some voronoi vertices)
if the polygons are sufficiently far from one another, this should give good results. The solution is not perfect because distance to the polygon is interpreted as distance to one of its edges (which is incorrect, distance should also be measured to the edges of the polygons). You can increase precision by artificially creating polygon vertices _on_ the polygon edges, though this will increase processing time, of course.
Just give a try ,
Ben.
|
|
|
|
|
Afternoon
First, great piece of code - have always been interest in Thessien Polygons.
Implementing your code to determine regions of influence use lat/longs as well as using GDI to show the image plot via HTML. Had to add some extra hashing, as well as Convex Hulling to determine boundries to build out necessary polygons - worked perfect.
I have only found one issue, one of lines/vector seem to be computing values that cause the line to plot in the wrong direction. This only occurs if the point it the lowest.
Any ideas ... If you there is way you can get me your email address I will gladly to send you the code or at least send you the out graphic.
Thanks in advance
Ken
Ken
|
|
|
|
|
Yes I am going to answer my own question ...
I found out the issue was my code relating to image area boundry in relationship to the formula to compute the end point of an Infinity point. Forgot to adjust the slope of line equation to account for variable image size.
Hence you do not need to answer this posting, but yet again, can you post a complete API document/sample code for the DLL. Notice you have some stat functions (e.g. DAStdv). I was able to figure out a few, but would like to see how the other function.
Thanks
Ken
Ken
|
|
|
|
|
Trying to figure out how your implementation of this algorithm works, I instead figured out that this code is a mess!
Implementation is quite poor, code is not commented at all!
That Vector class? Very slow and not usable at all. Makes the code more unreadable with all that v[0], v[1] to say v.X and v.Y.
I prefer the use of Vector2, Vector3, Vector4 STRUCTS with specialized methods for linear algebra things applied in 2D and 3D.
VectorX class should be IMMUTABLE, so, it makes no sense to use a class: with Vectors, Points, Size and whatever you should use always structs when you can.
Use of Vector2, Vector3, Vector4 structs is safer and a lot faster!! See XNA for example.
You can even pass these vectors by reference in private methods to increase performance if you don't want to copy all these.
Another important thing: arrays of structs are always lot faster than arrays of objects!
Another very bad thing is to use floats or doubles as key for hash tables!
double.GetHashcode = unreliable code, also if you use rounding!
You should use some kind of AVL or Red Black tree with a fuzzy comparator (a comparator with tolerance).
For example, you can use SortedDictionary<> that is internally implemented with a Red Black tree (if you use .NET 2.0 or later).
This is an implementation for .NET 2.0 of the fuzzy comparer.
Of course, you can write it too for .NET 1.0 and for your datastructures like VoronoiEdge, or Vector2.
public sealed class FuzzyComparer : IComparer<double>, IComparer
{
public static readonly FuzzyComparer Default;
private readonly double tolerance;
public double Tolerance { get { return this.tolerance; } }
public int Compare(double a, double b)
{
double diff = a - b;
if (diff > this.tolerance) return 1;
if (diff < this.tolerance) return -1;
return 0;
}
int IComparer.Compare(object a, object b)
{
return Compare(a is double ? (double)a : 0, b is double ? (double)b : 0);
}
public FuzzyComparer()
: this(0.00000001)
{
}
public FuzzyComparer(double tolerance)
{
this.tolerance = tolerance;
}
static FuzzyComparer()
{
Default = new FuzzyComparer();
}
}
Of course, hashtables are O(1) while trees are O(log(n)), but really, this doesn't change the complexity of the overall algorithm, of course.
Instead, you can optimize a lot of other portions of that code using safer and faster data structures.
Sorry if I was rude, I don't want to offend anyone of course.
I want to thank you sharing your work to the code project community too.
Thanks.
I don't fear computers.
I fear the lack of them.
(Isaac Asimov)
modified on Monday, June 9, 2008 2:35 PM
|
|
|
|
|
One more question:
How could I easily extract centers of each face, made by VoronoiGraph.
Because the graph only returns vertices and edges, but no information about faces...
thanks in advance
|
|
|
|
|
Hej, can u help me with this code; FortuneVoronoi...
How do I get values of calculated vertices and edges, once the graph is calculated? I have never worked with hashSets before and I can't figure it out by myself, but I would appreciate if anyone could tell me.
The VoronoiGraph class only returns hashSet, so how do I get values?
Thanks in advance.
|
|
|
|
|
Never mind, I figured it out.
VoroniGraph.Vertices is a list of Vectors, which are readable...
thanks anyway for the code
|
|
|
|
|
Please show a sample with this lib,Thanks
|
|
|
|
|
First of all many thanks for providing this implementation of Fortune's algorithm in c#. The code seems to be working fine on randomly created point sets. However I have tested the code on several point sets of real-world (geographical) data and many times incorrect Voronoi diagrams are the result. I don't know where the error lies but I can send you screenshots+data if you want, to show you the problem.
|
|
|
|
|
Mmmh, we had one real problem and several double rounding errors in the past, but I've used the current version for real applications as well (PIONEER robot laser data) and it worked very well.
Anyway, if you're sure it's not a rounding problem (relevant data <1e-6), I'll be happy to look at the examples you have and try to fix something.
Ben.
|
|
|
|
|
Okay I found the problem and it was my own fault
There were duplicate voronoi sites in the input data set which caused the wrong output.
It seems that the check for identical datapoints in the ParabolicCut routine does not work?
|
|
|
|
|