Polygon Triangulation

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_

Researcher

Poland

Member

Article Top

Poor

Excellent

Add a reason or comment to your vote: x
Votes of 3 or less require a comment

Comments and Discussions

You must Sign In to use this message board. (secure sign-in)

Search this forum
	Profile popups Noise Layout Per page

error c2440

davood_m

22:12 16 Aug '11

hello, please help 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);"
Sign In·View Thread·Permalink	1.00/5 (1 vote)

Re: error c2440

_qqq_

11:28 8 Sep '11

Well, I am aware of this problem - the code is quite obsolete... Bad news is that at the moment I do not have an easy fix for this. One day when I have a bit more time, maybe I will prepare a new version of the code (an excerpt from the stuff I work on now) which should be ok with regards to the current C++ standard and what is more important, it should be also much faster.
Sign In·View Thread·Permalink	2.00/5 (1 vote)

volume calulation between two surfaces

aser34trw34

1:40 5 Jul '11

Hi, Nice article. i am doing a volume calulation between two surfaces project. Can you provide me the code to calculate volume between two tin files? Please reply me @mamatha.neni@gmail.com
Sign In·View Thread·Permalink

VC2008 Compiler Errors

MeriInssi

0:17 17 Aug '09

Getting some errors:

----------------------------------------------------------



 

1>------ Rebuild All started: Project: hgrd_demo, Configuration: Debug Win32 ------

1>Deleting intermediate and output files for project 'hgrd_demo', configuration 'Debug|Win32'

1>Compiling...

1>mgexcept.cxx

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(52) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(54) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>mgconst.cxx

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(52) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(54) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>main.cxx

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(52) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(54) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>hpolygon.cxx

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(52) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(54) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\hgrid.h(99) : error C2440: 'default argument' : cannot convert from 'int' to 'const HGrdTri::IterGCell &'

1>        Reason: cannot convert from 'int' to 'const HGrdTri::IterGCell'

1>        Constructor for class 'std::list<_Ty>::_Iterator<_Secure_validation>' is declared 'explicit'

1>        with

1>        [

1>            _Ty=HGrdTri *,

1>            _Secure_validation=false

1>        ]

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\hgrid.h(119) : fatal error C1903: unable to recover from previous error(s); stopping compilation

1>hgrid.cxx

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(52) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(54) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\hgrid.h(99) : error C2440: 'default argument' : cannot convert from 'int' to 'const HGrdTri::IterGCell &'

1>        Reason: cannot convert from 'int' to 'const HGrdTri::IterGCell'

1>        Constructor for class 'std::list<_Ty>::_Iterator<_Secure_validation>' is declared 'explicit'

1>        with

1>        [

1>            _Ty=HGrdTri *,

1>            _Secure_validation=false

1>        ]

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\hgrid.h(119) : fatal error C1903: unable to recover from previous error(s); stopping compilation

1>dimension.cxx

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(52) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>c:\c++ projects\drawer\source codes\triangle\polygon triangulation\hgrd_demo\hgrd_demo\mgexcept.h(54) : warning C4996: 'fopen': This function or variable may be unsafe. Consider using fopen_s instead. To disable deprecation, use _CRT_SECURE_NO_WARNINGS. See online help for details.

1>        c:\program files\microsoft visual studio 9.0\vc\include\stdio.h(237) : see declaration of 'fopen'

1>Generating Code...

1>Build log was saved at "file://c:\C++ Projects\Drawer\Source Codes\Triangle\Polygon Triangulation\hgrd_demo\hgrd_demo\Debug\BuildLog.htm"

1>hgrd_demo - 4 error(s), 12 warning(s)

========== Rebuild All: 0 succeeded, 1 failed, 0 skipped ==========

Another uninitialized variable

ultimatenexus

23:48 23 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

3: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.

Compile Errors (GCC 4.1.1)

pmacko

12: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!

Re: Compile Errors (GCC 4.1.1)

codecack

4:56 7 Nov '09

I have the same problem. Does anyone have a fix for that?
Sign In·View Thread·Permalink	2.00/5 (2 votes)

i am just a biginer

pushn

7: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

17: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

Re: Compile Errors VS2005

_qqq_

21: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	1.83/5 (6 votes)

Re: Compile Errors VS2005 : A solution

DevRX

9: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

9: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

2: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_

3: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

16:09 19 Dec '06

how to insert one point ?
Sign In·View Thread·Permalink	1.00/5 (1 vote)

Re: how to insert one point ?

_qqq_

3: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 (2 votes)

Errors in vect.h

aunghtet

6: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.95/5 (12 votes)

Co-linear line segments

Jon Evans

22: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.

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

Anonymous

4: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 (4 votes)

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

tsohg

10: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	2.00/5 (1 vote)

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

_qqq_

23:09 3 Jul '05

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

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

Duduff

6: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	4.00/5 (1 vote)