C++

Forum

 
Detriangulation of Polygon

Bronislaw (22)
Let's assume you have the whole triangulated concave/convex polygon information stored in a container like a vector etc. and want to "detriangulate"=reverse triangulation, so you can find all the edges/corners of it in the right order (clockwise etc.)
How to proceed?

If you remove all duplicates you get all unique edge/corner coordinates, but what about the coordinate points order (important for the whole polygon shape)? How to calculate it, esp. when the polygon can be concave or convex? Is it possible at all?

1
2
3
4
5
6
 
  struct Point { float x, y; };

std::vector<Point> PolygonVector = { {337.8, 657.25},{247.5, 654.25},{260,366.5},{260,366.5},
{347.8,257},{474.5,235},{474.5,235},{816.3,211}, {859.8,372}, {859.8,372}, {838.3,432}, {709,566},
{538,562}, {337.8,657.25}, {260,366.5}, {260,366.5},{474.5,235}, {859.8,372}, {859.8,372}, {709,566},
{538,562},{538,562}, {260,366.5}, {859.8,372} };
Last edited on
ne555 (10692)
¿so you want the boundary of the mesh?

> If you remove all duplicates you get all unique edge/corner coordinates
then you get all boundary edges and vertex
every vertex is connected to other two by the corresponding edges, so start at one vertex (anyone) and do a depth search.


Also, checkout the half-edge structure
Bronislaw (22)
Does a depth search work without adjacency information only with the information from the vector above?
ne555 (10692)
¿you only have the boundary vertices? there would be several valid permutations, so it's ill-defined
but you said that you did have the polygons, so that will give you the boundary edges

try to describe your problem better, so we can give a better solution
¿what information do you have? ¿only points or the triangulation?
¿where does this information come from? ¿what's the format / data structure?
¿what do you plan to do with the border?
Duthomhas (13145)
If I understand you correctly, you have a list of vertices (only!) and wish to turn that into a collection of triangles?

You cannot do this reliably with any concave geometry.

But, assuming a purely convex object (like a cube or sphere or torus, etc) then you can do it, but it requires a fair bit of work.

First, remember that the ORDER of vertices matters when calculating the normal.

I recommend finding the FURTHEST vertex (any random from the set of all equally-furthest vertices will do), then finding the nearest two vertices and adding them to the edge and poly/triangle collections as appropriate -- making sure that the normal has a acute angle with the ray from the object center, coordinate center, or centroid, whichever of the three you are using).

After that you only need to find adjacent tris/polys where the edge normal does not contradict the two surface normals. Repeat until all edges belong to exactly TWO tris.

Good luck!
lastchance (6980)
https://imgur.com/WbPkkDE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct Pt{ double x, y; };
struct Triangle{ Pt A, B, C; };
using Polygon = vector<Pt>;

bool operator == ( Pt a, Pt b ) { return a.x == b.x && a.y == b.y; }
bool operator != ( Pt a, Pt b ) { return !(a == b);                }
Pt   operator -  ( Pt a, Pt b ) { return { a.x - b.x, a.y - b.y }; }
double sq( Pt p ) { return p.x * p.x + p.y * p.y; }
ostream &operator << ( ostream &out, const Pt p       ) { return out << p.x << '\t' << p.y << '\t'; }
ostream &operator << ( ostream &out, const Triangle T ) { return out << T.A << T.B << T.C << '\n'; }
ostream &operator << ( ostream &out, const Polygon P  ) { for ( Pt pt : P ) out << pt << '\n';   return out; }


//======================================================================

                                                     
double area( const Polygon &P )                            // Note: assumes P is CLOSED
{                                     
   double A = 0;
   for ( int i = 1; i < P.size(); i++ ) A += P[i-1].x * P[i].y - P[i-1].y * P[i].x;
   return 0.5 * A;
}


//======================================================================


Polygon fix( const Polygon &P )    // Ensures: (1) no duplicates; (2) closed; (3) traversed anticlockwise
{
   Polygon Q;
   for ( Pt pt : P ) if ( Q.empty() || pt != Q.back() ) Q.push_back( pt );    // remove (successive) duplicates
   if ( Q[0] != Q.back() ) Q.push_back( Q[0] );                               // ensure closed
   if ( area( Q ) < 0 ) reverse( Q.begin(), Q.end() );                        // ensure traversed anticlockwise
   return Q;
}


//======================================================================


