• API
• FAQ
• Tools
• Archive
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. //
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.     {
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.                 {
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