244:
of the convex hull, and lies 'inside' it. The same determination is then made for the set of the latest point and the two points that immediately precede the point found to have been inside the hull, and is repeated until a "left turn" set is encountered, at which point the algorithm moves on to the next point in the set of points in the sorted array minus any points that were found to be inside the hull; there is no need to consider these points again. (If at any stage the three points are collinear, one may opt either to discard or to report it, since in some applications it is required to find all points on the boundary of the convex hull.)
681:
71:
132:
20:
957:
The pseudocode below uses a function ccw: ccw > 0 if three points make a counter-clockwise turn, ccw < 0 if clockwise, and ccw = 0 if collinear. (In real applications, if the coordinates are arbitrary real numbers, the function requires exact comparison of floating-point numbers, and one has to
243:
The algorithm proceeds by considering each of the points in the sorted array in sequence. For each point, it is first determined whether traveling from the two points immediately preceding this point constitutes making a left turn or a right turn. If a right turn, the second-to-last point is not part
1090:
computer arithmetic. A 2004 paper analyzed a simple incremental strategy, which can be used, in particular, for an implementation of the Graham scan. The stated goal of the paper was not to specifically analyze the algorithm, but rather to provide a textbook example of what and how may fail due to
1052:
The same basic idea works also if the input is sorted on x-coordinate instead of angle, and the hull is computed in two steps producing the upper and the lower parts of the hull respectively. This modification was devised by A. M. Andrew. It has the same basic properties as Graham's scan.
139:
The first step in this algorithm is to find the point with the lowest y-coordinate. If the lowest y-coordinate exists in more than one point in the set, the point with the lowest x-coordinate out of the candidates should be chosen. Call this point
1060:, rather than one of its vertices. For the same choice of a pivot point for the sorting algorithm, connecting all of the other points in their sorted order around this point rather than performing the remaining steps of the Graham scan produces a
1246:
Arkin, Esther M.; Fekete, Sándor P.; Hurtado, Ferran; Mitchell, Joseph S. B.; Noy, Marc; Sacristán, Vera; Sethia, Saurabh (2003). "On the reflexivity of point sets". In Aronov, Boris; Basu, Saugata; Pach, János; Sharir, Micha (eds.).
664:. If the result is 0, the points are collinear; if it is positive, the three points constitute a "left turn" or counter-clockwise orientation, otherwise a "right turn" or clockwise orientation (for counter-clockwise numbered points).
247:
Again, determining whether three points constitute a "left turn" or a "right turn" does not require computing the actual angle between the two line segments, and can actually be achieved with simple arithmetic only. For three points
1103:
problem, and therefore one may expect algorithms which produce an answer within a reasonable error margin. Second, they demonstrate that a modification of Graham scan which they call Graham-Fortune (incorporating ideas of
662:
135:
As one can see, PAB and ABC are counterclockwise, but BCD is not. The algorithm detects this situation and discards previously chosen segments until the turn taken is counterclockwise (ABD in this case.)
667:
This process will eventually return to the point at which it started, at which point the algorithm is completed and the stack now contains the points on the convex hull in counterclockwise order.
526:
480:
423:
364:
305:
939:
893:
847:
801:
1075:
problem, and parallel algorithms for all nearest smaller values may also be used (like Graham's scan) to compute convex hulls of sorted sequences of points efficiently.
215:
221:, or the slope of the line may be used. If numeric precision is at stake, the comparison function used by the sorting algorithm can use the sign of the
1401:
1264:
1230:
531:
182:
Sorting in order of angle does not require computing the angle. It is possible to use any function of the angle which is monotonic in the
53:, who published the original algorithm in 1972. The algorithm finds all vertices of the convex hull ordered along its boundary. It uses a
1377:
1108:
for numeric stability) does overcome the problems of finite precision and inexact data "to whatever extent it is possible to do so".
1477:
1424:
1386:
728:
118:
1210:
1496:
706:
96:
702:
92:
691:
81:
753:), because for each point it goes back to check if any of the previous points make a "right turn", it is actually O(
485:
439:
1467:
1072:
1040:
1024:
Now the stack contains the convex hull, where the points are oriented counter-clockwise and P0 is the first point.
54:
1031:
is a function for returning the item one entry below the top of stack, without changing the stack, and similarly,
710:
695:
100:
85:
1096:
757:), because each point is considered at most twice in some sense. Each point can appear only once as a point
1305:
1117:
1092:
183:
369:
310:
251:
1430:
1338:
987:
points by polar angle with P0, if several points have the same polar angle then only keep the farthest
1296:(1993). "Optimal double logarithmic parallel algorithms based on finding all nearest smaller values".
1455:
1083:
240:
for easier computation, since the points lie on the same ray), or delete all but the furthest point.
1105:
1310:
1061:
898:
852:
806:
760:
1214:
434:
237:
233:
1473:
1420:
1374:
1260:
1226:
164:
995:
points: # pop the last point from the stack if we turn clockwise to reach this point
1451:
1412:
1353:
1315:
1252:
1218:
1202:
1183:
1156:
1100:
1065:
229:
1274:
1141:
159:
Next, the set of points must be sorted in increasing order of the angle they and the point
1381:
1289:
1270:
35:
1203:
1174:
Andrew, A. M. (1979). "Another efficient algorithm for convex hulls in two dimensions".
1463:
1087:
145:
38:
188:
1490:
1187:
1160:
430:
222:
50:
1384:, Computational Science and Its Applications - ICCSA 2006 Volume 3980 of the series
228:
If several points are of the same angle, either break ties by increasing distance (
1251:. Algorithms and Combinatorics. Vol. 25. Berlin: Springer. pp. 139–156.
949:), since the time to sort dominates the time to actually compute the convex hull.
1358:
1337:
Kettner, Lutz; Mehlhorn, Kurt; Pion, Sylvain; Schirra, Stefan; Yap, Chee (2008).
1293:
1256:
1057:
680:
218:
70:
31:
1142:"An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set"
1056:
Graham's original description involved sorting around an interior point of the
1459:
1222:
1416:
19:
1319:
1201:
De Berg, Mark; Cheong, Otfried; Van
Kreveld, Marc; Overmars, Mark (2008).
1071:
The stack technique used in Graham's scan is very similar to that for the
168:
131:
1339:"Classroom examples of robustness problems in geometric computations"
1099:
made two primary conclusions. The first is that the convex hull is a
657:{\displaystyle (x_{2}-x_{1})(y_{3}-y_{1})-(y_{2}-y_{1})(x_{3}-x_{1})}
1249:
Discrete and
Computational Geometry: The Goodman-Pollack Festschrift
1095:. Later D. Jiang and N. F. Stewart elaborated on this and using the
803:
in a "left turn" (because the algorithm advances to the next point
1402:"Stable maintenance of point set triangulations in two dimensions"
130:
1086:
is an issue to deal with in algorithms that use finite-precision
958:
beware of numeric singularities for "nearly" collinear points.)
749:). While it may seem that the time complexity of the loop is O(
674:
64:
57:
to detect and remove concavities in the boundary efficiently.
1472:(2nd ed.). MIT Press and McGraw-Hill. pp. 949–955.
1006:(next_to_top(stack), top(stack), point) <= 0:
1409:
30th Annual
Symposium on Foundations of Computer Science
941:
is removed). The overall time complexity is therefore O(
16:
Algorithm for computing convex hulls in a set of points
983:
the lowest y-coordinate and leftmost point, called P0
1364:(An earlier version was reported in 2004 at ESA'2004)
901:
855:
809:
763:
534:
488:
442:
372:
313:
254:
191:
1205:Computational Geometry Algorithms and Applications
933:
887:
841:
795:
656:
520:
474:
417:
358:
299:
209:
1375:Backward error analysis in computational geometry
23:A demo of Graham's scan to find a 2D convex hull.
521:{\displaystyle {\overrightarrow {P_{1}P_{3}}}}
475:{\displaystyle {\overrightarrow {P_{1}P_{2}}}}
8:
34:of a finite set of points in the plane with
709:. Unsourced material may be challenged and
217:. The cosine is easily computed using the
99:. Unsourced material may be challenged and
1466:(2001) . "33.3: Finding the convex hull".
163:make with the x-axis. Any general-purpose
1357:
1309:
922:
909:
900:
876:
863:
854:
830:
817:
808:
784:
771:
762:
741:Sorting the points has time complexity O(
729:Learn how and when to remove this message
645:
632:
616:
603:
584:
571:
555:
542:
533:
506:
496:
489:
487:
460:
450:
443:
441:
406:
393:
377:
371:
347:
334:
318:
312:
288:
275:
259:
253:
190:
119:Learn how and when to remove this message
18:
1332:
1330:
1129:
1135:
1133:
961:Then let the result be stored in the
895:in a "right turn" (because the point
167:is appropriate for this, for example
156:is the number of points in question.
7:
707:adding citations to reliable sources
97:adding citations to reliable sources
1035:for returning the topmost element.
528:, which is given by the expression
418:{\displaystyle P_{3}=(x_{3},y_{3})}
359:{\displaystyle P_{2}=(x_{2},y_{2})}
300:{\displaystyle P_{1}=(x_{1},y_{1})}
1411:. Vol. 30. pp. 494–499.
14:
1387:Lecture Notes in Computer Science
1038:This pseudocode is adapted from
679:
236:distance may be used instead of
69:
1091:floating-point computations in
1176:Information Processing Letters
1149:Information Processing Letters
928:
902:
882:
856:
836:
810:
790:
764:
651:
625:
622:
596:
590:
564:
561:
535:
412:
386:
353:
327:
294:
268:
225:to determine relative angles.
204:
192:
1:
934:{\displaystyle (x_{2},y_{2})}
888:{\displaystyle (x_{2},y_{2})}
842:{\displaystyle (x_{3},y_{3})}
796:{\displaystyle (x_{2},y_{2})}
1373:D. Jiang and N. F. Stewart,
1359:10.1016/j.comgeo.2007.06.003
1188:10.1016/0020-0190(79)90072-3
1161:10.1016/0020-0190(72)90045-2
849:after that), and as a point
1257:10.1007/978-3-642-55566-4_6
30:is a method of finding the
1513:
1469:Introduction to Algorithms
1073:all nearest smaller values
1041:Introduction to Algorithms
1223:10.1007/978-3-540-77974-2
1400:Fortune, Steven (1989).
1417:10.1109/SFCS.1989.63524
1097:backward error analysis
1497:Convex hull algorithms
1346:Computational Geometry
1320:10.1006/jagm.1993.1018
1118:Convex hull algorithms
1093:computational geometry
979:stack = empty_stack()
935:
889:
843:
797:
658:
522:
476:
419:
360:
301:
211:
136:
24:
1456:Leiserson, Charles E.
1298:Journal of Algorithms
1140:Graham, R.L. (1972).
936:
890:
844:
798:
659:
523:
477:
420:
361:
302:
212:
134:
49:). It is named after
22:
1084:Numerical robustness
1079:Numerical robustness
899:
853:
807:
761:
703:improve this section
532:
486:
440:
370:
311:
252:
189:
93:improve this section
1062:star-shaped polygon
975:the list of points
429:-coordinate of the
1380:2017-08-09 at the
931:
885:
839:
793:
654:
518:
472:
415:
356:
297:
207:
144:. This step takes
137:
25:
1460:Rivest, Ronald L.
1452:Cormen, Thomas H.
1266:978-3-642-62442-1
1232:978-3-540-77973-5
1002:stack > 1 and
739:
738:
731:
516:
470:
165:sorting algorithm
129:
128:
121:
1504:
1483:
1438:
1437:
1435:
1429:. Archived from
1406:
1397:
1391:
1371:
1365:
1363:
1361:
1343:
1334:
1325:
1323:
1313:
1290:Schieber, Baruch
1285:
1279:
1278:
1243:
1237:
1236:
1208:
1198:
1192:
1191:
1171:
1165:
1164:
1146:
1137:
1101:well-conditioned
1066:polygonalization
1034:
1030:
964:
940:
938:
937:
932:
927:
926:
914:
913:
894:
892:
891:
886:
881:
880:
868:
867:
848:
846:
845:
840:
835:
834:
822:
821:
802:
800:
799:
794:
789:
788:
776:
775:
734:
727:
723:
720:
714:
683:
675:
663:
661:
660:
655:
650:
649:
637:
636:
621:
620:
608:
607:
589:
588:
576:
575:
560:
559:
547:
546:
527:
525:
524:
519:
517:
512:
511:
510:
501:
500:
490:
481:
479:
478:
473:
471:
466:
465:
464:
455:
454:
444:
424:
422:
421:
416:
411:
410:
398:
397:
382:
381:
365:
363:
362:
357:
352:
351:
339:
338:
323:
322:
306:
304:
303:
298:
293:
292:
280:
279:
264:
263:
216:
214:
213:
210:{\displaystyle }
208:
124:
117:
113:
110:
104:
73:
65:
1512:
1511:
1507:
1506:
1505:
1503:
1502:
1501:
1487:
1486:
1480:
1464:Stein, Clifford
1450:
1447:
1445:Further reading
1442:
1441:
1433:
1427:
1404:
1399:
1398:
1394:
1382:Wayback Machine
1372:
1368:
1341:
1336:
1335:
1328:
1288:Berkman, Omer;
1287:
1286:
1282:
1267:
1245:
1244:
1240:
1233:
1200:
1199:
1195:
1173:
1172:
1168:
1144:
1139:
1138:
1131:
1126:
1114:
1081:
1050:
1032:
1028:
1022:
962:
955:
918:
905:
897:
896:
872:
859:
851:
850:
826:
813:
805:
804:
780:
767:
759:
758:
735:
724:
718:
715:
700:
684:
673:
671:Time complexity
641:
628:
612:
599:
580:
567:
551:
538:
530:
529:
502:
492:
491:
484:
483:
456:
446:
445:
438:
437:
402:
389:
373:
368:
367:
343:
330:
314:
309:
308:
284:
271:
255:
250:
249:
187:
186:
125:
114:
108:
105:
90:
74:
63:
36:time complexity
17:
12:
11:
5:
1510:
1508:
1500:
1499:
1489:
1488:
1485:
1484:
1478:
1446:
1443:
1440:
1439:
1436:on 2013-07-28.
1425:
1392:
1366:
1326:
1311:10.1.1.55.5669
1304:(3): 344–370.
1280:
1265:
1238:
1231:
1193:
1182:(5): 216–219.
1166:
1155:(4): 132–133.
1128:
1127:
1125:
1122:
1121:
1120:
1113:
1110:
1106:Steven Fortune
1088:floating-point
1080:
1077:
1068:of the input.
1049:
1046:
967:
954:
951:
930:
925:
921:
917:
912:
908:
904:
884:
879:
875:
871:
866:
862:
858:
838:
833:
829:
825:
820:
816:
812:
792:
787:
783:
779:
774:
770:
766:
737:
736:
687:
685:
678:
672:
669:
653:
648:
644:
640:
635:
631:
627:
624:
619:
615:
611:
606:
602:
598:
595:
592:
587:
583:
579:
574:
570:
566:
563:
558:
554:
550:
545:
541:
537:
515:
509:
505:
499:
495:
469:
463:
459:
453:
449:
425:, compute the
414:
409:
405:
401:
396:
392:
388:
385:
380:
376:
355:
350:
346:
342:
337:
333:
329:
326:
321:
317:
296:
291:
287:
283:
278:
274:
270:
267:
262:
258:
206:
203:
200:
197:
194:
127:
126:
77:
75:
68:
62:
59:
15:
13:
10:
9:
6:
4:
3:
2:
1509:
1498:
1495:
1494:
1492:
1481:
1479:0-262-03293-7
1475:
1471:
1470:
1465:
1461:
1457:
1453:
1449:
1448:
1444:
1432:
1428:
1426:0-8186-1982-1
1422:
1418:
1414:
1410:
1403:
1396:
1393:
1389:
1388:
1383:
1379:
1376:
1370:
1367:
1360:
1355:
1351:
1347:
1340:
1333:
1331:
1327:
1321:
1317:
1312:
1307:
1303:
1299:
1295:
1291:
1284:
1281:
1276:
1272:
1268:
1262:
1258:
1254:
1250:
1242:
1239:
1234:
1228:
1224:
1220:
1216:
1212:
1207:
1206:
1197:
1194:
1189:
1185:
1181:
1177:
1170:
1167:
1162:
1158:
1154:
1150:
1143:
1136:
1134:
1130:
1123:
1119:
1116:
1115:
1111:
1109:
1107:
1102:
1098:
1094:
1089:
1085:
1078:
1076:
1074:
1069:
1067:
1063:
1059:
1054:
1047:
1045:
1043:
1042:
1036:
1029:next_to_top()
1025:
1021:
1017:
1013:
1009:
1005:
1001:
998:
994:
990:
986:
982:
978:
974:
970:
966:
959:
952:
950:
948:
944:
923:
919:
915:
910:
906:
877:
873:
869:
864:
860:
831:
827:
823:
818:
814:
785:
781:
777:
772:
768:
756:
752:
748:
744:
733:
730:
722:
719:February 2024
712:
708:
704:
698:
697:
693:
688:This section
686:
682:
677:
676:
670:
668:
665:
646:
642:
638:
633:
629:
617:
613:
609:
604:
600:
593:
585:
581:
577:
572:
568:
556:
552:
548:
543:
539:
513:
507:
503:
497:
493:
467:
461:
457:
451:
447:
436:
432:
431:cross product
428:
407:
403:
399:
394:
390:
383:
378:
374:
348:
344:
340:
335:
331:
324:
319:
315:
289:
285:
281:
276:
272:
265:
260:
256:
245:
241:
239:
235:
231:
226:
224:
223:cross product
220:
201:
198:
195:
185:
180:
178:
174:
170:
166:
162:
157:
155:
151:
147:
143:
133:
123:
120:
112:
109:February 2024
102:
98:
94:
88:
87:
83:
78:This section
76:
72:
67:
66:
60:
58:
56:
52:
51:Ronald Graham
48:
44:
40:
37:
33:
29:
28:Graham's scan
21:
1468:
1431:the original
1408:
1395:
1385:
1369:
1352:(1): 61–78.
1349:
1345:
1301:
1297:
1294:Vishkin, Uzi
1283:
1248:
1241:
1204:
1196:
1179:
1175:
1169:
1152:
1148:
1082:
1070:
1055:
1051:
1039:
1037:
1026:
1023:
1019:
1015:
1011:
1007:
1003:
999:
996:
992:
988:
984:
980:
976:
972:
968:
960:
956:
946:
942:
754:
750:
746:
742:
740:
725:
716:
701:Please help
689:
666:
426:
246:
242:
227:
181:
176:
172:
171:(which is O(
160:
158:
153:
149:
141:
138:
115:
106:
91:Please help
79:
46:
42:
27:
26:
1213:. pp.
1058:convex hull
433:of the two
219:dot product
32:convex hull
1390:, pp 50–59
1209:. Berlin:
1124:References
1010:stack
953:Pseudocode
1306:CiteSeerX
690:does not
639:−
610:−
594:−
578:−
549:−
514:→
468:→
238:Euclidean
234:Chebyshev
230:Manhattan
202:π
152:), where
80:does not
61:Algorithm
1491:Category
1378:Archived
1211:Springer
1112:See also
184:interval
169:heapsort
1275:2038472
971:points
711:removed
696:sources
435:vectors
101:removed
86:sources
1476:
1423:
1308:
1273:
1263:
1229:
1027:Here,
1018:stack
1014:point
991:point
1434:(PDF)
1405:(PDF)
1342:(PDF)
1217:–14.
1145:(PDF)
1048:Notes
1033:top()
1000:count
997:while
963:stack
55:stack
1474:ISBN
1421:ISBN
1261:ISBN
1227:ISBN
1064:, a
1012:push
985:sort
981:find
945:log
745:log
694:any
692:cite
482:and
366:and
179:)).
175:log
84:any
82:cite
45:log
1413:doi
1354:doi
1316:doi
1253:doi
1219:doi
1184:doi
1157:doi
1020:end
1008:pop
1004:ccw
989:for
977:let
969:let
705:by
232:or
95:by
1493::
1462:;
1458:;
1454:;
1419:.
1407:.
1350:40
1348:.
1344:.
1329:^
1314:.
1302:14
1300:.
1292:;
1271:MR
1269:.
1259:.
1225:.
1178:.
1151:.
1147:.
1132:^
1044:.
1016:to
993:in
973:be
965:.
307:,
1482:.
1415::
1362:.
1356::
1324:.
1322:.
1318::
1277:.
1255::
1235:.
1221::
1215:2
1190:.
1186::
1180:9
1163:.
1159::
1153:1
947:n
943:n
929:)
924:2
920:y
916:,
911:2
907:x
903:(
883:)
878:2
874:y
870:,
865:2
861:x
857:(
837:)
832:3
828:y
824:,
819:3
815:x
811:(
791:)
786:2
782:y
778:,
773:2
769:x
765:(
755:n
751:n
747:n
743:n
732:)
726:(
721:)
717:(
713:.
699:.
652:)
647:1
643:x
634:3
630:x
626:(
623:)
618:1
614:y
605:2
601:y
597:(
591:)
586:1
582:y
573:3
569:y
565:(
562:)
557:1
553:x
544:2
540:x
536:(
508:3
504:P
498:1
494:P
462:2
458:P
452:1
448:P
427:z
413:)
408:3
404:y
400:,
395:3
391:x
387:(
384:=
379:3
375:P
354:)
349:2
345:y
341:,
336:2
332:x
328:(
325:=
320:2
316:P
295:)
290:1
286:y
282:,
277:1
273:x
269:(
266:=
261:1
257:P
205:]
199:,
196:0
193:[
177:n
173:n
161:P
154:n
150:n
148:(
146:O
142:P
122:)
116:(
111:)
107:(
103:.
89:.
47:n
43:n
41:(
39:O
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
