triangulate: Triangulate a two-dimensional polygon.
In rgl: 3D Visualization Using OpenGL
Description
Usage
Arguments
Details
Value
Note
Author(s)
References
See Also
Examples
Description
This algorithm decomposes a general polygon into simple
polygons and uses the “ear-clipping” algorithm to triangulate it.
Polygons with holes are supported.
Usage
1
Arguments
x, y, z
Coordinates of a two-dimensional polygon in a format supported by xyz.coords.
See Details for how z is 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.
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.
Author(s)
Duncan Murdoch
References
See the Wikipedia article “polygon triangulation”
for a description of the ear-clipping algorithm.
See Also
extrude3d for a solid extrusion of a polygon, polygon3d for
a flat display; both use triangulate.
Examples
1
2
3
4
5
6
7
8
9
10
11
theta <- seq(0, 2*pi, len = 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)
open3d()
polygon3d(x, y, x - y, col = "red")
Example output
Warning messages:
1: In rgl.init(initValue, onlyNULL) : RGL: unable to open X11 display
2: 'rgl.init' failed, running with 'rgl.useNULL = TRUE'.
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,] 5 57 5 56 56 55 54 5 53 12 52 12 52 36
[2,] 58 56 59 36 55 54 53 12 52 60 37 61 51 35
[3,] 57 5 58 5 36 36 36 59 36 59 36 60 37 5
[,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26]
[1,] 35 51 34 74 33 74 73 12 12 12 12 32
[2,] 34 74 33 38 32 73 72 62 63 64 65 31
[3,] 5 37 5 37 5 38 38 61 62 63 64 5
[,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38]
[1,] 31 72 12 72 71 13 71 30 13 29 28 19
[2,] 30 39 13 71 40 66 70 29 19 28 2 67
[3,] 5 38 65 39 39 65 40 5 66 5 5 66
[,39] [,40] [,41] [,42] [,43] [,44] [,45] [,46] [,47] [,48] [,49] [,50]
[1,] 19 70 28 19 19 27 70 70 26 26 19 2
[2,] 68 41 27 69 44 26 42 69 22 49 45 4
[3,] 67 40 2 68 69 2 41 42 2 22 44 5
[,51] [,52] [,53] [,54] [,55] [,56] [,57] [,58] [,59] [,60] [,61] [,62]
[1,] 49 19 48 21 13 5 47 22 22 13 44 19
[2,] 48 21 47 46 17 7 46 1 24 16 43 20
[3,] 22 45 22 45 19 12 22 2 1 17 69 21
[,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71] [,72] [,73] [,74]
[1,] 7 46 5 17 22 13 7 43 8 14 2 9
[2,] 11 21 6 18 23 14 8 42 9 15 3 10
[3,] 12 22 7 19 24 16 11 69 11 16 4 11
[,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85] [,86]
[1,] 116 115 114 113 91 112 91 91 91 111 111 110
[2,] 115 114 113 112 117 111 118 119 120 89 110 109
[3,] 91 91 91 91 116 91 117 118 119 91 89 89
[,87] [,88] [,89] [,90] [,91] [,92] [,93] [,94] [,95] [,96] [,97] [,98]
[1,] 109 109 91 91 108 107 76 106 76 76 76 105
[2,] 81 108 121 76 107 106 122 105 123 124 101 104
[3,] 89 81 120 121 81 81 121 81 122 123 124 81
[,99] [,100] [,101] [,102] [,103] [,104] [,105] [,106] [,107] [,108]
[1,] 104 81 103 76 81 102 77 91 91 96
[2,] 103 87 102 77 86 80 80 96 92 98
[3,] 81 89 81 101 87 81 101 76 96 76
[,109] [,110] [,111] [,112] [,113] [,114] [,115] [,116] [,117] [,118]
[1,] 77 92 96 80 92 89 78 98 94 81
[2,] 78 94 97 102 93 90 79 99 95 85
[3,] 80 96 98 101 94 91 80 76 96 86
[,119] [,120] [,121] [,122]
[1,] 87 81 82 83
[2,] 88 82 83 84
[3,] 89 85 85 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
null
1
rgl documentation built on Feb. 1, 2021, 3:01 a.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Description Usage Arguments Details Value Note Author(s) References See Also Examples
Description
This algorithm decomposes a general polygon into simple polygons and uses the “ear-clipping” algorithm to triangulate it. Polygons with holes are supported.
Usage
1 |
Arguments
x, y, z |
Coordinates of a two-dimensional polygon in a format supported by |
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.
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.
Author(s)
Duncan Murdoch
References
See the Wikipedia article “polygon triangulation” for a description of the ear-clipping algorithm.
See Also
extrude3d for a solid extrusion of a polygon, polygon3d for
a flat display; both use triangulate.
Examples
1 2 3 4 5 6 7 8 9 10 11 | theta <- seq(0, 2*pi, len = 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)
open3d()
polygon3d(x, y, x - y, col = "red")
|
Example output
Warning messages:
1: In rgl.init(initValue, onlyNULL) : RGL: unable to open X11 display
2: 'rgl.init' failed, running with 'rgl.useNULL = TRUE'.
[,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
[1,] 5 57 5 56 56 55 54 5 53 12 52 12 52 36
[2,] 58 56 59 36 55 54 53 12 52 60 37 61 51 35
[3,] 57 5 58 5 36 36 36 59 36 59 36 60 37 5
[,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26]
[1,] 35 51 34 74 33 74 73 12 12 12 12 32
[2,] 34 74 33 38 32 73 72 62 63 64 65 31
[3,] 5 37 5 37 5 38 38 61 62 63 64 5
[,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38]
[1,] 31 72 12 72 71 13 71 30 13 29 28 19
[2,] 30 39 13 71 40 66 70 29 19 28 2 67
[3,] 5 38 65 39 39 65 40 5 66 5 5 66
[,39] [,40] [,41] [,42] [,43] [,44] [,45] [,46] [,47] [,48] [,49] [,50]
[1,] 19 70 28 19 19 27 70 70 26 26 19 2
[2,] 68 41 27 69 44 26 42 69 22 49 45 4
[3,] 67 40 2 68 69 2 41 42 2 22 44 5
[,51] [,52] [,53] [,54] [,55] [,56] [,57] [,58] [,59] [,60] [,61] [,62]
[1,] 49 19 48 21 13 5 47 22 22 13 44 19
[2,] 48 21 47 46 17 7 46 1 24 16 43 20
[3,] 22 45 22 45 19 12 22 2 1 17 69 21
[,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71] [,72] [,73] [,74]
[1,] 7 46 5 17 22 13 7 43 8 14 2 9
[2,] 11 21 6 18 23 14 8 42 9 15 3 10
[3,] 12 22 7 19 24 16 11 69 11 16 4 11
[,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85] [,86]
[1,] 116 115 114 113 91 112 91 91 91 111 111 110
[2,] 115 114 113 112 117 111 118 119 120 89 110 109
[3,] 91 91 91 91 116 91 117 118 119 91 89 89
[,87] [,88] [,89] [,90] [,91] [,92] [,93] [,94] [,95] [,96] [,97] [,98]
[1,] 109 109 91 91 108 107 76 106 76 76 76 105
[2,] 81 108 121 76 107 106 122 105 123 124 101 104
[3,] 89 81 120 121 81 81 121 81 122 123 124 81
[,99] [,100] [,101] [,102] [,103] [,104] [,105] [,106] [,107] [,108]
[1,] 104 81 103 76 81 102 77 91 91 96
[2,] 103 87 102 77 86 80 80 96 92 98
[3,] 81 89 81 101 87 81 101 76 96 76
[,109] [,110] [,111] [,112] [,113] [,114] [,115] [,116] [,117] [,118]
[1,] 77 92 96 80 92 89 78 98 94 81
[2,] 78 94 97 102 93 90 79 99 95 85
[3,] 80 96 98 101 94 91 80 76 96 86
[,119] [,120] [,121] [,122]
[1,] 87 81 82 83
[2,] 88 82 83 84
[3,] 89 85 85 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
null
1
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.