Advanced Strategic Command
polygontriangulation.h
Go to the documentation of this file.
1 
5 // $Id: polygontriangulation.h,v 1.6 2009-04-18 13:48:38 mbickel Exp $
6 /*
7  This file is part of Advanced Strategic Command; http://www.asc-hq.de
8  Copyright (C) 1994-2010 Martin Bickel and Marc Schellenberger
9 
10  This program is free software; you can redistribute it and/or modify
11  it under the terms of the GNU General Public License as published by
12  the Free Software Foundation; either version 2 of the License, or
13  (at your option) any later version.
14 
15  This program is distributed in the hope that it will be useful,
16  but WITHOUT ANY WARRANTY; without even the implied warranty of
17  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18  GNU General Public License for more details.
19 
20  You should have received a copy of the GNU General Public License
21  along with this program; see the file COPYING. If not, write to the
22  Free Software Foundation, Inc., 59 Temple Place, Suite 330,
23  Boston, MA 02111-1307 USA
24 */
25 
26 #ifndef polygontriangulationH
27  #define polygontriangulationH
28 
29  #include <math.h>
30  #include <sys/types.h>
31  #include <stdlib.h>
32  #include <stdio.h>
33 
34  namespace PolygonTriangulationLibrary {
35  #include "libs/triangul/interfac.h"
36  #include "libs/triangul/triangul.h"
37  };
38 
39 template <class Poly>
41  public:
42  bool paintPolygon ( const Poly& poly );
43  protected:
44  virtual void sortpolygon ( Poly& a );
45  virtual void painttriangle ( typename Poly::Point p[] );
46  virtual void painthorizline ( int x1, int x2, int y );
47  virtual void paintline ( int x1, int y1, int x2, int y2 );
48  virtual void setpoint ( int x, int y ) = 0;
49  virtual int getpolydir ( const Poly& a);
50  virtual double getsegmentdir ( int dx, int dy );
52  virtual bool checkpolygon ( const Poly& poly );
54  virtual bool checkline ( typename Poly::Point a, typename Poly::Point b, typename Poly::Point d, typename Poly::Point e );
55  virtual ~PolygonPainter() {};
56  };
57 
58 template <class Poly>
59 bool PolygonPainter<Poly>::paintPolygon ( const Poly& poly )
60 {
61  if ( !poly.vertex.size() )
62  return true;
63 
64 // displayLogMessage ( 10, "pp1 ");
65  if (checkpolygon ( poly )) {
66  if ( poly.vertex.size() == 1 ) {
67  setpoint ( poly.vertex[0].x, poly.vertex[0].y );
68  return true;
69  }
70  if ( poly.vertex.size() == 2 ) {
71  paintline ( poly.vertex[0].x, poly.vertex[0].y, poly.vertex[1].x, poly.vertex[1].y );
72  return true;
73  }
74 
75 // displayLogMessage ( 10, "pp2 ");
76  Poly pol2 = poly;
77  sortpolygon ( pol2 );
78 
79 
80  typedef double double2[2];
81  double2* floatpoints = new double2 [ pol2.vertex.size()+1 ];
82  for ( int i=0; i<pol2.vertex.size() ; i++ ) {
83  floatpoints[i+1][0] = (double) pol2.vertex[i].x;
84  floatpoints[i+1][1] = (double) pol2.vertex[i].y;
85  } /* endfor */
86 
87  typedef int int3[3];
88 
89  int3* triangles = new int3 [ pol2.vertex.size() ];
90 
91  int contours = pol2.vertex.size();
92 
93 // displayLogMessage ( 10, "pp3 ");
94  PolygonTriangulationLibrary::triangulate_polygon ( 1, &contours, floatpoints, triangles );
95 // displayLogMessage ( 10, "pp4 ");
96 
97  for ( int i=0; i<pol2.vertex.size()-2 ;i++ ) {
98  typename Poly::Point tripos[3];
99  tripos[0] = pol2.vertex[triangles[i][0]-1];
100  tripos[1] = pol2.vertex[triangles[i][1]-1];
101  tripos[2] = pol2.vertex[triangles[i][2]-1];
102  painttriangle ( tripos );
103  } /* endfor */
105  delete[] triangles;
106  delete[] floatpoints;
108  return true;
109  } else
110  return false;
111 }
113 static const double pi = 3.141592654;
115 
116 template <class Poly>
117 bool PolygonPainter<Poly>::checkline( typename Poly::Point a, typename Poly::Point b, typename Poly::Point d, typename Poly::Point e )
118 {
119  double r,s,t;
121  b.x -= a.x;
122  b.y -= a.y;
123 
124  e.x -= d.x;
125  e.y -= d.y;
126 
127  /*
128  if ( b.y != 0 && e.y != 0 ) {
129  if ( abs( b.x / b.y - e.x / e.y ) < 1e-6 )
130  return false;
131  } else
132  if ( b.y == 0 && e.y == 0 )
133  return false;
134  */
135 
136 
137  t = b.x * e.y - b.y * e.x;
138  if (t != 0) {
139  double m = ( a.x * b.y - a.y * b.x + d.y * b.x - d.x * b.y );
140  r = m / -t;
141 
142  double n = ( a.y * e.x - a.x * e.y + d.x * e.y - d.y * e.x );
143  s = n / t;
144  if ( s>=0 && s <= 1 && r>=0 && r <= 1)
145  return false;
146 
147  } /* endif */
148  return true;
149 }
150 
151 
152 template <class Poly>
153 bool PolygonPainter<Poly>::checkpolygon ( const Poly& poly )
154 {
155  if ( poly.vertex.size() > 1 && poly.vertex.size() < 3 )
156  return true;
157  else {
158  size_t i,j,k;
159 
160  for ( i = 0; i < poly.vertex.size(); i++ )
161  for ( j = 0; j < poly.vertex.size(); j++ )
162  if ( i != j )
163  if ( poly.vertex[i].x == poly.vertex[j].x &&
164  poly.vertex[i].y == poly.vertex[j].y )
165  return false;
166 
167  k = poly.vertex.size() -1;
168  for (i=0; i < k ; i++) {
169  for (j = i +2; j < k ; j++)
170  if (checkline ( poly.vertex[i], poly.vertex[i+1], poly.vertex[j], poly.vertex[j+1] ) == false)
171  return false;
172  if (i > 0 && j == k)
173  if (checkline ( poly.vertex[i], poly.vertex[i+1], poly.vertex[j], poly.vertex[0] ) == false)
174  return false;
175  } /* endfor */
176  return true;
177  }
178 }
179 
180 
181 
182 template <class Poly>
183 double PolygonPainter<Poly>::getsegmentdir ( int dx, int dy )
184 {
185  double alpha;
186 
187  if (dx) {
188  alpha = atan ( (double) dy / (double) dx );
189  if ( dy < 0 ) {
190  if ( dx < 0)
191  alpha = -pi + alpha;
192  } else
193  if ( dx < 0)
194  alpha = pi - alpha;
195 
196  } else {
197  if (dy > 0)
198  alpha = pi/2;
199  else
200  alpha = -pi/2;
201  } /* endif */
202 
203  return alpha;
204 }
205 
206 template <class Poly>
208 {
209  int p ;
210  double alpha, beta, gamma;
211  int r = 0;
212  for (p=0; p< a.vertex.size(); p++) {
213 
214  if (p == 0)
215  alpha = getsegmentdir( a.vertex[p].x - a.vertex[a.vertex.size()-1].x , a.vertex[p].y - a.vertex[a.vertex.size()-1].y );
216  else
217  alpha = getsegmentdir( a.vertex[p].x - a.vertex[p-1].x, a.vertex[p].y - a.vertex[p-1].y );
218 
219  if (p+1 >= a.vertex.size())
220  beta = getsegmentdir( a.vertex[0].x - a.vertex[p].x , a.vertex[0].y - a.vertex[p].y );
221  else
222  beta = getsegmentdir( a.vertex[p+1].x - a.vertex[p].x, a.vertex[p+1].y - a.vertex[p].y );
223 
224  gamma = beta - alpha ;
225  if (gamma > pi)
226  gamma = pi - gamma;
227  if (gamma < -pi)
228  gamma = -pi - gamma;
229  r+= (int) ( gamma * 1000 );
230  }
231  return r;
232 }
233 
234 
235 template <class Poly>
237 {
238  if ( a.vertex.size() >= 3 )
239  if ( getpolydir(a) < 0 ) {
240  for ( int i=0;i< a.vertex.size()/2 ;i++ ) {
241  typename Poly::Point p = a.vertex[i];
242  a.vertex[i] = a.vertex[a.vertex.size()-i-1];
243  a.vertex[a.vertex.size()-i-1] = p;
244  } /* endfor */
245  }
246 }
247 
248 
249 template <class Poly>
250 void PolygonPainter<Poly>::painttriangle ( typename Poly::Point p[] )
251 {
252  int x,y,dx1,dx2,dy1,dy2;
253 
254  for ( int i=0; i<2 ; ) {
255  if ( p[i+1].y < p[i].y || ( p[i+1].y == p[i].y && p[i+1].x < p[i].x )) {
256  x = p[i].x;
257  p[i].x = p[i+1].x;
258  p[i+1].x = x;
259  y = p[i].y;
260  p[i].y = p[i+1].y;
261  p[i+1].y = y;
262  i = 0;
263  } else
264  i++;
265 
266  } /* endfor */
267 
268 
269  if ( p[0].y < p[1].y ) {
270  dx1 = p[1].x - p[0].x;
271  dx2 = p[2].x - p[0].x;
272  dy1 = p[1].y - p[0].y;
273  dy2 = p[2].y - p[0].y;
274 
275  for (y=p[0].y; y<=p[1].y ; y++)
276  painthorizline ( p[0].x + dx1 * (y - p[0].y) / dy1 , p[0].x + dx2 * (y - p[0].y) / dy2, y );
277 
278  if (p[1].y < p[2].y) {
279  dx1 = p[2].x - p[1].x;
280  dy1 = p[2].y - p[1].y;
281 
282  for ( ; y<=p[2].y ; y++)
283  painthorizline ( p[1].x + dx1 * (y - p[1].y) / dy1 , p[0].x + dx2 * (y - p[0].y) / dy2, y );
284  }
285  } else {
286  if ( p[1].y < p[2].y ) {
287 
288  dx1 = p[2].x - p[1].x;
289  dx2 = p[2].x - p[0].x;
290  dy1 = p[2].y - p[0].y;
291 
292  for (y=p[0].y; y<=p[2].y ; y++)
293  painthorizline ( p[1].x + dx1 * (y - p[0].y) / dy1 , p[0].x + dx2 * (y - p[0].y) / dy1, y );
294  } else
295  painthorizline ( p[0].x, p[2].x, p[0].y );
296  }
297 
298 }
299 
300 
301 template <class Poly>
302 void PolygonPainter<Poly>::painthorizline ( int x1, int x2, int y )
303 {
304  int dx;
305  if (x1 > x2)
306  dx = -1;
307  else
308  if (x1 < x2)
309  dx = 1;
310  else {
311  setpoint ( x2, y );
312  return;
313  }
314 
315  int x= x1;
316 
317  do {
318  setpoint ( x, y );
319  x += dx;
320  } while ( x != x2 ); /* enddo */
321  setpoint ( x, y );
322 }
323 
324 
325 template <class Poly>
326 void PolygonPainter<Poly>::paintline ( int x1, int y1, int x2, int y2 )
327 {
328  float m, b;
329  int w;
330  float yy1, yy2, xx1, xx2;
331 
332 
333 
334  if ( x1 == x2) {
335  for (w=y1;w<=y2 ;w++ )
336  setpoint ( x1, w );
337  } else {
338  if ( y1 == y2) {
339  for (w=x1;w<=x2 ;w++ )
340  setpoint( w, y1 );
341  } else {
342  yy1 = y1;
343  yy2 = y2;
344  xx1 = x1;
345  xx2 = x2;
346  m = (yy2 - yy1) / (xx2 - xx1);
347  b = y1 - m * x1;
348  if ((m <= 1) && (m >= -1)) {
349  if (x2 < x1) {
350  w = x2;
351  x2 = x1;
352  x1 = w;
353  w = y2;
354  y2 = y1;
355  y1 = w;
356  }
357  for (w = x1; w <= x2; w++)
358  setpoint(w, (int) (m * w + b) );
359 
360  } else {
361  if (y2 < y1) {
362  w = x2;
363  x2 = x1;
364  x1 = w;
365  w = y2;
366  y2 = y1;
367  y1 = w;
368  }
369  for (w = y1; w <= y2; w++) {
370  setpoint( (int) ((w - b) / m), w );
371  }
372 
373  }
374  } /* endif */
375  }
376 }
377 
378 
379 
380 
381 
382 #endif
virtual void paintline(int x1, int y1, int x2, int y2)
static const double pi
virtual double getsegmentdir(int dx, int dy)
virtual bool checkline(typename Poly::Point a, typename Poly::Point b, typename Poly::Point d, typename Poly::Point e)
returns true if lines a-b and c-d don't intersect
virtual int getpolydir(const Poly &a)
virtual void painttriangle(typename Poly::Point p[])
virtual void sortpolygon(Poly &a)
virtual void setpoint(int x, int y)=0
virtual bool checkpolygon(const Poly &poly)
returns true if polygon correct
bool paintPolygon(const Poly &poly)
virtual void painthorizline(int x1, int x2, int y)
int triangulate_polygon(int, int *, double(*)[2], int(*)[3])