Divide a 2D polygon with N vertices into triangles draw in a 3D space

Question

I'm developing a C++ software and I have a problem with a polygon with N vertices.

I have a set of N vertices unordered. This vertices describe an polygon.

I'm developing a planetarium and I want to draw constellations area in a 2D plane. For example, this Andromeda's constellation:

Picture taken from International Astronomical Union.

I'm using a software that needs the set of vertices and a set of triangles. I have to use these vertices to create triangles. In other words, I have to divide the polygon into a triangles.

I don't know how can I do it and I don't if it is a problem to have the vertices are unordered.

How can I divide a polygon with N vertices to M triangles using its vertices (doesn't create new ones)?

You can find an example of what I need here.

I will need an Index set indicating which vertices make up each triangle. Length must be a multiple of 3.

UPDATE

I have translated the data on and.txt to points in a 3D space:

{X=4396.37256 Y=-6379.14014 Z=1994.61243 }
{X=5500.31494 Y=-4671.09717 Z=3453.60474 }
{X=5113.30176 Y=-4762.04297 Z=3895.77808 }
{X=4968.60693 Y=-5036.05127 Z=3735.12256 }
{X=4747.05127 Y=-5056.14600 Z=3987.59253 }
{X=4615.38721 Y=-5269.29980 Z=3864.28223 }
{X=4076.43237 Y=-5229.03613 Z=4476.59229 }
{X=3918.59326 Y=-5434.22998 Z=4371.92969 }
{X=3260.70557 Y=-5214.97998 Z=5115.83594 }
{X=3442.72559 Y=-5017.84033 Z=5193.16064 }
{X=3223.62085 Y=-4900.48145 Z=5439.99512 }
{X=3410.07349 Y=-4701.84912 Z=5501.27393 }
{X=3204.70435 Y=-4568.61865 Z=5732.15430 }
{X=2966.23413 Y=-4382.50098 Z=5999.59473 }
{X=2657.99683 Y=-4658.74365 Z=5935.58398 }
{X=2356.95288 Y=-4370.98047 Z=6272.10498 }
{X=2736.06909 Y=-4066.88452 Z=6322.52930 }
{X=2407.01880 Y=-3669.90308 Z=6688.65234 }
{X=786.989624 Y=-4663.76953 Z=6452.12354 }
{X=1239.70874 Y=-5203.95654 Z=5948.27344 }
{X=1038.41187 Y=-5324.36963 Z=5879.86279 }
{X=1621.91162 Y=-5835.39307 Z=5226.62354 }
{X=1404.58948 Y=-5979.09863 Z=5126.15918 }
{X=2158.56323 Y=-6406.69336 Z=4277.25195 }
{X=1204.28198 Y=-7013.12695 Z=3655.92017 }
{X=1041.70898 Y=-6940.75293 Z=3839.37378 }
{X=747.571716 Y=-7085.02002 Z=3639.17993 }
{X=1643.21338 Y=-7375.80713 Z=2626.27490 }
{X=1744.26733 Y=-7323.22510 Z=2707.00928 }
{X=1840.00928 Y=-7339.11426 Z=2598.41602 }
{X=2429.56323 Y=-6976.63086 Z=3069.82886 }
{X=2510.73877 Y=-6987.80615 Z=2977.71021 }
{X=2824.51831 Y=-6752.74512 Z=3228.39502 }
{X=3119.60718 Y=-6774.78857 Z=2893.14551 }
{X=3186.54883 Y=-6718.54443 Z=2950.77417 }
{X=3479.27539 Y=-6711.39160 Z=2617.60718 }
{X=3683.21411 Y=-6522.57178 Z=2808.91260 }

It's a 2D plane in a 3D space. I'm drawing the plan on a sphere surface.

Answer 1

There are several algorithms for polygon triangulation but you need to order the vertices first, because different orders may give different polygons. See for instance:

• Fast Polygon Triangulation based on Seidel's Algorithm.

• FIST: Fast Industrial-Strength Triangulation of Polygons, also here.

• Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.

To order the vertices automatically, you need an algorithm for curve reconstruction:

• Curve Reconstruction

• The Crust Curve Reconstruction Applet

Here are the triangles found with Triangle, one triangle per line:

747.571716  -7085.02002 1643.21338  -7375.80713 1204.28198  -7013.12695
1204.28198  -7013.12695 1041.70898  -6940.75293 747.571716  -7085.02002
1643.21338  -7375.80713 1744.26733  -7323.2251  1204.28198  -7013.12695
1744.26733  -7323.2251  1840.00928  -7339.11426 2158.56323  -6406.69336
2824.51831  -6752.74512 2158.56323  -6406.69336 2429.56323  -6976.63086
2429.56323  -6976.63086 2158.56323  -6406.69336 1840.00928  -7339.11426
3260.70557  -5214.97998 1621.91162  -5835.39307 2158.56323  -6406.69336
1744.26733  -7323.2251  2158.56323  -6406.69336 1204.28198  -7013.12695
1239.70874  -5203.95654 1038.41187  -5324.36963 1621.91162  -5835.39307
786.989624  -4663.76953 1239.70874  -5203.95654 2356.95288  -4370.98047
2657.99683  -4658.74365 2356.95288  -4370.98047 1239.70874  -5203.95654
3260.70557  -5214.97998 2657.99683  -4658.74365 1621.91162  -5835.39307
2356.95288  -4370.98047 2736.06909  -4066.88452 2407.0188   -3669.90308
2407.0188   -3669.90308 786.989624  -4663.76953 2356.95288  -4370.98047
1239.70874  -5203.95654 1621.91162  -5835.39307 2657.99683  -4658.74365
1404.58948  -5979.09863 2158.56323  -6406.69336 1621.91162  -5835.39307
2510.73877  -6987.80615 2824.51831  -6752.74512 2429.56323  -6976.63086
2824.51831  -6752.74512 3119.60718  -6774.78857 3186.54883  -6718.54443
3186.54883  -6718.54443 3479.27539  -6711.3916  3683.21411  -6522.57178
3260.70557  -5214.97998 2824.51831  -6752.74512 3186.54883  -6718.54443
3683.21411  -6522.57178 4396.37256  -6379.14014 3918.59326  -5434.22998
3918.59326  -5434.22998 4615.38721  -5269.2998  4076.43237  -5229.03613
4615.38721  -5269.2998  3918.59326  -5434.22998 4396.37256  -6379.14014
3918.59326  -5434.22998 3260.70557  -5214.97998 3683.21411  -6522.57178
4396.37256  -6379.14014 4968.60693  -5036.05127 4615.38721  -5269.2998
3186.54883  -6718.54443 3683.21411  -6522.57178 3260.70557  -5214.97998
3204.70435  -4568.61865 2657.99683  -4658.74365 3223.62085  -4900.48145
2966.23413  -4382.50098 2657.99683  -4658.74365 3204.70435  -4568.61865
3410.07349  -4701.84912 3204.70435  -4568.61865 3223.62085  -4900.48145
3223.62085  -4900.48145 3260.70557  -5214.97998 3442.72559  -5017.84033
2657.99683  -4658.74365 3260.70557  -5214.97998 3223.62085  -4900.48145
5500.31494  -4671.09717 5113.30176  -4762.04297 4968.60693  -5036.05127
4968.60693  -5036.05127 4396.37256  -6379.14014 5500.31494  -4671.09717
4615.38721  -5269.2998  4968.60693  -5036.05127 4747.05127  -5056.146
3260.70557  -5214.97998 2158.56323  -6406.69336 2824.51831  -6752.74512