SHARE
TWEET

Untitled

a guest Feb 1st, 2017 261 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. ///shape_to_triangles(shape)
  2. //
  3. //  Returns a list of triangles created from a given 2D polygon.
  4. //
  5. //      polygon     ds_list of an ordered series of coordinate
  6. //                  pairs defining the shape of a polygon
  7. //
  8. //  The polygon vertices are given and returned in traditional
  9. //  counter-clockwise order. Polygons are closed figures with edges
  10. //  spanning consecutive vertices and from the last vertex to the
  11. //  first. Polygons must be simple, which means they cannot have
  12. //  edges that cross one another. The number of triangles created
  13. //  is (n-2), where n is the number of vertices in the polygon.
  14. //
  15. //  eg. in:  square polygon = { 100,100,  100,200,  200,200,  200,100 }
  16. //
  17. //      out: two triangles = { 100,100,  100,200,  200,100,  
  18. //                             100,200,  200,200,  200,100 }
  19. //
  20. //  Depends on lines_intersect() and point_in_triangle().
  21. //
  22. /// GMLscripts.com/license
  23. {
  24.     var polygon, polygonSize, triangles, points, polyX, polyY, good;
  25.     var i, j, n, p, A, B, C, x0, y0, x1, y1, x2, y2, x3, y3, x4, y4,
  26.     p0,p1,p2,p3,p4;
  27.     polygon = argument0;
  28.     polygonSize = ds_list_size(polygon);
  29.     triangles = ds_list_create();
  30.     points = ds_list_create();
  31.     polyP = ds_list_create();
  32.  
  33.     i = 0;
  34.     repeat (polygonSize)
  35.     {
  36.         ds_list_add(polyP, ds_list_find_value(polygon, i));
  37.         i += 1;
  38.     }
  39.  
  40.     // 1. For (n - 3) vertices
  41.     n = polygonSize;
  42.     for (n = polygonSize; n > 3; n -= 1)
  43.     {
  44.         //  a. Select first point (random)    
  45.         ds_list_clear(points);
  46.         for (p = 0; p < n; p += 1) ds_list_add(points, p);
  47.         repeat (p)
  48.         {
  49.             i = floor(random(ds_list_size(points)));
  50.             A = ds_list_find_value(points, i);
  51.             ds_list_delete(points, i);
  52.  
  53.             //  b. Pick the next two points
  54.             B = (A + 1) mod n;
  55.             C = (A + 2) mod n;
  56.  
  57.             //  c. Make a triangle with the selected points
  58.             p0 = ds_list_find_value(polyP, A);
  59.             p1 = ds_list_find_value(polyP, B);
  60.             p2 = ds_list_find_value(polyP, C);
  61.            
  62.             x0 = point_x(p0); y0 = point_y(p0);
  63.             x1 = point_x(p1); y1 = point_y(p1);
  64.             x2 = point_x(p2); y2 = point_y(p2);
  65.            
  66.             //  d. If triangle is counter-clockwise...
  67.             if ((x1 - x0) * (y2 - y0) + (y0 - y1) * (x2 - x0) < 0)
  68.             {
  69.                 good = true;
  70.                 //  ...and if triangle has no vertices within it...
  71.                 for (i = 0; i < n; i += 1)
  72.                 {
  73.                     if ((i != A) && (i != B) && (i != C))
  74.                     {
  75.                         p3 = ds_list_find_value(polyP,i);
  76.                         x3 = point_x(p3);
  77.                         y3 = point_y(p3);
  78.                         if (point_in_triangle(x3, y3, x0, y0, x1, y1, x2, y2))
  79.                         {
  80.                             good = false;
  81.                             break;
  82.                         }
  83.                         //  ...and if the new edge has no other edges crossing it...
  84.                         j = (i + 1) mod n;
  85.                         if ((j != A) && (j != B) && (j != C))
  86.                         {
  87.                             p4 = ds_list_find_value(polyP,j);
  88.                             x4 = point_x(p4);
  89.                             y4 = point_y(p4);
  90.  
  91.                             if (lines_intersect(x0, y0, x2, y2, x3, y3, x4, y4, true) != 0)
  92.                             {
  93.                                 good = false;
  94.                                 break;
  95.                             }
  96.                         }
  97.                     }
  98.                 }
  99.  
  100.                 //  e.  ...then add the triangle to list and remove the unshared vertex
  101.                 if (good)
  102.                 {
  103.                     ds_list_add(triangles, p0);
  104.                     ds_list_add(triangles, p1);
  105.                     ds_list_add(triangles, p2);
  106.                     ds_list_delete(polyP, B);
  107.                     break;
  108.                 }
  109.             }
  110.         }
  111.     }
  112.  
  113.     //  2. There are only three vertices left, so add the final triangle to the list
  114.     ds_list_add(triangles, ds_list_find_value(polyP, 0));
  115.     ds_list_add(triangles, ds_list_find_value(polyP, 1));
  116.     ds_list_add(triangles, ds_list_find_value(polyP, 2));
  117.  
  118.     //  3. Clean up
  119.     ds_list_destroy(polyP);
  120.     ds_list_destroy(points);
  121.  
  122.     return triangles;
  123. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top