948:
970:
polygon. Alternatively, the vertex with the smallest Y-coordinate among the ones with the largest X-coordinates or the vertex with the smallest X-coordinate among the ones with the largest Y-coordinates (or any other of 8 "smallest, largest" X/Y combinations) will do as well. Once a vertex of the convex hull is chosen, one can then apply the formula using the previous and next vertices, even if those are not on the convex hull, as there can be no local concavity on this vertex.
397:
943:{\displaystyle {\begin{aligned}\det(O)&=1{\begin{vmatrix}x_{B}&y_{B}\\x_{C}&y_{C}\end{vmatrix}}-1{\begin{vmatrix}x_{A}&y_{A}\\x_{C}&y_{C}\end{vmatrix}}+1{\begin{vmatrix}x_{A}&y_{A}\\x_{B}&y_{B}\end{vmatrix}}\\&=x_{B}y_{C}-y_{B}x_{C}-x_{A}y_{C}+y_{A}x_{C}+x_{A}y_{B}-y_{A}x_{B}\\&=(x_{B}y_{C}+x_{A}y_{B}+y_{A}x_{C})-(y_{A}x_{B}+y_{B}x_{C}+x_{A}y_{C}).\end{aligned}}}
25:
1198:
and form a zero-degree angle, the concept of "interior" still makes sense, but an extra care must be taken in selection of the tested angle. In the given example, imagine point A to lie on segment BC. In this situation the angle ABC and its determinant will be 0, hence useless. A solution is to test
969:
One does not need to construct the convex hull of a polygon to find a suitable vertex. A common choice is the vertex of the polygon with the smallest X-coordinate. If there are several of them, the one with the smallest Y-coordinate is picked. It is guaranteed to be a vertex of the convex hull of the
1363:
If the determinant of this matrix is 0, then the sequence is collinear - neither concave nor convex. If the determinant has the same sign as that of the orientation matrix for the entire polygon, then the sequence is convex. If the signs differ, then the sequence is concave. In this example, the
1215:
of a local region of the polygon can be determined using a second orientation matrix. This matrix is composed of three consecutive vertices which are being examined for concavity. For example, in the polygon pictured above, if we wanted to know whether the sequence of points F-G-H is
1358:
382:
205:
1132:
402:
953:
If the determinant is negative, then the polygon is oriented clockwise. If the determinant is positive, the polygon is oriented counterclockwise. The determinant is non-zero if points A, B, and C are
1230:
254:
113:, if one always has the curve interior to the left (and consequently, the curve exterior to the right), when traveling on it. Otherwise, that is if left and right are exchanged, the curve is
236:
of the polygon, for example, of the angle ABC in the picture. In computations, the sign of the smaller angle formed by a pair of vectors is typically determined by the sign of the
1501:
1137:
The latter formula has four multiplications less. What is more important in computer computations involved in most practical applications, such as
986:
1171:) (or for any self-intersecting curve) there is no natural notion of the "interior", hence the orientation is not defined. At the same time, in
105:(that is, a curve in the plane whose starting point is also the end point and which has no other self-intersections), the curve is said to be
248:
with common endpoint, such as the sides BA and BC of the angle ABC in our example, the orientation matrix may be defined as follows:
1160:
When it is not known in advance that the sequence of points defines a simple polygon, the following things must be kept in mind.
958:. In the above example, with points ordered A, B, C, etc., the determinant is negative, and therefore the polygon is clockwise.
1353:{\displaystyle \mathbf {O} ={\begin{bmatrix}1&x_{F}&y_{F}\\1&x_{G}&y_{G}\\1&x_{H}&y_{H}\end{bmatrix}}.}
377:{\displaystyle \mathbf {O} ={\begin{bmatrix}1&x_{A}&y_{A}\\1&x_{B}&y_{B}\\1&x_{C}&y_{C}\end{bmatrix}}.}
1199:
consecutive corners along the polygon (BCD, DEF,...) until a non-zero determinant is found (unless all points lie on the same
1364:
polygon is negatively oriented, but the determinant for the points F-G-H is positive, and so the sequence F-G-H is concave.
121:. This definition relies on the fact that every simple closed curve admits a well-defined interior, which follows from the
132:
of a beltway road in a country where people drive on the right side of the road is an example of a negatively oriented (
65:
1535:
1423:
1179:
there are a number of concepts to replace the notion of the "interior" for closed non-simple curves; see, e.g., "
1367:
The following table illustrates rules for determining whether a sequence of points is convex, concave, or flat:
1498:
40:. In particular, the title and the lead are about curves, and the body of the article is about polygonal lines.
204:
86:
of a curve is the choice of one of the two possible directions for travelling on the curve. For example, for
1203:). (Notice that the points C, D, E are on the same line and form a 180-degree angle with zero determinant.)
175:
1145:, the absolute values of the multipliers are usually smaller (e.g., when A, B, C are within the same
1164:
1146:
156:
1191:
43:
212:
In two dimensions, given an ordered set of three or more connected vertices (points) (such as in
178:
of its points by a real variable. A curve may have equivalent parametrizations when there is a
47:
980:
For numerical reasons, the following equivalent formula for the determinant is commonly used:
1428:
1142:
87:
244:
of their orientation matrix. In the particular case when the two vectors are defined by two
1483:
129:
122:
225:
8:
1154:
966:
In practical applications, the following considerations are commonly taken into account.
179:
102:
35:
1211:
Once the orientation of a polygon formed from an ordered set of vertices is known, the
388:
185:
164:
1540:
1511:
1475:
1443:
1176:
1138:
229:
192:
continuous function relating the parameters, then the parametric representations are
213:
188:
relating the parameter of one curve to the parameter of the other. When there is a
145:
1530:
1505:
1212:
1168:
1150:
163:(that is, besides orientation of a curve one may also speak of orientation of a
1184:
974:
217:
1524:
1433:
1200:
1195:
1127:{\displaystyle \det(O)=(x_{B}-x_{A})(y_{C}-y_{A})-(x_{C}-x_{A})(y_{B}-y_{A})}
237:
1499:
http://www.math.hmc.edu/faculty/gu/curves_and_surfaces/curves/_topology.html
245:
168:
137:
1438:
1217:
387:
A formula for its determinant may be obtained, e.g., using the method of
241:
233:
141:
79:
1221:
1180:
1515:
955:
240:
of the vectors. The latter one may be calculated as the sign of the
133:
1172:
160:
1194:
vertices when three consecutive points are allowed be on the same
221:
1394:
determinant of orientation matrix for local points is positive
1383:
determinant of orientation matrix for local points is negative
94:-axis is traditionally oriented toward the right, and the
1405:
determinant of orientation matrix for local points is 0
1247:
977:
is sought, then, of course, any vertex may be picked.
572:
502:
432:
271:
155:
of a curve is just a particular case of the notion of
1233:
989:
400:
257:
1352:
1126:
942:
376:
199:
1522:
990:
405:
1378:Positively oriented polygon (counterclockwise)
1224:, or collinear (flat), we construct the matrix
196:and the orientation of the curve is reversed.
46:. There might be a discussion about this on
1190:In "mild" cases of self-intersection, with
961:
174:Orientation of a curve is associated with
66:Learn how and when to remove this message
1375:Negatively oriented polygon (clockwise)
16:Property of a planar simple closed curve
1480:A First Course in Differential Geometry
1153:or, in the extreme cases, avoiding the
1523:
1464:Introduction to Differential Geometry
18:
220:, the orientation of the resulting
13:
1206:
203:
14:
1552:
1508:(page is not found on 2023.07.27)
1492:
1235:
259:
23:
1424:Differential geometry of curves
200:Orientation of a simple polygon
1469:
1456:
1121:
1095:
1092:
1066:
1060:
1034:
1031:
1005:
999:
993:
930:
861:
855:
786:
414:
408:
1:
1449:
1411:collinear sequence of points
1408:collinear sequence of points
7:
1417:
1397:concave sequence of points
1389:concave sequence of points
224:is directly related to the
208:Selecting reference points.
10:
1557:
1400:convex sequence of points
1386:convex sequence of points
144:is traditionally oriented
98:-axis is upward oriented.
1466:, page 28, Addison Wesley
1372:
1165:self-intersecting polygon
1149:), thus giving a smaller
111:counterclockwise oriented
973:If the orientation of a
962:Practical considerations
101:In the case of a planar
1536:Orientation (geometry)
1354:
1128:
944:
378:
209:
1484:John Wiley & Sons
1462:Abraham Goetz (1970)
1429:Directed line segment
1355:
1129:
945:
379:
207:
88:Cartesian coordinates
1231:
987:
398:
255:
123:Jordan curve theorem
36:confusing or unclear
1155:arithmetic overflow
115:negatively oriented
107:positively oriented
103:simple closed curve
44:clarify the article
1504:2004-12-23 at the
1350:
1341:
1124:
940:
938:
625:
555:
485:
389:cofactor expansion
374:
365:
210:
186:monotonic function
119:clockwise oriented
1512:Curve orientation
1476:Chuan-Chih Hsiung
1444:Signed arc length
1415:
1414:
1177:computer graphics
1139:computer graphics
226:sign of the angle
76:
75:
68:
1548:
1486:
1473:
1467:
1460:
1370:
1369:
1359:
1357:
1356:
1351:
1346:
1345:
1338:
1337:
1326:
1325:
1307:
1306:
1295:
1294:
1276:
1275:
1264:
1263:
1238:
1133:
1131:
1130:
1125:
1120:
1119:
1107:
1106:
1091:
1090:
1078:
1077:
1059:
1058:
1046:
1045:
1030:
1029:
1017:
1016:
949:
947:
946:
941:
939:
929:
928:
919:
918:
906:
905:
896:
895:
883:
882:
873:
872:
854:
853:
844:
843:
831:
830:
821:
820:
808:
807:
798:
797:
779:
775:
774:
765:
764:
752:
751:
742:
741:
729:
728:
719:
718:
706:
705:
696:
695:
683:
682:
673:
672:
660:
659:
650:
649:
634:
630:
629:
622:
621:
610:
609:
596:
595:
584:
583:
560:
559:
552:
551:
540:
539:
526:
525:
514:
513:
490:
489:
482:
481:
470:
469:
456:
455:
444:
443:
383:
381:
380:
375:
370:
369:
362:
361:
350:
349:
331:
330:
319:
318:
300:
299:
288:
287:
262:
216:) which forms a
214:connect-the-dots
146:counterclockwise
97:
93:
71:
64:
60:
57:
51:
27:
26:
19:
1556:
1555:
1551:
1550:
1549:
1547:
1546:
1545:
1521:
1520:
1506:Wayback Machine
1495:
1490:
1489:
1474:
1470:
1461:
1457:
1452:
1420:
1340:
1339:
1333:
1329:
1327:
1321:
1317:
1315:
1309:
1308:
1302:
1298:
1296:
1290:
1286:
1284:
1278:
1277:
1271:
1267:
1265:
1259:
1255:
1253:
1243:
1242:
1234:
1232:
1229:
1228:
1209:
1207:Local concavity
1169:complex polygon
1151:numerical error
1115:
1111:
1102:
1098:
1086:
1082:
1073:
1069:
1054:
1050:
1041:
1037:
1025:
1021:
1012:
1008:
988:
985:
984:
964:
937:
936:
924:
920:
914:
910:
901:
897:
891:
887:
878:
874:
868:
864:
849:
845:
839:
835:
826:
822:
816:
812:
803:
799:
793:
789:
777:
776:
770:
766:
760:
756:
747:
743:
737:
733:
724:
720:
714:
710:
701:
697:
691:
687:
678:
674:
668:
664:
655:
651:
645:
641:
632:
631:
624:
623:
617:
613:
611:
605:
601:
598:
597:
591:
587:
585:
579:
575:
568:
567:
554:
553:
547:
543:
541:
535:
531:
528:
527:
521:
517:
515:
509:
505:
498:
497:
484:
483:
477:
473:
471:
465:
461:
458:
457:
451:
447:
445:
439:
435:
428:
427:
417:
401:
399:
396:
395:
364:
363:
357:
353:
351:
345:
341:
339:
333:
332:
326:
322:
320:
314:
310:
308:
302:
301:
295:
291:
289:
283:
279:
277:
267:
266:
258:
256:
253:
252:
202:
176:parametrization
151:The concept of
95:
91:
72:
61:
55:
52:
41:
28:
24:
17:
12:
11:
5:
1554:
1544:
1543:
1538:
1533:
1519:
1518:
1509:
1494:
1493:External links
1491:
1488:
1487:
1468:
1454:
1453:
1451:
1448:
1447:
1446:
1441:
1436:
1431:
1426:
1419:
1416:
1413:
1412:
1409:
1406:
1402:
1401:
1398:
1395:
1391:
1390:
1387:
1384:
1380:
1379:
1376:
1373:
1361:
1360:
1349:
1344:
1336:
1332:
1328:
1324:
1320:
1316:
1314:
1311:
1310:
1305:
1301:
1297:
1293:
1289:
1285:
1283:
1280:
1279:
1274:
1270:
1266:
1262:
1258:
1254:
1252:
1249:
1248:
1246:
1241:
1237:
1208:
1205:
1185:winding number
1135:
1134:
1123:
1118:
1114:
1110:
1105:
1101:
1097:
1094:
1089:
1085:
1081:
1076:
1072:
1068:
1065:
1062:
1057:
1053:
1049:
1044:
1040:
1036:
1033:
1028:
1024:
1020:
1015:
1011:
1007:
1004:
1001:
998:
995:
992:
975:convex polygon
963:
960:
951:
950:
935:
932:
927:
923:
917:
913:
909:
904:
900:
894:
890:
886:
881:
877:
871:
867:
863:
860:
857:
852:
848:
842:
838:
834:
829:
825:
819:
815:
811:
806:
802:
796:
792:
788:
785:
782:
780:
778:
773:
769:
763:
759:
755:
750:
746:
740:
736:
732:
727:
723:
717:
713:
709:
704:
700:
694:
690:
686:
681:
677:
671:
667:
663:
658:
654:
648:
644:
640:
637:
635:
633:
628:
620:
616:
612:
608:
604:
600:
599:
594:
590:
586:
582:
578:
574:
573:
571:
566:
563:
558:
550:
546:
542:
538:
534:
530:
529:
524:
520:
516:
512:
508:
504:
503:
501:
496:
493:
488:
480:
476:
472:
468:
464:
460:
459:
454:
450:
446:
442:
438:
434:
433:
431:
426:
423:
420:
418:
416:
413:
410:
407:
404:
403:
385:
384:
373:
368:
360:
356:
352:
348:
344:
340:
338:
335:
334:
329:
325:
321:
317:
313:
309:
307:
304:
303:
298:
294:
290:
286:
282:
278:
276:
273:
272:
270:
265:
261:
218:simple polygon
201:
198:
74:
73:
31:
29:
22:
15:
9:
6:
4:
3:
2:
1553:
1542:
1539:
1537:
1534:
1532:
1529:
1528:
1526:
1517:
1513:
1510:
1507:
1503:
1500:
1497:
1496:
1485:
1481:
1477:
1472:
1465:
1459:
1455:
1445:
1442:
1440:
1437:
1435:
1434:Orientability
1432:
1430:
1427:
1425:
1422:
1421:
1410:
1407:
1404:
1403:
1399:
1396:
1393:
1392:
1388:
1385:
1382:
1381:
1377:
1374:
1371:
1368:
1365:
1347:
1342:
1334:
1330:
1322:
1318:
1312:
1303:
1299:
1291:
1287:
1281:
1272:
1268:
1260:
1256:
1250:
1244:
1239:
1227:
1226:
1225:
1223:
1219:
1214:
1204:
1202:
1201:straight line
1197:
1196:straight line
1193:
1188:
1186:
1182:
1178:
1174:
1170:
1166:
1161:
1158:
1156:
1152:
1148:
1144:
1140:
1116:
1112:
1108:
1103:
1099:
1087:
1083:
1079:
1074:
1070:
1063:
1055:
1051:
1047:
1042:
1038:
1026:
1022:
1018:
1013:
1009:
1002:
996:
983:
982:
981:
978:
976:
971:
967:
959:
957:
933:
925:
921:
915:
911:
907:
902:
898:
892:
888:
884:
879:
875:
869:
865:
858:
850:
846:
840:
836:
832:
827:
823:
817:
813:
809:
804:
800:
794:
790:
783:
781:
771:
767:
761:
757:
753:
748:
744:
738:
734:
730:
725:
721:
715:
711:
707:
702:
698:
692:
688:
684:
679:
675:
669:
665:
661:
656:
652:
646:
642:
638:
636:
626:
618:
614:
606:
602:
592:
588:
580:
576:
569:
564:
561:
556:
548:
544:
536:
532:
522:
518:
510:
506:
499:
494:
491:
486:
478:
474:
466:
462:
452:
448:
440:
436:
429:
424:
421:
419:
411:
394:
393:
392:
390:
371:
366:
358:
354:
346:
342:
336:
327:
323:
315:
311:
305:
296:
292:
284:
280:
274:
268:
263:
251:
250:
249:
247:
246:line segments
243:
239:
238:cross product
235:
231:
227:
223:
219:
215:
206:
197:
195:
191:
187:
184:
181:
177:
172:
170:
166:
162:
158:
154:
149:
147:
143:
139:
136:) curve. In
135:
131:
126:
124:
120:
116:
112:
108:
104:
99:
89:
85:
81:
70:
67:
59:
49:
48:the talk page
45:
39:
37:
32:This article
30:
21:
20:
1479:
1471:
1463:
1458:
1366:
1362:
1210:
1189:
1162:
1159:
1136:
979:
972:
968:
965:
952:
386:
211:
193:
189:
182:
173:
169:hypersurface
152:
150:
138:trigonometry
127:
118:
114:
110:
106:
100:
83:
77:
62:
53:
42:Please help
33:
1482:, page 84,
1439:Convex hull
242:determinant
234:convex hull
157:orientation
153:orientation
142:unit circle
84:orientation
80:mathematics
1525:Categories
1450:References
1192:degenerate
1181:flood fill
190:decreasing
183:increasing
180:continuous
130:inner loop
38:to readers
1516:MathWorld
1213:concavity
1109:−
1080:−
1064:−
1048:−
1019:−
956:collinear
859:−
754:−
685:−
662:−
492:−
171:, etc.).
134:clockwise
56:June 2020
1541:Polygons
1502:Archived
1418:See also
1173:geometry
1147:quadrant
194:opposite
161:manifold
1478:(1981)
1218:concave
1183:" and "
232:of the
228:at any
222:polygon
165:surface
34:may be
1531:Curves
1222:convex
1163:For a
230:vertex
140:, the
90:, the
159:of a
82:, an
1175:and
954:non-
128:The
1514:at
1187:".
1143:CAD
1141:or
991:det
406:det
117:or
109:or
78:In
1527::
1220:,
1157:.
391::
167:,
148:.
125:.
1348:.
1343:]
1335:H
1331:y
1323:H
1319:x
1313:1
1304:G
1300:y
1292:G
1288:x
1282:1
1273:F
1269:y
1261:F
1257:x
1251:1
1245:[
1240:=
1236:O
1167:(
1122:)
1117:A
1113:y
1104:B
1100:y
1096:(
1093:)
1088:A
1084:x
1075:C
1071:x
1067:(
1061:)
1056:A
1052:y
1043:C
1039:y
1035:(
1032:)
1027:A
1023:x
1014:B
1010:x
1006:(
1003:=
1000:)
997:O
994:(
934:.
931:)
926:C
922:y
916:A
912:x
908:+
903:C
899:x
893:B
889:y
885:+
880:B
876:x
870:A
866:y
862:(
856:)
851:C
847:x
841:A
837:y
833:+
828:B
824:y
818:A
814:x
810:+
805:C
801:y
795:B
791:x
787:(
784:=
772:B
768:x
762:A
758:y
749:B
745:y
739:A
735:x
731:+
726:C
722:x
716:A
712:y
708:+
703:C
699:y
693:A
689:x
680:C
676:x
670:B
666:y
657:C
653:y
647:B
643:x
639:=
627:|
619:B
615:y
607:B
603:x
593:A
589:y
581:A
577:x
570:|
565:1
562:+
557:|
549:C
545:y
537:C
533:x
523:A
519:y
511:A
507:x
500:|
495:1
487:|
479:C
475:y
467:C
463:x
453:B
449:y
441:B
437:x
430:|
425:1
422:=
415:)
412:O
409:(
372:.
367:]
359:C
355:y
347:C
343:x
337:1
328:B
324:y
316:B
312:x
306:1
297:A
293:y
285:A
281:x
275:1
269:[
264:=
260:O
96:y
92:x
69:)
63:(
58:)
54:(
50:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
