444:
184:
38:
452:
490:: in a simple rectilinear polygon, a maximal square that does not contain a knob is a separator. A square containing a knob may or may not be a separator. The number of different separator squares may be infinite and even uncountable. For example, in a rectangle, every maximal square not touching one of the shorter sides is a separator.
230:
The number of convex corners is four more than the number of concave corners. To see why, imagine that you traverse the boundary of the polygon clockwise (with your right hand inside the polygon and your left hand outside). At a convex corner, you turn 90° right; at any concave corner, you turn 90°
76:. The distinction becomes crucial when spoken about sets of polygons: the latter definition would imply that sides of all polygons in the set are aligned with the same coordinate axes. Within the framework of the second definition it is natural to speak of
440:. For every convex corner, there is exactly one maximal (corner) square covering it, but a single maximal square may cover more than one corner. For every corner, there may by many different maximal rectangles covering it.
514:
is continuous. A maximal continuator is always a corner square. Moreover, a maximal continuator always contains a knob. Hence the number of continuators is always finite and bounded by the number of knobs.
663:
Of particular interest to rectilinear polygons are problems of decomposing a given rectilinear polygon to simple units - usually rectangles or squares. There are several types of decomposition problems:
529:
In a simple rectilinear polygon, every maximal square is either a separator or a continuator. This is also true for rectangles: every maximal rectangle is either a separator or a continuator.
536:
There is an interesting analogy between maximal squares in a simple polygon and nodes in a tree: a continuator is analogous to a leaf node and a separator is analogous to an internal node.
525:
No square can be both a continuator and a separator. In general polygons, there may be squares that are neither continuators nor separators, but in simple polygons this cannot happen:
231:
left. Finally you must make an entire 360° turn and come back to the original point; hence the number of right turns must be 4 more than the number of left turns.
239:
The number of knobs (sides connecting two convex corners) is four more than the number of antiknobs (sides connecting two concave corners).To see why, let
174:: The number of horizontal edges is equal to the number of vertical edges (because every horizontal edge is followed by a vertical edge and vice versa).
683:
problems, the goal is to find a largest set of non-overlapping units whose union is contained in the polygon. The union may be smaller than the polygon.
672:
problems, the goal is to find a smallest set of units (squares or rectangles) whose union is equal to the polygon. The units may overlap. See
518:
There are several different types of continuators, based on the number of knobs they contain and their internal structure (see figure). The
599:
Most of them may be stated for general polygons as well, but expectation of more efficient algorithms warrants a separate consideration
293:
A rectilinear polygon can be covered by a finite number of squares or rectangles with edges parallel to the edges of the polygon (see
191:
A rectilinear polygon has corners of two types: corners in which the smaller angle (90°) is interior to the polygon are called
17:
187:
X marks convex corners; O marks concave corners. Blue lines are knobs; red lines are anti-knobs; yellow lines are neither.
855:
764:
Bar-Yehuda, R.; Ben-Hanoch, E. (1996). "A Linear-Time
Algorithm for Covering Simple Polygons with Similar Rectangles".
690:
problems, the goal is to find a smallest set of non-overlapping units whose union is exactly equal to the polygon. See
738:
730:
143:
297:). It is possible to distinguish several types of squares/rectangles contained in a certain rectilinear polygon
614:
150:
for orthogonal polygons, which leads to more efficient guard coverage than is possible for arbitrary polygons.
135:
due to their simplicity for design and manufacturing. Many manufactured objects result in orthogonal polygons.
61:. Thus the interior angle at each vertex is either 90° or 270°. Rectilinear polygons are a special case of
30:
This article is about right-angled polygons. For "rectilineal figure" as defined in Euclid's
Elements, see
978:
958:
522:
of a continuator is defined as its points that are not covered by any other maximal square (see figure).
73:
1385:
953:
910:
885:
603:
549:
618:
132:
226:
because it has no holes - only a single continuous boundary. It has several interesting properties:
1013:
938:
652:
548:- a rectangle with 2 sides parallel to the x axis and 2 sides parallel to the y axis. See also:
963:
848:
608:
139:
1364:
1304:
943:
704:
591:
is a fractal generated from a sequence of rectilinear polygons with interesting properties.
1248:
1018:
948:
890:
646:
532:
In a simple rectilinear polygon which is not a square, there are at least two continuators.
443:
406:
in even 3 adjacent sides and still not be maximal as it can be stretched in the 4th side.
402:. The second direction is not necessarily true: a rectangle can intersect the boundary of
8:
1354:
1299:
1294:
1253:
968:
718:
568:
147:
320:. Similarly, a maximal rectangle is a rectangle not contained in any other rectangle in
1359:
900:
722:
642:
622:
588:
183:
129:
1339:
933:
841:
734:
691:
62:
868:
820:
773:
673:
581:
294:
559:
is a rectilinear polygon whose side lengths in sequence are consecutive integers.
1334:
1314:
1309:
1279:
998:
973:
905:
628:
124:
The importance of the class of rectilinear polygons comes from the following.
1344:
1324:
1289:
1284:
915:
895:
796:
563:
413:
has at least two points, on two opposite edges, that intersect the boundary of
219:
31:
777:
1379:
1319:
1170:
1063:
983:
925:
632:
1349:
1219:
1175:
1139:
1129:
1124:
97:
54:
811:
Albertson, M. O.; o’Keefe, C. J. (1981). "Covering
Regions with Squares".
791:
717:
378:; the interior of this larger square contains a pair of adjacent edges of
1258:
1165:
1144:
1134:
105:. These adjectives are less confusing when the polygons of this type are
58:
1263:
1119:
1109:
993:
37:
594:
390:
The first direction is also true for rectangles, i.e.: If a rectangle
146:
when restricted to orthogonal polygons. An example is provided by the
1238:
1228:
1205:
1195:
1185:
1114:
1023:
988:
545:
106:
824:
451:
195:
and corners in which the larger angle (270°) is interior are called
1243:
1233:
1190:
1149:
1078:
1068:
1058:
877:
234:
Corollary: every rectilinear polygon has at least 4 convex corners.
833:
766:
International
Journal of Computational Geometry & Applications
288:
1200:
1180:
1093:
1088:
1083:
1073:
1048:
1003:
864:
636:
556:
50:
1008:
1053:
355:, then this pair be pushed further towards the boundary, so
177:
Corollary: Orthogonal polygons have an even number of edges.
259:
the number of convex corners followed by a concave corner,
743:. 1st edition; 2nd printing, corrected and expanded, 1988.
282:
Corollary: every rectilinear polygon has at least 4 knobs.
255:
the number of convex corners followed by a convex corner,
707:, a natural generalization of orthogonal polygons to 3D.
562:
A rectilinear polygon which is not a rectangle is never
128:
They are convenient for the representation of shapes in
206:
is an edge whose two endpoints are convex corners. An
382:, hence this pair does not intersect the boundary of
247:
the number of concave corners. By the previous fact,
763:
544:
The simplest rectilinear polygon is an axis-aligned
210:
is an edge whose two endpoints are concave corners.
595:
Algorithmic problems involving rectilinear polygons
506:such that the intersection between the boundary of
68:In many cases another definition is preferable: a
142:stated in terms of polygons often allow for more
1377:
810:
394:is maximal, then each pair of adjacent edges of
72:is a polygon with sides parallel to the axes of
343:. The proof of both sides is by contradiction:
289:Squares and rectangles in a rectilinear polygon
813:SIAM Journal on Algebraic and Discrete Methods
316:which is not contained in any other square in
159:A rectilinear polygon has edges of two types:
849:
409:Corollary: every maximal square/rectangle in
213:
658:
856:
842:
745:, chapter 8: "The Geometry of Rectangles"
566:, but it can be orthogonally convex. See
759:
757:
755:
753:
727:Computational Geometry - An Introduction
450:
442:
182:
36:
87:Rectilinear polygons are also known as
14:
1378:
837:
750:
41:Some examples of rectilinear polygons
27:Polygon in which all angles are right
267:defined analogously. Then obviously
243:be the number of convex corners and
863:
804:
370:, then there is a larger square in
351:does not intersect the boundary of
218:A rectilinear polygon that is also
24:
335:if each pair of adjacent edges of
25:
1397:
432:such that at least one corner of
539:
617:for orthogonal polygons (e.g.,
784:
615:Boolean operations on polygons
347:If a certain adjacent pair in
277:XX=X-XY=X-(Y-YY)=YY+(X-Y)=YY+4
13:
1:
711:
578:monotone rectilinear polygon
436:overlaps a convex corner of
7:
698:
639:among rectilinear obstacles
584:which is also rectilinear.
398:intersects the boundary of
339:intersects the boundary of
10:
1402:
604:Orthogonal range searching
550:Minimum bounding rectangle
214:Simple rectilinear polygon
84:of a rectilinear polygon.
29:
1272:
1218:
1158:
1102:
1041:
1032:
924:
876:
778:10.1142/S021819599600006X
659:Rectangular decomposition
447:continuator and separator
91:. Other terms in use are
792:"Counting pairs of bits"
154:
653:Maximal empty rectangle
113:is preferred, although
609:Orthogonal convex hull
456:
448:
188:
140:computational geometry
111:axis-aligned rectangle
103:axis-oriented polygons
42:
18:Axis-aligned rectangle
647:Illumination problems
454:
446:
186:
119:rectilinear rectangle
74:Cartesian coordinates
40:
1089:Nonagon/Enneagon (9)
1019:Tangential trapezoid
800:. November 17, 2013.
705:Orthogonal polyhedra
510:and the boundary of
424:is a maximal square
144:efficient algorithms
121:are in use as well.
115:orthogonal rectangle
1201:Megagon (1,000,000)
969:Isosceles trapezoid
719:Franco P. Preparata
643:Visibility problems
571:rectilinear polygon
569:Orthogonally convex
148:art gallery theorem
89:orthogonal polygons
70:rectilinear polygon
47:rectilinear polygon
1171:Icositetragon (24)
723:Michael Ian Shamos
496:continuator square
483:is not connected.
457:
449:
366:is not maximal in
189:
130:integrated circuit
63:isothetic polygons
43:
1386:Types of polygons
1373:
1372:
1214:
1213:
1191:Myriagon (10,000)
1176:Triacontagon (30)
1140:Heptadecagon (17)
1130:Pentadecagon (15)
1125:Tetradecagon (14)
1064:Quadrilateral (4)
934:Antiparallelogram
692:Polygon partition
455:continuator types
16:(Redirected from
1393:
1186:Chiliagon (1000)
1166:Icositrigon (23)
1145:Octadecagon (18)
1135:Hexadecagon (16)
1039:
1038:
858:
851:
844:
835:
834:
829:
828:
808:
802:
801:
788:
782:
781:
761:
744:
674:Polygon covering
582:monotone polygon
461:separator square
295:Polygon covering
78:horizontal edges
21:
1401:
1400:
1396:
1395:
1394:
1392:
1391:
1390:
1376:
1375:
1374:
1369:
1268:
1222:
1210:
1154:
1120:Tridecagon (13)
1110:Hendecagon (11)
1098:
1034:
1028:
999:Right trapezoid
920:
872:
862:
832:
825:10.1137/0602026
809:
805:
790:
789:
785:
762:
751:
741:
714:
701:
661:
629:Motion planning
597:
542:
359:is not maximal.
312:is a square in
291:
222:is also called
216:
157:
109:, and the term
35:
28:
23:
22:
15:
12:
11:
5:
1399:
1389:
1388:
1371:
1370:
1368:
1367:
1362:
1357:
1352:
1347:
1342:
1337:
1332:
1327:
1325:Pseudotriangle
1322:
1317:
1312:
1307:
1302:
1297:
1292:
1287:
1282:
1276:
1274:
1270:
1269:
1267:
1266:
1261:
1256:
1251:
1246:
1241:
1236:
1231:
1225:
1223:
1216:
1215:
1212:
1211:
1209:
1208:
1203:
1198:
1193:
1188:
1183:
1178:
1173:
1168:
1162:
1160:
1156:
1155:
1153:
1152:
1147:
1142:
1137:
1132:
1127:
1122:
1117:
1115:Dodecagon (12)
1112:
1106:
1104:
1100:
1099:
1097:
1096:
1091:
1086:
1081:
1076:
1071:
1066:
1061:
1056:
1051:
1045:
1043:
1036:
1030:
1029:
1027:
1026:
1021:
1016:
1011:
1006:
1001:
996:
991:
986:
981:
976:
971:
966:
961:
956:
951:
946:
941:
936:
930:
928:
926:Quadrilaterals
922:
921:
919:
918:
913:
908:
903:
898:
893:
888:
882:
880:
874:
873:
861:
860:
853:
846:
838:
831:
830:
803:
797:Stack Exchange
783:
748:
747:
746:
739:
713:
710:
709:
708:
700:
697:
696:
695:
684:
677:
660:
657:
656:
655:
650:
640:
626:
612:
606:
596:
593:
541:
538:
534:
533:
530:
492:
491:
388:
387:
360:
331:is maximal in
306:maximal square
290:
287:
286:
285:
284:
283:
237:
236:
235:
215:
212:
181:
180:
179:
178:
156:
153:
152:
151:
136:
82:vertical edges
32:Simple polygon
26:
9:
6:
4:
3:
2:
1398:
1387:
1384:
1383:
1381:
1366:
1365:Weakly simple
1363:
1361:
1358:
1356:
1353:
1351:
1348:
1346:
1343:
1341:
1338:
1336:
1333:
1331:
1328:
1326:
1323:
1321:
1318:
1316:
1313:
1311:
1308:
1306:
1305:Infinite skew
1303:
1301:
1298:
1296:
1293:
1291:
1288:
1286:
1283:
1281:
1278:
1277:
1275:
1271:
1265:
1262:
1260:
1257:
1255:
1252:
1250:
1247:
1245:
1242:
1240:
1237:
1235:
1232:
1230:
1227:
1226:
1224:
1221:
1220:Star polygons
1217:
1207:
1206:Apeirogon (∞)
1204:
1202:
1199:
1197:
1194:
1192:
1189:
1187:
1184:
1182:
1179:
1177:
1174:
1172:
1169:
1167:
1164:
1163:
1161:
1157:
1151:
1150:Icosagon (20)
1148:
1146:
1143:
1141:
1138:
1136:
1133:
1131:
1128:
1126:
1123:
1121:
1118:
1116:
1113:
1111:
1108:
1107:
1105:
1101:
1095:
1092:
1090:
1087:
1085:
1082:
1080:
1077:
1075:
1072:
1070:
1067:
1065:
1062:
1060:
1057:
1055:
1052:
1050:
1047:
1046:
1044:
1040:
1037:
1031:
1025:
1022:
1020:
1017:
1015:
1012:
1010:
1007:
1005:
1002:
1000:
997:
995:
992:
990:
987:
985:
984:Parallelogram
982:
980:
979:Orthodiagonal
977:
975:
972:
970:
967:
965:
962:
960:
959:Ex-tangential
957:
955:
952:
950:
947:
945:
942:
940:
937:
935:
932:
931:
929:
927:
923:
917:
914:
912:
909:
907:
904:
902:
899:
897:
894:
892:
889:
887:
884:
883:
881:
879:
875:
870:
866:
859:
854:
852:
847:
845:
840:
839:
836:
826:
822:
818:
814:
807:
799:
798:
793:
787:
779:
775:
771:
767:
760:
758:
756:
754:
749:
742:
740:0-387-96131-3
736:
732:
728:
724:
720:
716:
715:
706:
703:
702:
693:
689:
685:
682:
678:
675:
671:
667:
666:
665:
654:
651:
648:
644:
641:
638:
634:
633:path planning
630:
627:
624:
620:
616:
613:
610:
607:
605:
602:
601:
600:
592:
590:
585:
583:
579:
574:
572:
570:
565:
560:
558:
553:
551:
547:
540:Special cases
537:
531:
528:
527:
526:
523:
521:
516:
513:
509:
505:
502:in a polygon
501:
497:
489:
486:
485:
484:
482:
478:
474:
470:
466:
463:in a polygon
462:
453:
445:
441:
439:
435:
431:
428:in a polygon
427:
423:
422:corner square
418:
416:
412:
407:
405:
401:
397:
393:
385:
381:
377:
373:
369:
365:
361:
358:
354:
350:
346:
345:
344:
342:
338:
334:
330:
325:
323:
319:
315:
311:
308:in a polygon
307:
302:
300:
296:
281:
280:
278:
274:
273:Y=XY+YY=YX+YY
270:
269:X=XX+XY=XX+YX
266:
262:
258:
254:
250:
246:
242:
238:
233:
232:
229:
228:
227:
225:
221:
211:
209:
205:
200:
198:
194:
185:
176:
175:
173:
170:
169:
168:
166:
162:
149:
145:
141:
137:
134:
131:
127:
126:
125:
122:
120:
116:
112:
108:
104:
100:
99:
94:
90:
85:
83:
79:
75:
71:
66:
64:
60:
56:
53:all of whose
52:
48:
39:
33:
19:
1329:
1159:>20 sides
1094:Decagon (10)
1079:Heptagon (7)
1069:Pentagon (5)
1059:Triangle (3)
954:Equidiagonal
816:
812:
806:
795:
786:
769:
765:
726:
688:partitioning
687:
680:
669:
662:
619:intersection
611:construction
598:
586:
577:
575:
567:
561:
554:
543:
535:
524:
519:
517:
511:
507:
503:
499:
498:is a square
495:
493:
487:
480:
476:
472:
468:
467:is a square
464:
460:
458:
437:
433:
429:
425:
421:
419:
414:
410:
408:
403:
399:
395:
391:
389:
383:
379:
375:
371:
367:
363:
356:
352:
348:
340:
336:
332:
328:
326:
321:
317:
313:
309:
305:
303:
298:
292:
276:
272:
268:
264:
260:
256:
252:
248:
244:
240:
223:
217:
207:
203:
201:
196:
192:
190:
171:
164:
160:
158:
138:Problems in
133:mask layouts
123:
118:
114:
110:
102:
98:axis-aligned
96:
93:iso-oriented
92:
88:
86:
81:
77:
69:
67:
59:right angles
46:
44:
1355:Star-shaped
1330:Rectilinear
1300:Equilateral
1295:Equiangular
1259:Hendecagram
1103:11–20 sides
1084:Octagon (8)
1074:Hexagon (6)
1049:Monogon (1)
891:Equilateral
374:containing
1360:Tangential
1264:Dodecagram
1042:1–10 sides
1033:By number
1014:Tangential
994:Right kite
819:(3): 240.
772:: 79–102.
712:References
475:such that
161:horizontal
107:rectangles
1340:Reinhardt
1249:Enneagram
1239:Heptagram
1229:Pentagram
1196:65537-gon
1054:Digon (2)
1024:Trapezoid
989:Rectangle
939:Bicentric
901:Isosceles
878:Triangles
546:rectangle
327:A square
224:hole-free
1380:Category
1315:Isotoxal
1310:Isogonal
1254:Decagram
1244:Octagram
1234:Hexagram
1035:of sides
964:Harmonic
865:Polygons
731:Springer
725:(1985).
699:See also
670:covering
589:T-square
275:. Hence
208:antiknob
165:vertical
57:meet at
1335:Regular
1280:Concave
1273:Classes
1181:257-gon
1004:Rhombus
944:Crossed
681:packing
637:routing
557:golygon
520:balcony
479:−
197:concave
51:polygon
1345:Simple
1290:Cyclic
1285:Convex
1009:Square
949:Cyclic
911:Obtuse
906:Kepler
737:
564:convex
251:. Let
220:simple
193:convex
101:, and
1320:Magic
916:Right
896:Ideal
886:Acute
623:union
580:is a
488:Lemma
249:X=Y+4
172:Lemma
155:Edges
55:sides
49:is a
1350:Skew
974:Kite
869:List
735:ISBN
721:and
621:and
271:and
263:and
204:knob
163:and
117:and
80:and
821:doi
774:doi
686:In
679:In
668:In
471:in
362:If
167:.
95:,
1382::
815:.
794:.
770:06
768:.
752:^
733:.
729:.
587:A
576:A
573:.
555:A
552:.
494:A
459:A
420:A
417:.
324:.
304:A
301::
279:.
265:YY
261:YX
257:XY
253:XX
202:A
199:.
65:.
45:A
871:)
867:(
857:e
850:t
843:v
827:.
823::
817:2
780:.
776::
694:.
676:.
649:)
645:(
635:/
631:/
625:)
512:P
508:s
504:P
500:s
481:s
477:P
473:P
469:s
465:P
438:P
434:s
430:P
426:s
415:P
411:P
404:P
400:P
396:s
392:s
386:.
384:P
380:s
376:s
372:P
368:P
364:s
357:s
353:P
349:s
341:P
337:s
333:P
329:s
322:P
318:P
314:P
310:P
299:P
245:Y
241:X
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