void triangulate( const Polygon &P, vector<Triangle> &T )  // Recursively triangulate from polygon vertices
{
   if ( P.size() <= 3 ) return;

   Pt A = P[0], B = P[1], AB = B - A;
   double ABsq = sq( AB );

   // Find point C ... to left of AB ... which maximises angle ACB 
   // FAILS IF EXTREMELY CONCAVE; in that case need to confirm that AC and BC cross no other line
   //                             ... which is a lot more work!
   double minCos = 2.0;
   int iC = -1;
   for ( int i = 2; i < P.size() - 1; i++ )
   {
      Pt AC = P[i] - A, BC = P[i] - B;
      if ( AC.x * BC.y - AC.y * BC.x > 0 )                 // To left of AB
      {
         double ACsq = sq( AC ), BCsq = sq( BC );
         double cosTheta = ( ACsq + BCsq - ABsq ) / ( 2.0 * sqrt( ACsq * BCsq ) );
         if ( cosTheta < minCos )
         {
            iC = i;
            minCos = cosTheta;
         }
      }
   }
   Pt C = P[iC];
   T.push_back( { A, B, C } );

   // Now gather polygons to left of AC and to right of CB and recurse
   Polygon L{ A, C }, R{ C, B };
   for ( int i = iC + 1; i < P.size(); i++ ) L.push_back( P[i] );
   for ( int i = 2     ; i <= iC     ; i++ ) R.push_back( P[i] );
   triangulate( L, T );
   triangulate( R, T );
}


//======================================================================


int main()
{
   Polygon P = { { 337.8, 657.25 }, { 247.5   , 654.25 }, { 260  , 366.5 }, { 260  , 366.5 },
                 { 347.8, 257    }, { 474.5   , 235    }, { 474.5, 235   }, { 816.3, 211   },
                 { 859.8, 372    }, { 859.8   , 372    }, { 838.3, 432   }, { 709  , 566   },
                 { 538  , 562    } };
   P = fix( P );
   ofstream outP( "polygon.dat" );
   outP << P;

   vector<Triangle> T;
   triangulate( P, T );

   ofstream outT( "triangles.dat" );
   for ( Triangle tri : T ) outT << tri;
}

Bronislaw (22)
As I understand this code triangulates from a given polygon and captures the edge/corner coordinates during the process.

But what is if the polygon is triangulated already (like with my case), but the information about the polygon coordinates order is lost/not captured during the process.

I know that if you only have the polygon without additional information then it is not possible to find out the edge/coordinate order, esp. with concave polygons.

But in my case the triangulation is already done and stored in a way that allows to perfectly draw the polygon with all triangles like here: Every 3 x,y coordinates in the vector make up a triangle. Triangle1: x1,y1; x2,y2; x3,y3 Triangle2: x1,y1; x2,y2; x3,y3


std::vector<Point> PolygonVector = { {259,611.5},{204.3,577.25},{372.5,331},{568,298},{568.5,202.75}{713.3,239.5},{720,421},{751.8,544.5},{469,642.25},{469,642.25},{259,611.5},{372.5,331},{568,298},{713.3,239.5},{720,421},{720,421},{469,642.25},{372.5,331},{480.3,331.25},{568,298},{720,421},{720,421},{372.5,331},{480.3,331.25} };


Now if you want to draw this it is perfectly possible, because you have all triangle coordinates of the polygon in the vector.

And if you remove all duplicates you get all unique edge/corner coordinates (unordered like they come in the triangles).

But how to sort all unique edge/corner coordinates in the right order (for drawing a border line around the polygon etc.) without having captured it during triangulation.

Is it still possible to somehow retrieve the lost information only with the vector info. In my first example it was sufficient to remove all duplicates and the order was right (by pure luck), but in my second example it's not so easy.
I need a safe approach (that works reliably) which takes the information of the already triangulated polygon into account.

Last edited on
ne555 (10692)
> Every 3 x,y coordinates in the vector make up a triangle.
say that vertices a, b, c form a triangle, you may create the edges
a -> b
b -> c
c -> a

say that a->b is an internal edge (not a border), then somewhere another triangle has the edge b-> a
so if you remove the "duplicates" you have the boundary edges

so you have the boundary vertex, and for every vertex v there are two edges (one that start on v and one that ends in v)
there you have the order
lastchance (6980)
@Bronislaw,
I really don't understand what you are saying.

If you know that successive triplets are triangles then you know what the edges are. If an edge belongs to only one triangle then it is a border edge to the polygon.

If you REMOVE all duplicate points then you CANNOT recover a unique polygon. Imagine you just put 4 points in a square. Then there are FOUR distinct non-closed polylines going through those points (2 directions for diagonals x 2 directions for laterals/verticals, or the letters Z and N and their mirrors). Alternatively, there are two distinct ways of triangulating it. If you knew the EDGES as well there would only be one polygon; but if you know only the POINTS then the polygon cannot be unique.




As I understand this code triangulates from a given polygon
I thought that was what you meant ... but clearly not.


But in my case the triangulation is already done and stored in a way that allows to perfectly draw the polygon with all triangles like here: Every 3 x,y coordinates in the vector make up a triangle. Triangle1: x1,y1; x2,y2; x3,y3 Triangle2: x1,y1; x2,y2; x3,y3
Clearly I missed that!


