Add your own alternative version
Stats
214.4K views 3.6K downloads 111 bookmarked
Posted
26 Dec 2001

Comments and Discussions


You should warn that the Delaunay implementation is based on very slow O(N³) exhaustive search and should be used for small N only. (Not mentioning the typo k = i + 1 .)





What would you suggest as a faster alternative? I used this class in my PhD work 20 years ago and it was more than fast enough on a 486 with several thousand triangles, but obviously for today's applications we'd be looking at orders of magnitude more triangles.
(Where's the typo? I'll make the fix)
cheers
Chris Maunder





Is it possible to add support for linear regression?





When I compiled this with VS2005 it had several warnings about deprecated functions. I could have switched them off but I felt it better to upgrade the code to use the new variations, like fscanf_s etc..
Are you planning on making this alteration so that this super class is V8 compliant without any changes to building behavior?
Thanks.
Andrew





Sometimes, the CPoint3D object returns has negative coordinates and is not the center of the shape. Why?





andrewtruckle wrote: negative coordinates
That depends on how you define the "centre". Also, negative or positive is only relative. If you're polygon extends over an axis then you may get negative coords. If not then maybe it's a bug. Have you stepped through the code to see what's happening?
cheers,
Chris Maunder
CodeProject.com : C++ MVP





To be honest it is over my head. As I understand it, your method returns the center of gravity and not a literal point inside the polygon shape.
This is my problem.
Thanks for any help.
Andrew





Ah  unfortunately they are two different things. Sorry.
cheers,
Chris Maunder
CodeProject.com : C++ MVP





Pity. Is there no way you can consider such an implementation by using an average of the vertices and nudging the point by a distance and angle until it falls inside or something? It would be nice to have something support via this class if possible.
Andrew





The centroid (centre of gravity) does not necessarily fall within the bounds of the polygon.
Andrew Phillips
http://www.hexedit.com
andrew @ hexedit.com





Yes, I am no maths guru here but I picked up that the center of gravity can be outside the polygon depending on it's shape.
However, I wanted a centroid routine that gave me the cosmetic(?) centroid (ie: visually in the center).





How do you define the 'cosmetic' centre? Think about an assymetrical figure '8'  how would you define the 'centre' of that?
One thing you might look into is an algorithm that finds the centre of the largest circle that will fit entirely within the polygon. If you come up with one I'll be happy to add it to this library
cheers,
Chris Maunder
CodeProject.com : C++ MVP





Well, I am thinking in terms of shapes that build areas and that don't intersect so a figure of 8 would not apply.
For now this is not an issue for me since it was a year ago. We probably agreed to leave it as it was.
Andrew





I'm developing a C# library to draw diagrams. I need a method to test if a point is inside a polygon. I've adapted your C++ version to C#, and it works great!
Thank you, it saves me a lot of time.





Hi,
The NaturalSpline function seems to give odd results sometimes.
Check out the following:
CPolygon p;
p.Add(C3Point(1875, 930, 0));
p.Add(C3Point(1868, 618, 0));
p.Add(C3Point(1990, 465, 0));
double *b, *c, *d;
p.NaturalSpline(b, c, d);
for(double x1 = 1875; x1 >= 1868; x1 = 1) {
double x = x1  1875;
double y = x * x * x * d[0] + x * x * c[0] + b[0] * x + 930;
cout << "x=" << x1 << " y=" << y << "\n";
}
cout << "\n";
for(double x1 = 1868; x1 <= 1991; x1 += 4) {
double x = x1  1868;
double y = x * x * x * d[1] + x * x * c[1] + b[1] * x + 618;
cout << "x=" << x1 << " y=" << y << "\n";
}
delete []b; delete []c; delete []d;
The results for the second line segment seem way off:
Here's the output:
x=1875 y=930
x=1874 y=886.795
x=1873 y=843.419
x=1872 y=799.701
x=1871 y=755.471
x=1870 y=710.558
x=1869 y=664.792
x=1868 y=618
x=1868 y=618
x=1872 y=797.984
x=1876 y=959.468
x=1880 y=1103.08
x=1884 y=1229.44
x=1888 y=1339.19
x=1892 y=1432.95
x=1896 y=1511.34
x=1900 y=1574.99
x=1904 y=1624.53
x=1908 y=1660.59
x=1912 y=1683.8
x=1916 y=1694.77
x=1920 y=1694.15
x=1924 y=1682.55
x=1928 y=1660.6
x=1932 y=1628.93
x=1936 y=1588.17
x=1940 y=1538.94
x=1944 y=1481.87
x=1948 y=1417.59
x=1952 y=1346.73
x=1956 y=1269.9
x=1960 y=1187.75
x=1964 y=1100.9
x=1968 y=1009.96
x=1972 y=915.584
x=1976 y=818.38
x=1980 y=718.982
x=1984 y=618.017
x=1988 y=516.11
Although the final number converges to the third point, the intermmediate points create a very nasty looking curve.
Can you help?





