15,885,767 members
Articles / Web Development / HTML
Tip/Trick

# A Polygon-triangulation Algorithm with Time Complexity O(N*logN)

Rate me:
16 Jan 2016CPOL4 min read 31.1K   710   31   6
This tip will introduce a library written in C++ that wraps up a 2d polygon triangulation algorithm with time complexity of O(N*logN), the algorithm works on both self-intersected and non self-intersected polygons.

The dependant.zip or dependant.rar is the environment for building testing application running on Windows, to know more in detail, please refer to readme.txt in compressed file redistribution.rar or redistribution.zip.

## Introduction

The algorithm introduced in this tip and provided in C++ code has time complexity of O(N*LogN), the basic idea is from here, sweepling line is pivotal, and sweepling line enables computer vision for triangulating the polygon. In addition, this algorithm provides a solution for self-intersected polygon and with correspondingly 2 ways of triangulation, one for even-odd fill mode, the other is for winding fill mode. For more details, please refer to libtriangulation.h.

The image above shows the testing application of this algorithm running on Windows, all the testing functions can be initivated by the buttons on the toolbar, buttons marked as "`I`", "`F`", "`D`" are for testing triangulation algorithms corresponding to data type of "`integer`", "`float`", "`double`" respectively, button marked as "`E`" and "`W`" are for setting the fill mode to be "`even-odd`" and "`winding`" respectively. Lastly, button marked as "`A`" is for initiating a built-in case test. To use this application: Firstly, use mouse to create a polygon, Secondly, set the fill mode with button either marked as "`E`" for even-odd or marked as "`W`" for winding, thirdly press button "`I`", "`F`" or "`D`" to run the triangulation algorithm with polygon input generated by mouse and with preset fill mode, then in the left view, it draws the expected filled polygon and in the right it draws the triangles generated by the algorithm; the left view is painted by GDI, and the right view is painted by OpenGL, since the coordinate system of OpenGL supports floating points, therefore it can sufficiently test on this algorithm. when an item in the list view is selected, then the corresponding triangle will be highlighted in red. Technically, this algorithm supports all the signed number data type, however, practically it works the best with the maximum precise data type----`double` type. By comparison of the left and right view optically, we can confirm if the algorithm works correctly.

## Background

Polygon triangulation is an important topic in 2d computer graphics, working with triangles is more convenient than working with various kinds of polygons, as an extension triangle also defines a plane, therefore it is geometrically significant for 3d graphic engines, furthermore the OpenGL and direct3d are making triangle as one of their graphical primitives. Motivation of this algorithm is for optimizing the polygon rending by utilizing the graphical hardware, hence OpengGL is one of the options, using this algorithm triangulates the polygon, and generates the triangles, and then send the triangles away to the graphical hardware with OpenGL, to maximally utilize the graphical hardware. The interface of the algorithm is designed seamlessly for graphical engine, with 2 types of polygon fill-mode supported, one is `Even-Odd`, the other is `Winding`. For more information about these 2 types of filling mode, you can refer to this link for winding, and this link for even-odd.

## Using the Code

The triangulation algorithm is wrapped in a standalone dynamic link library, the interface of the library is defined in file libtriangulation.h (\$Package\libtriangulation\triangulation\src\libtriangulation.h). Using the library can be depicted in the following pseudo code:

C++
```Polygon2D_f polygon;
Triangles_f *triangles = NULL;
polygon.num = 3
polygon.points = new Point2D_f[3];
polygon.points[0].x = 0;
polygon.points[0].y = 0;
......
//for initializing the points of the polygon,
//polygon is defined as a sequence of the points{p0, p1, p2 ... pn, p0}

if (GenerateTriangles_f(&polygon, Even_Odd, &triangles) > 0)
{
//access each triangle here
for (unsigned int i_tri = 0; i_tri < triangles->num; i_tri ++)
{
const Point2D_f &pt1 = triangles->pts[i_tri][0]; //the first point of the triangle
const Point2D_f &pt2 = triangles->pts[i_tri][1]; //the second point of the triangle
const Point2D_f &pt3 = triangles->pts[i_tri][2]; //the second point of the triangle
}
ReleaseTriangles_f(triangles);
}

delete [] polygon.points;
polygon.points = NULL;
polygon.num = 0;```

For more information about how to use the library through the interface, please refer to ListPoints_i.h, ListPoints_i.cpp (in folder tester_win), particularly to function `CListPoints_i::GenPolygon_f`, this function converts the MFC list of points to `Polygon2D_f`; or the file mock_vega.h, mock_vega.cpp, cases.h which works on linux.

It's recommended to use `tester_win` to learn, test, and evaluate the algorithm; `tester_win `runs on Windows 7.0 with OpenGL 3.0 minimally. Once the algorithm works abnormally (comparing the left view and right view, it has obvious difference), then save the file as a case, and send it to wwxhero@163.com, so that I can analyze it later.

## Points of Interest

The calculation error can overturn the logic, the theoretical stance of this algorithm was neglect to CPU calculation error, and this issue is critical especially with data type “`int`”, and for the cases the algorithm failed to triangulate the polygon are mostly caused by calculation error, therefore the implementation of the algorithm should use the logic calculation to replace arithmetic calculation if possible. While for the cases that the algorithm fails, please save the testing data to a file and send it to wwxhero@163.com.<o:p>

The algorithm will have poorer performance if there are dense points in a small region than the rasterization algorithm.

## History

• 24th Jan, 2016: Bug fix: For the multiple overlapping edges intersecting in a single vertices geometrically, the winding number is not correctly calculated.
• 24th Jan, 2016: Port latest update to linux
• 17th Jan, 2016: Code complete for winding mode triangulation
• 10th Jan, 2016: Do not offset vertices during re-routing in order to avoid calculation based on error values
• 6th Jan, 2016: Bug fix: intersection test in even-odd mode
• 14th June, 2015: Initial version

Written By
Student
United States
Over 10 years working experience on computer programming in c/c++

I'm interested in computer graphics, and the related fields.

I have been benefited from this site, and other Open source community for years, and it is my turn to contribute back.

Data visualization is the pivot for computer graphics application, I am going to develop the basic tools to visualize the 3d data, from static to animation on Windows with OpenGL or DirectX. I will wrap the core part into a library portable to other platforms and make those libraries open and free to use.

Once I am able to manipulate the data, rendering the data, then everything in the 3d world is open to me, and I am stepping in.

Thanks to my employer Beijing Pencho Pai Fashion Technology, for offering the opportunity on 3d graphics application development, the true commitment will come in 2016

 First Prev Next
 Message Closed 17-Jan-16 2:15 Member 10891848 17-Jan-16 2:15
 Last Visit: 31-Dec-99 18:00     Last Update: 25-Apr-24 3:16 Refresh 1