Triangulate a two-dimensional polygon
triangulate.RdThis algorithm decomposes a general polygon into simple polygons and uses the “ear-clipping” algorithm to triangulate it. Polygons with holes are supported.
triangulate(x, y = NULL, z = NULL, random = TRUE, plot = FALSE, partial = NA)Arguments
- x, y, z
Coordinates of a two-dimensional polygon in a format supported by
xyz.coords. See Details for howzis handled.- random
Whether to use a random or deterministic triangulation.
- plot
Whether to plot the triangulation; mainly for debugging purposes.
- partial
If the triangulation fails, should partial results be returned?
Details
Normally triangulate looks only at the x and y
coordinates. However, if one of those is constant, it is replaced
with the z coordinate if present.
The algorithm works as follows. First, it breaks the polygon into
pieces separated by NA values in x or y.
Each of these pieces should be a simple, non-self-intersecting
polygon, separate from the other pieces.
(Though some minor exceptions to this rule may work, none
are guaranteed). The nesting of these pieces is determined.
The “outer” polygon(s) are then merged with the polygons that they immediately contain, and each of these pieces is triangulated using the ear-clipping algorithm.
Finally, all the triangulated pieces are put together into one result.
Value
A three-by-n array giving the indices of the vertices of each triangle. (No vertices are added; only the original vertices are used in the triangulation.)
The array has an integer vector attribute "nextvert"
with one entry per vertex, giving the index of the next
vertex to proceed counter-clockwise around outer
polygon boundaries, clockwise around inner boundaries.
References
See the Wikipedia article “polygon triangulation” for a description of the ear-clipping algorithm.
Note
Not all inputs will succeed, even when a triangulation is
possible. Generally using random = TRUE will find
a successful triangulation if one exists, but it may
occasionally take more than one try.
See also
Examples
theta <- seq(0, 2*pi, length.out = 25)[-25]
theta <- c(theta, NA, theta, NA, theta, NA, theta, NA, theta)
r <- c(rep(1.5, 24), NA, rep(0.5, 24), NA, rep(0.5, 24), NA, rep(0.3, 24), NA, rep(0.1, 24))
dx <- c(rep(0, 24), NA, rep(0.6, 24), NA, rep(-0.6, 24), NA, rep(-0.6, 24), NA, rep(-0.6, 24))
x <- r*cos(theta) + dx
y <- r*sin(theta)
plot(x, y, type = "n")
polygon(x, y)
triangulate(x, y, plot = TRUE)
#> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
#> [1,] 64 13 13 63 62 61 60 13 20 20 60 59 58 20
#> [2,] 63 65 66 62 61 60 7 20 67 68 59 58 57 69
#> [3,] 13 64 65 13 13 13 13 66 66 67 7 7 7 68
#> [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26]
#> [1,] 20 57 43 20 43 56 20 42 42 55 20 42
#> [2,] 43 56 70 44 42 55 45 71 72 54 46 41
#> [3,] 69 7 69 43 70 7 44 70 71 7 45 72
#> [,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38]
#> [1,] 20 41 20 41 24 41 24 24 40 39 39 24
#> [2,] 47 73 24 74 48 40 49 26 39 51 38 27
#> [3,] 46 72 47 73 47 74 48 49 74 74 51 26
#> [,39] [,40] [,41] [,42] [,43] [,44] [,45] [,46] [,47] [,48] [,49] [,50]
#> [1,] 54 24 53 33 38 32 53 38 7 10 31 53
#> [2,] 53 28 33 32 52 31 34 37 10 12 30 52
#> [3,] 7 27 7 7 51 7 33 52 13 13 7 34
#> [,51] [,52] [,53] [,54] [,55] [,56] [,57] [,58] [,59] [,60] [,61] [,62]
#> [1,] 37 20 30 30 10 13 21 13 29 29 36 13
#> [2,] 36 21 4 29 11 19 22 16 3 1 35 14
#> [3,] 52 24 7 4 12 20 24 19 4 3 52 16
#> [,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71] [,72] [,73] [,74]
#> [1,] 4 16 22 29 7 1 5 24 8 17 52 14
#> [2,] 5 17 23 28 8 2 6 1 9 18 35 15
#> [3,] 7 19 24 1 10 3 7 28 10 19 34 16
#> [,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85] [,86]
#> [1,] 118 117 90 116 115 114 113 112 111 110 110 90
#> [2,] 117 116 119 115 114 113 112 111 110 81 109 120
#> [3,] 90 90 118 90 90 90 90 90 90 90 81 119
#> [,87] [,88] [,89] [,90] [,91] [,92] [,93] [,94] [,95] [,96] [,97] [,98]
#> [1,] 90 95 109 95 95 95 108 107 107 95 106 95
#> [2,] 95 121 108 122 123 124 107 80 106 101 77 98
#> [3,] 120 120 81 121 122 123 81 81 80 124 80 101
#> [,99] [,100] [,101] [,102] [,103] [,104] [,105] [,106] [,107] [,108]
#> [1,] 98 99 95 90 99 95 106 81 87 106
#> [2,] 99 102 97 92 103 96 76 87 89 105
#> [3,] 101 101 98 95 102 97 77 90 90 76
#> [,109] [,110] [,111] [,112] [,113] [,114] [,115] [,116] [,117] [,118]
#> [1,] 105 81 87 99 81 81 92 77 83 77
#> [2,] 104 86 88 104 83 82 93 79 85 78
#> [3,] 76 87 89 103 86 83 95 80 86 79
#> [,119] [,120] [,121] [,122]
#> [1,] 90 99 93 83
#> [2,] 91 76 94 84
#> [3,] 92 104 95 85
#> attr(,"nextvert")
#> [1] 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
#> [19] 20 21 22 23 24 1 NA 49 26 27 28 29 30 31 32 33 34 35
#> [37] 36 37 38 39 40 41 42 43 44 45 46 47 48 NA 74 51 52 53
#> [55] 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
#> [73] 72 73 NA 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
#> [91] 92 93 94 95 96 97 98 99 76 NA 124 101 102 103 104 105 106 107
#> [109] 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
open3d()
polygon3d(x, y, x - y, col = "red")
3D plot