I'm playing with 3D trianglepolygons and I would like to have a function that determines if they intersect.
I hoped this class could do that, but when I looked at the code it's only using the x and y in C3Point, so it doesn't.
How do I determine intersects in 3 dimensions?





Has anybody developed code using these classes to determine the point coordinate of the intersection of two line segments, not just whether they intersect? Unless I am missing something, this capability is not implemented. If somebody has done so, I would appreciate a posting.
Thanks in advance.
Dick Males





Subtract CPolygon from CPolygon
Is there some easy way to subract one CPolygon from another bigger one?
_____________________________
...and justice for all
APe





hi,
I can't seem to find the colinear method you use?
(btw i don't use MFC)





Hey Chris,
That's exactly what I was looking for.
I used MacMartin's XRay algorithm and some own math code stuff before but your collection is just the best I've seen so far.
Many thanks for that great job you did!
Frank.





I think these classes are great but how can I use them in a nonMFC application? Whenever I try to compile the files, I get errors about not finding the identifier BOOL and all the MFC functions.
Anyone know?
Thanks!
TCMaster





BOOL is not MFC and is defined in the Windows SDK. Include windows.h...
John





Thanks John.
What about ASSERT? Can I just include <assert.h>?





You could just define it as
#define ASSERT(f) ((void)0)
and it will be ignored. ASSERTs are compiled this way in release code normally.
Ant.





I think assertion check might not be the thing to be got rid of, since it's always useful for debugging. So we could use this instead:
<pre>#ifndef __AFX_H__ // if nonMFC<br />
#include <assert.h><br />
#define ASSERT(x) assert(x)<br />
#endif</pre>
Just add above block to the beginning of your C++ file and you can still have assertion check in your nonMFC applications.





thks for ur presentation.
but i found a problem. when i try to conduct Delaunay triangulation. The result triangle mesh is not unique. some are intersected. can u help me ?
thank u very much!
Learn from each other and improve together.





How do I get the delaunay triangulation of a set of points using the above classes?
thanks





Try one in www.3djockey.com
Recently I have completed code for Constrained Delaunay Triangulation(CDT).
The code posted in www.3djockey.com is one I made quite long time ago.
The code may have bugs but still works quite well for Delaunay Triangulation.
Later when I have time, I will post codes for CDT, which I am using now for my own application.
Enjoy the code!;)
Youngsub Ahn





ysAhn:
How do you do .
I am a gis student from Taiyuan of China.
How I can get the source code of Delaunay Triangulation to learn?
I cann't open the www.3djockey.com web site
Can you email to me . Thanks very much .
My email :zqf2099@sina.com ;





ysahn:Thanks very much for your email .And the web site you afford
is very good. I will go there frequently.
Now I am going to do some map generalization using Constrained Delaunay trianglation ,I want to do some simple examples,but my VC++ is poor ,so I must study some source code to do it ,So I am sincerely expected for your help, thanks very much!






Have you a sample to use naturalspline? or a help file
Thank you





please give me a sample to get norm and Curvature of each POINT!
thanks a lot!





Please, Inform DelaunayTri function directions.
//////////////////////////
CPolygon poly1, poly2;
C3Point p1(0.0, 0.0, 0.0);
C3Point p2(100.0, 0.0, 0.0);
C3Point p3(100.0, 100.0, 0.0);
C3Point p4(0.0, 100.0, 0.0);
C3Point p5(50.0, 50.0, 0.0);
C3Point p6(0.0, 0.0, 0.0);
poly1.Add(p1);
poly1.Add(p2);
poly1.Add(p3);
poly1.Add(p4);
poly1.Add(p5);
poly1.Add(p6);
poly1.DelauneyTri(&poly2);
int cnt = poly2.GetSize();
poly2.Save(_T("D:\TEST.DAT"));
////
Error happens in upside sentence.Ask certainly.





Post a demo app so we can play too Chris
bryce





