212:
31:
86:
is the number of points on the convex hull. Its real-life performance compared with other convex hull algorithms is favorable when n is small or h is expected to be very small with respect to n. In general cases, the algorithm is outperformed by many others (see
234:
will be the set of points which form the convex hull. Final set size is i. pointOnHull := leftmost point in S // which is guaranteed to be part of the CH(S) i := 0
367:, another convex hull algorithm, combines the logarithmic dependence of Graham scan with the output sensitivity of the gift wrapping algorithm, achieving an asymptotic running time
34:
Animation of the gift wrapping algorithm. The red lines are already placed lines, the black line is the current best guess for the new line, and the green line is the next guess
403:
349:
300:
200:
steps. In two dimensions, the gift wrapping algorithm is similar to the process of winding a string (or wrapping paper) around the set of points.
246:// endpoint == pointOnHull is a rare case and can happen only when j == 1 and a better endpoint has not yet been set for the loop
111:(vertices of the convex hull) or all points that lie on the convex hull. Also, the complete implementation must choose how to deal with
254:
endpoint := S // found greater left turn, update endpoint i := i + 1 pointOnHull := endpoint
107:. The algorithm may be easily modified to deal with collinearity, including the choice whether it should report only
454:
238:
P := pointOnHull endpoint := S // initial endpoint for a candidate edge on the hull
502:
466:
17:
464:
Jarvis, R. A. (1973). "On the identification of the convex hull of a finite set of points in the plane".
444:
303:
30:
160:
370:
316:
414:
88:
39:
211:
432:
273:
116:
8:
364:
497:
270:, and the outer loop repeats for each point on the hull. Hence the total run time is
479:
450:
171:
115:
when the convex hull has only 1 or 2 vertices, as well as with the issues of limited
475:
428:
100:
112:
99:
For the sake of simplicity, the description below assumes that the points are in
75:
133:
known to be on the convex hull, e.g., the leftmost point, and selects the point
440:
67:
491:
108:
302:. The run time depends on the size of the output, so Jarvis's march is an
352:
310:
51:
436:
250:(endpoint == pointOnHull) or (S is on left of line from P to endpoint)
104:
47:
449:(2nd ed.). MIT Press and McGraw-Hill. pp. 955–956.
62:
In the two-dimensional case the algorithm is also known as
427:
258:
endpoint == P // wrapped around to first hull point
313:
on the number of hull vertices, it is only faster than
66:, after R. A. Jarvis, who published it in 1973; it has
27:
Algorithm for computing convex hulls in a set of points
405:
that improves on both Graham scan and gift wrapping.
373:
319:
276:
203:The approach can be extended to higher dimensions.
397:
343:
294:
140:such that all points are to the right of the line
489:
119:, both of computer computations and input data.
463:
266:The inner loop checks every point in the set
443:(2001) . "33.3: Finding the convex hull".
359:of hull vertices is smaller than log
309:However, because the running time depends
215:Jarvis's march computing the convex hull.
182:+1, and repeating with until one reaches
210:
122:The gift wrapping algorithm begins with
29:
14:
490:
163:of all points with respect to point
24:
25:
514:
196:again yields the convex hull in
467:Information Processing Letters
392:
377:
338:
323:
289:
280:
57:
13:
1:
420:
261:
206:
151:. This point may be found in
480:10.1016/0020-0190(73)90020-3
230:is the set of points //
103:, i.e., no three points are
94:
82:is the number of points and
7:
408:
10:
519:
446:Introduction to Algorithms
398:{\displaystyle O(n\log h)}
344:{\displaystyle O(n\log n)}
304:output-sensitive algorithm
54:of a given set of points.
170:taken for the center of
44:gift wrapping algorithm
503:Convex hull algorithms
415:Convex hull algorithms
399:
345:
296:
216:
89:Convex hull algorithms
40:computational geometry
35:
433:Leiserson, Charles E.
400:
346:
297:
295:{\displaystyle O(nh)}
214:
33:
371:
317:
274:
159:) time by comparing
117:arithmetic precision
351:algorithms such as
395:
341:
292:
217:
50:for computing the
36:
437:Rivest, Ronald L.
429:Cormen, Thomas H.
172:polar coordinates
16:(Redirected from
510:
483:
460:
404:
402:
401:
396:
365:Chan's algorithm
355:when the number
350:
348:
347:
342:
301:
299:
298:
293:
242:j from 0 to |S|
113:degenerate cases
101:general position
21:
518:
517:
513:
512:
511:
509:
508:
507:
488:
487:
486:
457:
441:Stein, Clifford
423:
411:
372:
369:
368:
318:
315:
314:
275:
272:
271:
264:
259:
209:
194:
187:
168:
149:
145:
138:
131:
126:=0 and a point
97:
76:time complexity
60:
28:
23:
22:
15:
12:
11:
5:
516:
506:
505:
500:
485:
484:
461:
455:
424:
422:
419:
418:
417:
410:
407:
394:
391:
388:
385:
382:
379:
376:
340:
337:
334:
331:
328:
325:
322:
291:
288:
285:
282:
279:
263:
260:
218:
208:
205:
192:
185:
166:
147:
143:
136:
129:
109:extreme points
96:
93:
59:
56:
26:
9:
6:
4:
3:
2:
515:
504:
501:
499:
496:
495:
493:
481:
477:
473:
469:
468:
462:
458:
456:0-262-03293-7
452:
448:
447:
442:
438:
434:
430:
426:
425:
416:
413:
412:
406:
389:
386:
383:
380:
374:
366:
362:
358:
354:
335:
332:
329:
326:
320:
312:
307:
305:
286:
283:
277:
269:
257:
253:
249:
245:
241:
237:
233:
229:
225:
221:
213:
204:
201:
199:
195:
188:
181:
177:
173:
169:
162:
158:
154:
150:
139:
132:
125:
120:
118:
114:
110:
106:
102:
92:
90:
85:
81:
77:
73:
69:
65:
55:
53:
49:
45:
41:
32:
19:
471:
465:
445:
360:
356:
308:
267:
265:
255:
251:
247:
243:
239:
235:
231:
227:
223:
219:
202:
197:
190:
183:
179:
175:
164:
161:polar angles
156:
152:
141:
134:
127:
123:
121:
98:
83:
79:
71:
64:Jarvis march
63:
61:
43:
37:
18:Jarvis march
353:Graham scan
58:Planar case
52:convex hull
492:Categories
421:References
262:Complexity
222:jarvis(S)
207:Pseudocode
174:. Letting
498:Polytopes
474:: 18–21.
387:
333:
220:algorithm
105:collinear
95:Algorithm
48:algorithm
409:See also
311:linearly
78:, where
453:
236:repeat
46:is an
42:, the
256:until
451:ISBN
252:then
476:doi
384:log
330:log
240:for
226://
148:i+1
137:i+1
91:).
38:In
494::
470:.
439:;
435:;
431:;
363:.
306:.
248:if
244:do
224:is
74:)
72:nh
482:.
478::
472:2
459:.
393:)
390:h
381:n
378:(
375:O
361:n
357:h
339:)
336:n
327:n
324:(
321:O
290:)
287:h
284:n
281:(
278:O
268:S
232:P
228:S
198:h
193:0
191:p
189:=
186:h
184:p
180:i
178:=
176:i
167:i
165:p
157:n
155:(
153:O
146:p
144:i
142:p
135:p
130:0
128:p
124:i
84:h
80:n
70:(
68:O
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
