
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 realworld (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 <1e6), 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?





I would like to congratulation to your work.
This was the unique implementation in a civilized language (as you say).
But I don´t understand why you represent the 2D Vector as a double?
Could you make available some examples?
Bye
Cristiano





Thank you very much, Cristiano. I dont really understand the question, though. I represent a 2dvector with two doubles. Single lacks the precision and Decimal is much too slow. There is some downside when it comes to rounding doubles, but I'm confident I got it working. Does that answer your question?
Regards,
Ben.





Hello!
I have a big problem to use the lib.
I type two code like this
Vector[] v = new Vector[] { new Vector(1, 1), new Vector(3, 1)};
VoronoiGraph r = Fortune.ComputeVoronoiGraph(v);
and then I dont know how to use the result.
Can anyone help me
Give me a little sample(ex:how to draw in pictureBox)
Thanks for help.
Have a nice day!!
Li.





Ben,
Under what EULA this software is distrubuted?
Best Regards,
Andrea







Hi all,
I dont know how to easily update the article so just download the new version from here.
modified on Friday, March 7, 2008 9:46 AM





Hi BenDi,
Thanks alot for the fast answer. Now everything is there. So then i will give it a big try.
Andre





New code, but the same old errors.
vectors (1, 1),(2, 3),(5, 1). Result is only 2 edges!





I've had a look at it and I think I got it (at least I could construct no example that didn't work). Please try it and let me know if you find any.
modified on Friday, March 7, 2008 9:46 AM





Congratulations!
I did not find any errors. So far.





First of all: nice work!  (just looked into your code yesterday) !
This means as well I do not yet get all implications (for instance, I would think the data events should be processed in the order highest Ycoordinate to lowest one) but your code seems to work.
This data set did not produce what it should be:
Point(0.4, 0.4)
Point(0.1, 0.4)
Point(0.3, 0.2)
Point(0.05, 0.2)
Point(0.4, 0)
Point(0.1, 0)
Point(0.3, 0.2)
Point(0.05, 0.2)
Point(0.4, 0.4)
Point(0.1, 0.4)
(I got my inspiration here: http://www.diku.dk/hjemmesider/studerende/duff/Fortune/[^])
I have it rendered but seem not to be able to post the results  please try it, you'll see a lot of edges get their second point on (+infinity, +infinity).
Thanks and good luck
Puzzled Dirk





Hi, checked your example, works.
It's perfectly normal that there are edges with VVertexA or VVertexB equal to Fortune.VVInfinity: this means the voronoi edge is unbounded (e.g. if you only have two data points, the graph will have one infinite line between them).
To draw it, the VoronoiEdge offers the FixedPoint and DirectionVector properties:
<br />
Vector A = VE.VVertexA;<br />
Vector B = VE.VVertexB;<br />
if (A == Fortune.VVInfinite)<br />
A = VE.FixedPoint  10 * VE.DirectionVector;<br />
if (B == Fortune.VVInfinite)<br />
B = VE.FixedPoint + 10 * VE.DirectionVector;<br />
Simple .
Cheers, Ben.






Crap! I hate to say this, but I tested the implementation with some random point sets, and sometimes a vertex is not found. Try this set, Ben! (20 points)
Point(0.3692434, 0.07671795)
Point(0.3255264, 0.3873076)
Point(0.1713028, 0.2256131)
Point(0.2075872, 0.06491974)
Point(0.1658398, 0.3280339)
Point(0.3723957, 0.4436001)
Point(0.2516395, 0.4356501)
Point(0.2152362, 0.1000157)
Point(0.2024738, 0.09652914)
Point(0.306734, 0.04758105)
Point(0.4167807, 0.2370589)
Point(0.1958051, 0.04800395)
Point(0.250089, 0.4712972)
Point(0.1643453, 0.1943359)
Point(0.3176289, 0.07668655)
Point(0.1188253, 0.2242593)
Point(0.4266324, 0.1413706)
Point(0.4631779, 0.2715097)
Point(0.006187368, 0.1215192)
Point(0.2943592, 0.2725327)
Again, good luck!




