SHOW:
|
|
- or go back to the newest paste.
| 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 | } |
