39:
47:
221:
365:, polygonal chains are often used to represent the edges of graphs, in drawing styles where drawing the edges as straight line segments would cause crossings, edge-vertex collisions, or other undesired features. In this context, it is often desired to draw edges with as few segments and bends as possible, to reduce the visual clutter in the drawing; the problem of minimizing the number of bends is called
373:
31:
277:
of the parameter corresponding to the index of the first vertex; alternately, each segment of the chain can be assigned an interval of the parameter corresponding to the length of the segment, so that the parameter corresponds uniformly to arclength along the whole chain.
340:
196:
is one in which the first vertex coincides with the last one, or, alternatively, the first and the last vertices are also connected by a line segment. A simple closed polygonal chain in
161:
304:
86:
273:
between successive vertices. For the whole chain, two parametrizations are common in practical applications: Each segment of the chain can be assigned a unit
681:
Douglas, David; Peucker, Thomas (1973), "Algorithms for the reduction of the number of points required to represent a digitized line or its caricature",
447:
355:
879:
845:
818:
638:
608:
896:
397:
624:
343:
562:
443:
208:" is used in the meaning of "closed polygonal chain", but in some cases it is important to draw a distinction between a
401:
781:
471:
309:
787:
OpenGIS® Implementation
Standard for Geographic information - Simple feature access - Part 1: Common architecture
751:
477:
254:
101:
416:
274:
249:
intersects the chain at most once. Every nontrivial monotone polygonal chain is open. In comparison, a
435:
into an ordered sequence of monotone chains, in which a point location query problem may be solved by
253:
is a polygon (a closed chain) that can be partitioned into exactly two monotone chains. The graphs of
738:
518:
489:
270:
494:
428:
358:
can be used to find a polygonal chain with few segments that serves as an accurate approximation.
742:
500:
432:
38:
927:
875:
841:
814:
808:
634:
604:
598:
366:
164:
869:
835:
654:
Ramer, Urs (1972), "An iterative procedure for the polygonal approximation of plane curves",
628:
480:, a generalization that replaces each straight line of a polygonal chain with a smooth curve.
865:
760:
720:
708:
690:
663:
633:, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, p. 45,
474:, a formal combination of simplices that in the 1-dimensional case includes polygonal chains
439:; this method was later refined to give optimal time bounds for the point location problem.
354:
Polygonal chains can often be used to approximate more complex curves. In this context, the
266:
250:
197:
932:
405:
17:
420:
392:. The gray polygonal chain connecting the control points is called the control polygon.
289:
209:
201:
71:
667:
408:
segments. When connected together, the control points form a polygonal chain called a
167:. The curve itself consists of the line segments connecting the consecutive vertices.
46:
921:
594:
486:, the number of segments of the shortest chain that links two points within a polygon
483:
436:
362:
239:
220:
746:
512:
424:
63:
897:"segmented: An R package to fit regression models with broken-line relationships"
184:
is one in which only consecutive segments intersect and only at their endpoints.
694:
446:, linestrings may represent any linear geometry, and can be described using the
372:
785:
711:(1987), "On embedding a graph in the grid with the minimum number of bends",
522:
506:
515:, a knot invariant based on representing a knot as a closed polygonal chain
462:) are closed and simple polygonal chains used to build polygon geometries.
342:
edges in which all slopes have the same sign. This is a corollary of the
95:
55:
205:
840:, Graduate Texts in Mathematics, vol. 208, Springer, p. 13,
30:
764:
724:
371:
91:
45:
37:
29:
749:(1986), "Optimal point location in a monotone subdivision",
600:
871:
257:
form monotone chains with respect to a horizontal line.
228:=17 points has a polygonal path with 4 same-sign slopes
807:
Gomes, Jonas; Velho, Luiz; Costa Sousa, Mario (2012),
415:
Polygonal chains are also a fundamental data type in
312:
292:
104:
74:
376:
A red BĂ©zier curve is defined by the control points
503:, a 3D generalization of a monotone polygonal chain
334:
298:
155:
80:
400:, smooth curves are often defined by a list of
265:Each segment of a polygonal chain is typically
335:{\displaystyle \lfloor {\sqrt {n-1}}\rfloor }
306:points contains a polygonal path of at least
8:
329:
313:
603:, Cambridge University Press, p. 758,
156:{\displaystyle (A_{1},A_{2},\dots ,A_{n})}
497:, an analogous concept in abstract graphs
316:
311:
291:
144:
125:
112:
103:
73:
219:
586:
541:A polygonal chain may also be called a
534:
859:
857:
810:Computer Graphics: Theory and Practice
784:(2011-05-28), Herring, John R. (ed.),
656:Computer Graphics and Image Processing
245:such that every line perpendicular to
776:
774:
7:
790:, 1.2.1, Open Geospatial Consortium
66:. More formally, a polygonal chain
42:A self-intersecting polygonal chain
431:operates by decomposing arbitrary
25:
27:Connected series of line segments
837:Analysis for Applied Mathematics
895:Muggeo, Vito M. R. (May 2008),
398:computer-aided geometric design
356:Ramer–Douglas–Peucker algorithm
563:geographic information systems
150:
105:
1:
668:10.1016/S0146-664X(72)80017-0
444:geographic information system
232:A polygonal chain is called
695:10.3138/FM57-6770-U75U-7727
630:Computational Geometry in C
949:
813:, CRC Press, p. 186,
782:Open Geospatial Consortium
509:, a spiral polygonal chain
472:Chain (algebraic topology)
255:piecewise linear functions
864:Boissonnat, Jean-Daniel;
752:SIAM Journal on Computing
713:SIAM Journal on Computing
683:The Canadian Cartographer
62:is a connected series of
874:, Springer, p. 34,
597:; Näher, Stefan (1999),
50:A closed polygonal chain
34:A simple polygonal chain
18:Monotone polygonal chain
212:and a polygonal chain.
555:piecewise linear curve
478:Composite BĂ©zier curve
417:computational geometry
393:
344:Erdős–Szekeres theorem
336:
300:
286:Every set of at least
229:
194:closed polygonal chain
182:simple polygonal chain
157:
82:
51:
43:
35:
834:Cheney, Ward (2001),
739:Edelsbrunner, Herbert
375:
337:
301:
223:
200:is the boundary of a
158:
83:
49:
41:
33:
490:Piecewise regression
310:
290:
271:linear interpolation
102:
72:
743:Guibas, Leonidas J.
495:Path (graph theory)
458:. Linear rings (or
433:planar subdivisions
404:, e.g. in defining
384:, ...,
501:Polyhedral terrain
419:. For instance, a
394:
332:
296:
230:
204:. Often the term "
153:
78:
52:
44:
36:
866:Teillaud, Monique
709:Tamassia, Roberto
521:, application in
367:bend minimization
327:
299:{\displaystyle n}
81:{\displaystyle P}
16:(Redirected from
940:
912:
911:
901:
892:
886:
884:
861:
852:
850:
831:
825:
823:
804:
798:
797:
796:
795:
778:
769:
767:
735:
729:
727:
705:
699:
697:
678:
672:
670:
651:
645:
643:
625:O'Rourke, Joseph
621:
615:
613:
591:
574:
539:
461:
457:
453:
391:
341:
339:
338:
333:
328:
317:
305:
303:
302:
297:
269:linearly, using
251:monotone polygon
162:
160:
159:
154:
149:
148:
130:
129:
117:
116:
89:
87:
85:
84:
79:
21:
948:
947:
943:
942:
941:
939:
938:
937:
918:
917:
916:
915:
899:
894:
893:
889:
882:
863:
862:
855:
848:
833:
832:
828:
821:
806:
805:
801:
793:
791:
780:
779:
772:
765:10.1137/0215023
737:
736:
732:
725:10.1137/0216030
707:
706:
702:
680:
679:
675:
653:
652:
648:
641:
623:
622:
618:
611:
593:
592:
588:
583:
578:
577:
543:polygonal curve
540:
536:
531:
468:
459:
456:MultiLineString
455:
451:
448:well-known text
410:control polygon
390:
383:
377:
352:
308:
307:
288:
287:
284:
282:From point sets
263:
261:Parametrization
218:
190:
178:
173:
140:
121:
108:
100:
99:
94:specified by a
70:
69:
67:
60:polygonal chain
28:
23:
22:
15:
12:
11:
5:
946:
944:
936:
935:
930:
920:
919:
914:
913:
887:
880:
853:
846:
826:
819:
799:
770:
759:(2): 317–340,
730:
719:(3): 421–444,
700:
689:(2): 112–122,
673:
662:(3): 244–256,
646:
639:
616:
609:
595:Mehlhorn, Kurt
585:
584:
582:
579:
576:
575:
547:polygonal path
533:
532:
530:
527:
526:
525:
516:
510:
504:
498:
492:
487:
481:
475:
467:
464:
421:point location
402:control points
388:
381:
351:
348:
331:
326:
323:
320:
315:
295:
283:
280:
262:
259:
238:if there is a
217:
214:
210:polygonal area
202:simple polygon
189:
186:
177:
174:
172:
169:
152:
147:
143:
139:
136:
133:
128:
124:
120:
115:
111:
107:
77:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
945:
934:
931:
929:
926:
925:
923:
909:
905:
898:
891:
888:
883:
881:9783540332596
877:
873:
872:
867:
860:
858:
854:
849:
847:9780387952796
843:
839:
838:
830:
827:
822:
820:9781568815800
816:
812:
811:
803:
800:
789:
788:
783:
777:
775:
771:
766:
762:
758:
754:
753:
748:
747:Stolfi, Jorge
744:
740:
734:
731:
726:
722:
718:
714:
710:
704:
701:
696:
692:
688:
684:
677:
674:
669:
665:
661:
657:
650:
647:
642:
640:9780521649766
636:
632:
631:
626:
620:
617:
612:
610:9780521563291
606:
602:
601:
596:
590:
587:
580:
572:
568:
564:
560:
556:
552:
548:
544:
538:
535:
528:
524:
520:
517:
514:
511:
508:
505:
502:
499:
496:
493:
491:
488:
485:
484:Link distance
482:
479:
476:
473:
470:
469:
465:
463:
449:
445:
440:
438:
437:binary search
434:
430:
426:
423:algorithm of
422:
418:
413:
411:
407:
403:
399:
387:
380:
374:
370:
368:
364:
363:graph drawing
359:
357:
349:
347:
345:
324:
321:
318:
293:
281:
279:
276:
272:
268:
260:
258:
256:
252:
248:
244:
241:
240:straight line
237:
236:
227:
222:
215:
213:
211:
207:
203:
199:
195:
187:
185:
183:
175:
170:
168:
166:
145:
141:
137:
134:
131:
126:
122:
118:
113:
109:
97:
93:
75:
65:
64:line segments
61:
57:
48:
40:
32:
19:
907:
903:
890:
870:
836:
829:
809:
802:
792:, retrieved
786:
756:
750:
733:
716:
712:
703:
686:
682:
676:
659:
655:
649:
629:
619:
599:
589:
570:
566:
558:
554:
550:
546:
542:
537:
513:Stick number
450:markup as a
441:
414:
409:
406:BĂ©zier curve
395:
385:
378:
360:
353:
350:Applications
285:
267:parametrized
264:
246:
242:
234:
233:
231:
225:
193:
191:
181:
179:
59:
53:
571:linear ring
559:broken line
163:called its
922:Categories
910:(1): 20–25
794:2016-01-15
581:References
567:linestring
460:LinearRing
452:LineString
171:Variations
98:of points
523:surveying
507:Spirangle
429:Preparata
330:⌋
322:−
314:⌊
224:A set of
198:the plane
135:…
928:Polygons
868:(2006),
627:(1998),
551:polyline
519:Traverse
466:See also
275:interval
235:monotone
216:Monotone
165:vertices
96:sequence
56:geometry
561:or, in
206:polygon
88:
68:
933:Curves
904:R News
878:
844:
817:
637:
607:
188:Closed
176:Simple
900:(PDF)
529:Notes
442:With
92:curve
90:is a
876:ISBN
842:ISBN
815:ISBN
635:ISBN
605:ISBN
565:, a
427:and
58:, a
761:doi
721:doi
691:doi
664:doi
569:or
454:or
425:Lee
396:In
361:In
54:In
924::
906:,
902:,
856:^
773:^
757:15
755:,
745:;
741:;
717:16
715:,
687:10
685:,
658:,
557:,
553:,
549:,
545:,
412:.
369:.
346:.
192:A
180:A
908:8
885:.
851:.
824:.
768:.
763::
728:.
723::
698:.
693::
671:.
666::
660:1
644:.
614:.
573:.
389:4
386:P
382:0
379:P
325:1
319:n
294:n
247:L
243:L
226:n
151:)
146:n
142:A
138:,
132:,
127:2
123:A
119:,
114:1
110:A
106:(
76:P
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