But how to sort all unique edge/corner coordinates in the right order (for drawing a border line around the polygon etc.) without having captured it during triangulation.
That's the bit of your post that I really don't understand.
Last edited on
Bronislaw (22)
@ne555 @lastchance

Theoretically it makes sense what you say, but how to check mathematically, which edge is internal or a border edge.

I know that all points lie at the outside of the polygon and that I have to begin at a point, which has no duplicates and then go from it to a point with duplicates?

Some points can have multiple duplicates (>2) so is it possible at all to go to the next border point in one direction without landing on the other side of the polygon?

I need to draw a border line around the shape (and do some other calculations)
For this I need the edge/corner coordinates to be sorted in way that allows to draw a connected line/linestrip around the polygon.

The result should be exactly:
{ {259,611.5},{204.3,577.25}, {372.5,331}, {480.3,331.25}, {568,298}, {568.5,202.75}, {713.3,239.5}, {720,421},{751.8,544.5}, {469,642.25} }

With this information I could connect all points. The last value could be connected to the first one and voila you have a line around the polygon.
Last edited on
lastchance (6980)
Bronislaw wrote:
The result should be exactly:
{ {259,611.5},{204.3,577.25}, {372.5,331}, {480.3,331.25}, {568,298}, {568.5,202.75}, {713.3,239.5}, {720,421},{751.8,544.5}, {469,642.25} }


You mean, like this ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Pt  { double x, y; };
struct Edge{ Pt A, B;     };
using Polygon = vector<Pt>;

bool operator == ( Pt p  , Pt q   ) { return p.x == q.x && p.y == q.y; }
bool operator != ( Pt p  , Pt q   ) { return !(p == q);                }
bool operator == ( Edge e, Edge f ) { return e.A == f.A && e.B == f.B; }
Pt   operator -  ( Pt p  , Pt q   ) { return { p.x - q.x, p.y - q.y }; }
ostream &operator << ( ostream &out, const Pt p       ) { return out << p.x << '\t' << p.y << '\t'; }
ostream &operator << ( ostream &out, const Polygon P  ) { for ( Pt pt : P ) out << pt << '\n';  return out; }

//======================================================================

Polygon detriangulate( const Polygon &P )        // Presumes input is a correct sequence of triangles
{
   // Take points in threes, make sure triangle is traversed anticlockwise and add edges to a collection
   vector<Edge> edges;
   for ( int i = 0; i < P.size(); i += 3 )
   {
      Pt A = P[i], B = P[i+1], C = P[i+2];
      Pt AB = B - A, AC = C - A;
      if ( AB.x * AC.y - AB.y * AC.x > 0 ) edges.insert( edges.end(), { { A, B }, { B, C }, { C, A } } );
      else                                 edges.insert( edges.end(), { { A, C }, { C, B }, { B, A } } );
   }
   
   // Border consists of all edges for which (p,q) and (q,p) aren't both in the collection
   vector<Edge> borderEdges;                     
   for ( Edge e : edges )
   {
      Edge rev = { e.B, e.A };
      if ( find( edges.begin(), edges.end(), rev ) == edges.end() ) borderEdges.push_back( e );
   }
   
   // Cycle round the border, joining up points
   Polygon Q;                                    
   Pt first = borderEdges.front().A, last = borderEdges.front().B;
   Q.push_back( first );
   while ( last != first )
   {
      Q.push_back( last );
      for ( Edge e : borderEdges )
      {
         if ( e.A == last )
         {
            last = e.B;
            break;
         }
      }
   }

   return Q;
}

//======================================================================

int main()
{
   Polygon P = { {259  , 611.5 }, {204.3, 577.25}, {372.5, 331   },
                 {568  , 298   }, {568.5, 202.75}, {713.3, 239.5 },
                 {720  , 421   }, {751.8, 544.5 }, {469  , 642.25},
                 {469  , 642.25}, {259  , 611.5 }, {372.5, 331   },
                 {568  , 298   }, {713.3, 239.5 }, {720  , 421   },
                 {720  , 421   }, {469  , 642.25}, {372.5, 331   },
                 {480.3, 331.25}, {568  , 298   }, {720  , 421   },
                 {720  , 421   }, {372.5, 331   }, {480.3 ,331.25} };

   Polygon Q = detriangulate( P );
   cout << Q;
}


259	611.5	
204.3	577.25	
372.5	331	
480.3	331.25	
568	298	
568.5	202.75	
713.3	239.5	
720	421	
751.8	544.5	
469	642.25
Last edited on
Bronislaw (22)
This is what I was looking for. Many thanks for this nice code :-)
Topic archived. No new replies allowed.