CodeProject: Polygon Triangulation. Free source code and programming help

Report Article

Discuss

Send to a friend

26 votes for this Article.

Popularity: 5.71 Rating: 4.04 out of 5

Introduction

HGRD is a code for triangulation of a polygon with or without holes. It can triangulate and also deal with many disconnected polygons treated as a single one (see figure with the triangulation of Norway border line). The algorithm is based on Delaunay triangulation. One of the main problems was to keep complexity order as low as possible (N log N) so tree structures (i.e., STL map) are used in critical parts. Thanks to this, it was possible to triangulate a complex polygon with around 40000 nodes within 6s (Athlon 1.4GHz DDR 266).

Using the code

The class HPolygon encapsulates functionality of a class HGrd which is responsible for triangulation. HPolygon provides also simple import and output of data (the syntax of input and output files are described inside 'readme' attached to the zip file with the code). Hopefully, this should make usage of the triangulator quite easily especially if you want to build the code into your application.

The demo is a console application which takes as arguments the names of input and output files. The output file can be used in Amtec Tecplot visualization software (not so readily available) but can be easily transformed to other formats.

Any feedback will be highly appreciated.

History

July 28, 2005: I have decided to release the hgrd under GNU Lesser General Public License.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

_qqq_

Occupation:	Researcher
Location:	Poland

Other popular Algorithms & Recipes articles:

Symbolic Differentiation
This article demonstrates differentiating expressions using a stack and displaying the input expression and its derivative.
Manipulating colors in .NET - Part 1
Understand and use color models in .NET
C#: A-Star is born
Understand graphs and A* path-finding algorithm with C#
State of the Art Expression Evaluation
A tutorial on how to realize an expression evaluator in CSharp with ANTLR
Fast mathematical expressions parser
Code for a fast math parser library.

Article Top

You must Sign In to use this message board.

Msgs 1 to 25 of 44 (Total in Forum: 44) (Refresh)

FirstPrevNext

Subject

Author

Date

Another uninitialized variable

ultimatenexus

0:48 24 Apr '08

I got some really bad triangulation errors triangulating a point cloud NOT as polygon compiling with VC6.

The Problem is the mInd in HGrdPnt.
You are not always setting the Index through rIndex() properly.
In Debug-Mode everything works fine because all int are initialized the same, which was apparently enough.
In Release Mode everything is uninitialized and occasinally the uninitialized int's were set to an valid index.
So mInd schould be initialized with INT_MIN or something similar, so you can determine which triangles are valid in release mode, too. just like this:

   
if (
   HgrdPolygon->mtabCell[i].Index(0) < NrOfPoints  && 
   HgrdPolygon->mtabCell[i].Index(1) < NrOfPoints  &&
   HgrdPolygon->mtabCell[i].Index(2) < NrOfPoints 
   )

I hope anyone understands what I am trying to tell. Its explained a bit confused... Smile

It doesent work "out of the box"?

Throred

4:41 29 Jan '08

Hi!

At first glance this piece of code looks great. However after a day of testing, debugging etc, I have but one question.

I modified the main function acording to the instructions. My changes are shown below:

int main( int argc, char *argv[])
{
try
{
HPolygon poly;

/* if ( argc != 3 )
{
printf ( "usage: hgrd [input file with points] [output tecplot file]\n");
return 1;
}*/

poly.Init( "data/ci_hynet.pnt");
poly.Triangulate();
poly.WriteTEC( "data/output.dat");
}
catch ( Except *pe)
{
ASSERT( pe);
TRACE_EXCEPTION( *pe);
TRACE_TO_STDERR( *pe);
delete pe;
}

return 0;
}

Perhaps im just doing it wrong? In any case, the feedback in cmd window is as follows:
"Reading file: data/ci_hynet.pnt"
"Triangulation started"

And nothing happens.. What am I doing wrong?

I did try several more severe modifications, and had several obstacles in my way. Got it to work somehow, but still got the wrong output.

3.00/5 (1 vote)

Compile Errors (GCC 4.1.1)

pmacko

13:31 25 Sep '07

