20:
31:
170:
Generating the list of triangles is trivial if an ordered list of vertices is available, and can be computed in linear time. As such, it is unnecessary to explicitly store the list of triangles, and therefore, many graphical libraries implement primitives to represent polygons based on this
165:
139:
113:
66:
to all of the other vertices of the polygon. Not every polygon can be triangulated this way, so this method is usually only used for
313:
258:
233:
85:
Polygons with only one concave vertex can always be fan triangulated, as long as the diagonals are drawn from the concave vertex.
318:
92:, in order to determine whether there is at least one vertex that is visible from every point in the polygon.
182:, it may be unfit for other tasks because the origin vertex accumulates a high number of neighbors, and the
43:
19:
51:
30:
283:
179:
89:
78:
Aside from the properties of all triangulations, fan triangulations have the following properties:
225:
264:
254:
229:
59:
217:
63:
35:
144:
118:
183:
98:
67:
24:
307:
218:
175:
196:
268:
174:
Although this triangulation is fit for solving certain problems, such as
55:
88:
It can be known if a polygon can be fan triangulated by solving the
82:
All convex polygons, but not all polygons, can be fan triangulated.
29:
18:
253:(2nd ed.). Cambridge, UK: Cambridge University Press.
220:
Triangulations: Structures for
Algorithms and Applications
216:
Loera, Jesus; Rambau, Joerg; Santos, Francisco (2010).
147:
121:
101:
224:. Springer Science & Business Media. pp.
159:
133:
107:
186:of the triangulation are unevenly distributed.
284:"The OpenGL Graphics System: A Specification"
8:
146:
120:
100:
16:Method of triangulating complex polygons
208:
7:
95:The triangulation of a polygon with
14:
282:Segal, Mark (24 October 2016).
1:
38:with a unique concave vertex.
251:Computational geometry in C
335:
249:O'Rourke, Joseph (1998).
141:diagonals, and generates
314:Triangulation (geometry)
34:Fan triangulation of a
23:Fan triangulation of a
161:
135:
109:
44:computational geometry
39:
27:
162:
136:
110:
33:
22:
319:Geometric algorithms
145:
119:
99:
180:collision detection
160:{\displaystyle n-2}
134:{\displaystyle n-3}
90:Art gallery problem
50:is a simple way to
157:
131:
105:
40:
28:
108:{\displaystyle n}
48:fan triangulation
326:
298:
297:
295:
293:
288:
279:
273:
272:
246:
240:
239:
223:
213:
166:
164:
163:
158:
140:
138:
137:
132:
114:
112:
111:
106:
334:
333:
329:
328:
327:
325:
324:
323:
304:
303:
302:
301:
291:
289:
286:
281:
280:
276:
261:
248:
247:
243:
236:
215:
214:
210:
205:
193:
184:internal angles
143:
142:
117:
116:
97:
96:
76:
68:convex polygons
36:concave polygon
17:
12:
11:
5:
332:
330:
322:
321:
316:
306:
305:
300:
299:
274:
259:
241:
234:
207:
206:
204:
201:
200:
199:
192:
189:
188:
187:
172:
171:triangulation.
168:
156:
153:
150:
130:
127:
124:
115:vertices uses
104:
93:
86:
83:
75:
72:
58:by choosing a
25:convex polygon
15:
13:
10:
9:
6:
4:
3:
2:
331:
320:
317:
315:
312:
311:
309:
285:
278:
275:
270:
266:
262:
260:9780521649766
256:
252:
245:
242:
237:
235:9783642129711
231:
227:
222:
221:
212:
209:
202:
198:
195:
194:
190:
185:
181:
177:
176:Rasterisation
173:
169:
154:
151:
148:
128:
125:
122:
102:
94:
91:
87:
84:
81:
80:
79:
73:
71:
69:
65:
61:
57:
53:
49:
45:
37:
32:
26:
21:
290:. Retrieved
277:
250:
244:
219:
211:
197:Triangle fan
77:
62:and drawing
47:
41:
52:triangulate
308:Categories
203:References
167:triangles.
74:Properties
152:−
126:−
269:38542796
191:See also
292:2 March
56:polygon
267:
257:
232:
60:vertex
287:(PDF)
178:, or
64:edges
294:2017
265:OCLC
255:ISBN
230:ISBN
46:, a
226:103
42:In
310::
263:.
228:.
70:.
54:a
296:.
271:.
238:.
155:2
149:n
129:3
123:n
103:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
