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

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.

• You haven't clearly described which triangles you need. Can you draw on your Andromeda diagram the set of triangles that you want your algorithm to produce? Jun 5, 2016 at 14:40
• Yes, I think. I can add a link to the software I'm going to use to make more clear what I need. I will add it. Jun 5, 2016 at 14:42
• That link doesn't help me (it may help others). I would like to see a picture of the expected output for Andromeda. Jun 5, 2016 at 15:36

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:

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

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


• Thanks for your answer. I have checked txt file and it has vertices sorted. It starts on the bottom right corner, and continue to the top right corner, and then to the left. Given the above image of Andromeda's constellation boundary polygon, it could be possible to do a polygon triangulation with it? The polygon has steps and I'm not sure if I could do a triangulation with those steps. Jun 6, 2016 at 12:23
• @VansFannel, if the vertices are ordered and form a simple polygon, then yes, because every simple polygon can be triangulated using diagonals. If you post your data somewhere public I can give you a triangulation. If you can use Python, see dzhelil.info/triangle.
– lhf
Jun 6, 2016 at 12:28
• I have updated my question adding the points for the and.txt files in a 3D space. It's a 2D plane draw in a sphere surface. Jun 7, 2016 at 7:30
• Did you do it with Triangle: A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator? I ask you this because it says that it is a Two-Dimensional and I have a 3D space. My apologies for this question, but I want to make sure what algorithm have you used. And thanks a lot for your time and help. Jun 8, 2016 at 7:01
• @VansFannel, yes, I dropped the $z$ coordinate and used Triangle on the projected points.
– lhf
Jun 8, 2016 at 11:32