This 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 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.

References

See the Wikipedia article “polygon triangulation” for a description of the ear-clipping algorithm.

Author

Duncan Murdoch

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

extrude3d for a solid extrusion of a polygon, polygon3d for a flat display; both use triangulate.

Examples

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)

#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12] [,13] [,14]
#> [1,]   56   55   55   54   36   53   35   34   34    33    11    52    33    33
#> [2,]   55   37   54   53   35   52   34   57   33    11    58    51     3    32
#> [3,]   36   36   37   37   56   37   56   56   57    57    57    37    11     3
#>      [,15] [,16] [,17] [,18] [,19] [,20] [,21] [,22] [,23] [,24] [,25] [,26]
#> [1,]    32    31    11    51    74    73    73    73    72    72    71    11
#> [2,]    31    30    59    74    73    38    39    72    20    71    70    60
#> [3,]     3     3    58    37    37    37    38    39    39    20    20    59
#>      [,27] [,28] [,29] [,30] [,31] [,32] [,33] [,34] [,35] [,36] [,37] [,38]
#> [1,]    30    70    69    11    29    68    67    11    28    67    27    66
#> [2,]    29    69    68    61    28    67    13    62    27    66    26    65
#> [3,]     3    20    20    60     3    20    20    61     3    13     3    13
#>      [,39] [,40] [,41] [,42] [,43] [,44] [,45] [,46] [,47] [,48] [,49] [,50]
#> [1,]    11    26    11    26    49    20    20    65    20     3    11    48
#> [2,]    63    22    64    49    48    40    41    12    42    10    12    47
#> [3,]    62     3    63    22    22    39    40    13    41    11    64    22
#>      [,51] [,52] [,53] [,54] [,55] [,56] [,57] [,58] [,59] [,60] [,61] [,62]
#> [1,]    47     3    46    45     7     8    12    13    14    44    43     3
#> [2,]    46     7    45    44     8     9    65    14    18    43    42     5
#> [3,]    22    10    22    22    10    10    64    20    20    22    22     7
#>      [,63] [,64] [,65] [,66] [,67] [,68] [,69] [,70] [,71] [,72] [,73] [,74]
#> [1,]    14     3    22    42    22    22     1     5    20    14    14    18
#> [2,]    17     4     1    21    24    23     2     6    21    16    15    19
#> [3,]    18     5     3    22     1    24     3     7    42    17    16    20
#>      [,75] [,76] [,77] [,78] [,79] [,80] [,81] [,82] [,83] [,84] [,85] [,86]
#> [1,]   121   120    98   119   119   118   117   116    98    98    98    98
#> [2,]   120   119   122    89   118   117   116   115   123   124   101   102
#> [3,]    98    98   121    98    89    89    89    89   122   123   124   101
#>      [,87] [,88] [,89] [,90] [,91] [,92] [,93] [,94] [,95] [,96] [,97] [,98]
#> [1,]    98   115   114    98    98    99    99    79   113   112    79    79
#> [2,]   103   114   113   104    99   105    79   106   112   111   107   108
#> [3,]   102    89    89   103   104   104   105   105    89    89   106   107
#>      [,99] [,100] [,101] [,102] [,103] [,104] [,105] [,106] [,107] [,108]
#> [1,]    79     79     79     89     89     88    111     92     99     76
#> [2,]   109     88     81     96     92     89    110     93     76     77
#> [3,]   108    109     88     98     96    109     89     96     79     79
#>      [,109] [,110] [,111] [,112] [,113] [,114] [,115] [,116] [,117] [,118]
#> [1,]     81     93     81     77     89     79     89     81     85     93
#> [2,]     87     95     85     78     91     80     90     82     86     94
#> [3,]     88     96     87     79     92     81     91     85     87     95
#>      [,119] [,120] [,121] [,122]
#> [1,]    110     82     83     96
#> [2,]    109     83     84     97
#> [3,]     89     85     85     98
#> 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")