# Untitled

a guest
Feb 1st, 2017
654
0
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. }
Add Comment
Please, Sign In to add comment