I am getting similar errors to those described in an earlier post about VS2005 errors:

src/hgrid.h:99: error: default argument for parameter of type ‘const std::_List_iterator&’ has type ‘int’
src/hgrid.h: In member function ‘void HGrdTri::DumpTri()’:
src/hgrid.h:193: error: no match for ‘operator!=’ in ‘HGrdTri::Cell(((const MGInt&)((const MGInt*)(&0)))) != 0’
/usr/lib/gcc/i386-redhat-linux/4.1.1/../../../../include/c++/4.1.1/bits/stl_list.h:173: note: candidates are: bool std::_List_iterator<_Tp>::operator!=(const std::_List_iterator<_Tp>&) const [with _Tp = HGrdTri*]
...

Is there any fix for this? (The fix for VS2005 doesn't work here.)

Thanks!

5.00/5 (1 vote)

i am just a biginer

pushn

8:11 10 Jul '07

hey i was wondering if u could help me get started up for triangulation . i am trying to implement triangulation as a project in my college . but i dont have any thing to study or no refrence algorithm . i would be greatful if u could help me . i dont want u to spoon feed me but just point me in the right direction .. thanks . pp
Sign In·View Thread·PermaLink

Compile Errors VS2005 [modified]

arkuhl

18:43 23 Apr '07

The code compiles fine in Debug mode, but when compiling in Release mode I get the following:

hgrid.h(99) : error C2440: 'default argument' : cannot convert from 'int' to 'const HGrdTri::IterGCell &'
Reason: cannot convert from 'int' to 'const HGrdTri::IterGCell'
No constructor could take the source type, or constructor overload resolution was ambiguous

The line corresponding to the error is "IterGCell NextCell( HFroSeg *pseg, const IterGCell& iclprv=NULL);"

If I remove the =NULL part it sets off a bunch of other errors all concerned with either default arguments or comparisons using NULL.

If I just run in debug mode, it will get to "if ( Cell(0) != NULL)" in HGridTri::NextCell and throw an error. "Debug Assertion Failed... [filepath]\list... Line: 309... Expression: list iterators incompatable"

Ran the included demo in debug mode (without following it with breakpoints like above) and it bailed and wrote a blank trace.txt.

Any ideas?

-- modified at 19:58 Tuesday 24th April, 2007

2.00/5 (1 vote)

Re: Compile Errors VS2005

_qqq_

22:28 24 Apr '07

At this moment I don't see an easy and fast solution. I think that it can be solved by adding to the list (e.g. at the begining of the list) a dummy invalid element. The iterator to this element should be then used instead of NULL.
Sign In·View Thread·PermaLink	2.00/5 (3 votes)

Re: Compile Errors VS2005 : A solution

DevRX

10:33 30 Jul '07

Hello,

Normally, using NULL for iterators seems not to be allowed.

Nevertheless, the solution for compiling is to add :

//See  http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1413506&SiteId=1
#ifndef _HAS_ITERATOR_DEBUGGING
#define _HAS_ITERATOR_DEBUGGING 0
#endif
#ifndef _SECURE_SCL
#define _SECURE_SCL 0
#endif

in the beginning of stldecl.h file (just after #ifndef __STLDECL_H__
#define __STLDECL_H__ and before #include )

Theses 6 lines allows compiling to work fine.

Regards,

DevGisRX

Re: Compile Errors VS2005

DevGisRX

10:36 30 Jul '07

Hello,

Normally, using NULL for iterators seems not to be allowed.

Nevertheless, the solution for compiling is to add :

//See  http://forums.microsoft.com/MSDN/ShowPost.aspx?PostID=1413506&SiteId=1
#ifndef _HAS_ITERATOR_DEBUGGING
#define _HAS_ITERATOR_DEBUGGING 0
#endif
#ifndef _SECURE_SCL
#define _SECURE_SCL 0
#endif

in the beginning of stldecl.h file (just after #ifndef __STLDECL_H__
#define __STLDECL_H__ and before #include )

Theses 6 lines allows compiling to work fine.

Regards,

DevGisRX

3d fragmentation

Shokker12

3:32 11 Jan '07

Hi! Nice code. Can I modify algorithm to make a volume fragmentaion (3d) with tetrahedron as simplex element?
Sign In·View Thread·PermaLink	1.50/5 (2 votes)

Re: 3d fragmentation

_qqq_

4:13 11 Jan '07

Sure, you can but it will be IMHO much easier to write this from scratch and even then it will be not easy...
Sign In·View Thread·PermaLink	1.00/5 (1 vote)

how to insert one point ?

e_ilite

17:09 19 Dec '06

how to insert one point ?
Sign In·View Thread·PermaLink

Re: how to insert one point ?

_qqq_

4:10 11 Jan '07

I don't know what exactly you mean but I guess that you want to insert additional points laying inside a domain. To do this you should store the points inside a collection CollGPnt and then add them by calling InsertPointIntoMesh(...). Adding inner points should be done in Generate function after FlagOuterTris(). Hope it helps and I have not forgotten anything essential...
Sign In·View Thread·PermaLink	2.00/5 (1 vote)

Errors in vect.h

aunghtet

7:00 3 Aug '06

Hi I have taken the hgrd_demo and when I compiled it in Microsoft visual c++ 6.0 I experienced with many error messages. All the errors are from the head file vect.h . I appreciate if you give the solution of the problem. thanks
Sign In·View Thread·PermaLink	1.86/5 (5 votes)

Co-linear line segments

Jon Evans

23:48 27 Jul '05

Hi have just found a slight problem where the code asserts due to a shared edge. I'm looking into it but if anyone else wants to have a go also, here is the test file I used

co_lin_squares.pnt

2
5
0 0
10 0
10 10
0 10
0 0
5
10 2
16 2
16 8
10 8
10 2

The best way to fix it that I have found so far is to split the longer co-linear line segment into 3 sections giving the following file

2
7
0 0
10 0
10 2 <--- These two points
10 8 <--- are duplicates...
10 10
0 10
0 0
5
10 2 <-- ...of these two
16 2
16 8
10 8 <--
10 2

Looks like co-linear points may have to be checked for and added to automatically split up line segments.

1.75/5 (4 votes)

Nice code :).. to bad it's GPL.

Anonymous

5:14 13 Jun '05

Nice bit of code. Too bad GPL renders it fairly useless to those of us who like to make money with our code .
Sign In·View Thread·PermaLink	5.00/5 (3 votes)

Re: Nice code :).. to bad it's GPL.

tsohg

11:43 15 Jun '05

I, too, was sad to see that this is GPL. Changing the license to be LGPL, rather than GPL would probably make it more palatable to people who are interested in using it in their own projects. Just a suggestion
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

_qqq_

0:09 4 Jul '05

Any more votes? Maybe I will rethink licensing
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

Duduff

7:44 27 Jul '05

Hi So what news for the LGPL Licence? because it's a very nice code and il will be interesting for me if it is LGPL
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

Armel Asselin

23:51 2 Aug '05

LGPL would be very nice for me too
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

itouh2

1:26 4 Aug '05

me too.
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

andrzej.bol

1:56 25 Mar '07

me too ))
Sign In·View Thread·PermaLink	5.00/5 (1 vote)

Re: Nice code :).. to bad it's GPL.

doojoo

17:27 13 Sep '07

LGPL is better for me
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

Leonnik

10:15 24 Oct '07

Free for all!!! LeonniK®
Sign In·View Thread·PermaLink

Re: Nice code :).. to bad it's GPL.

Albertino

8:29 12 May '08

why not LGPL?
Sign In·View Thread·PermaLink

Practical use

Stas Desyatnikov

2:52 12 May '05

Dear _qqq_, Can you please add a section to your article on a practicle use of tringulation (at least just for noobs like me). I know that this is how textures are applied to compex 3D models but I'm also interested in 2D uses. Stas.
Sign In·View Thread·PermaLink	1.67/5 (2 votes)

Last Visit: Tuesday, July 8, 2008 5:50 PM Last Update:Tuesday, July 8, 2008 5:50 PM

1 Next »

General News Question Answer Joke Rant Admin