Guest User

Untitled

a guest
Feb 1st, 2017
564
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.43 KB | None | 0 0
  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. }
Add Comment
Please, Sign In to add comment