Very good,
much completed than the Vector class of Direct X 3D.
And something more,
Did you know any site where i can find information
about what the DotProduct and what the CrossProduct is?
                 
Memory leaks is the price we pay \0
01234567890123456789012345678901234





Dr. Math.com
Build a man a fire, and he will be warm for a day Light a man on fire, and he will be warm for the rest of his life!





CPolygon prc;
prc.Add(C3Point(0.45, 0.59, 0));
prc.Add(C3Point(0.45, 0.83, 0));
prc.Add(C3Point(0.67, 0.59, 0));
prc.Add(C3Point(0.67, 0.83, 0));
BOOL b = prc.PointIn(C3Point(0.55, 0.66, 0.0 )); // b = 0;
That stuff doesn't work.





The stuff does work. The problem with your code is that the order of points is significant. I believe that you tried to create a square  however you actually created a "bowtie" shape. Therefore your test point is outside the polygon. Rearranging the order of declaration as follows shows the expected result:
CPolygon prc;
prc.Add(C3Point(0.45, 0.59, 0)); // lower left
prc.Add(C3Point(0.45, 0.83, 0)); // upper left
prc.Add(C3Point(0.67, 0.83, 0)); // upper right
prc.Add(C3Point(0.67, 0.59, 0)); // lower right
BOOL b = prc.PointIn(C3Point(0.55, 0.66, 0.0 )); // b = 1;
Graham





...that we all write some intriguingly similar stuff at times!
When I first joined our company three and a half years ago one of the first things I wrote was a library (called the Geometric Model) for describing shapes and coordinate frames in 2 or 3 dimensions (for our Pharos acoustic tracking system), modelled loosly on the object hierarchy of OpenGL and Direct3D.
Since it is intended to describe shapes rather than for computational geometry, the focus is different, although the domain is the same.
We planned from day 1 to include 3D rendered displays so you could follow an ROV around the seabed in realtime alongside the more conventional 2D Chart Displays, but apart from a few demos we still haven't released that bit...and even the 2D stuff hasn't been stretched yet (we haven't included a shape editor yet).
Still, it's a pretty interesting area to work in (I never did think I'd find a use for matrices, but I was wrong...)
Andy Metcalfe  Sonardyne International Ltd
Trouble with resource IDs? Try the Resource ID Organiser AddIn for Visual C++ 5.0/6.0
"I'm just another 'S' bend in the internet. A ton of stuff goes through my system, and some of the hairer, stickier and lumpier stuff sticks."
 Chris Maunder (I just couldn't let that one past )





We used to rely on an XWindow 2D graphics engine written in Fortran that only worked on AIX's and Suns. Finally I spat the dummy and sat down to write a decent 3D version. We needed to view landscapes with overlays of wetness, erosion, vegetation etc and then view the results of rainfall and erosion simulations. It was such a buzz to get it done and be able to do flyovers of the hillslopes in fully shaded 3D.
It was also great proving that my C++ code on my $2,000 PC was faster at running the simulations and displaying the final results than their $15,000 workstations
cheers,
Chris Maunder





Chris Maunder wrote:
We used to rely on an XWindow 2D graphics engine written in Fortran that only worked on AIX's and Suns. Finally I spat the dummy and sat down to write a decent 3D version. We needed to view landscapes with overlays of wetness, erosion, vegetation etc and then view the results of rainfall and erosion simulations. It was such a buzz to get it done and be able to do flyovers of the hillslopes in fully shaded 3D.
Although I'm anything but a mathematician, I found this stuff fascinating when I first came across it (heck, I even relearned matrix maths for it )...so I can imagine!
Chris Maunder wrote:
It was also great proving that my C++ code on my $2,000 PC was faster at running the simulations and displaying the final results than their $15,000 workstations
Oh I bet it was! I'm sure there were a few red faces when you showed them the final result...
Andy Metcalfe  Sonardyne International Ltd
Trouble with resource IDs? Try the Resource ID Organiser AddIn for Visual C++ 5.0/6.0
"I'm just another 'S' bend in the internet. A ton of stuff goes through my system, and some of the hairer, stickier and lumpier stuff sticks."
 Chris Maunder (I just couldn't let that one past )





These are very useful classes.
I also recommend taking a look at the C++ port of Java's vecmath package. It's clean, efficient, and very well designed.
CoolDev






General News Suggestion Question Bug Answer Joke Praise Rant Admin Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

