Polygon trapezoidation by sets of open trapezoids
Povzetek
A new efficient algorithm is described for the simple trapezoidation of polygons based on a sweep-line paradigm. As the sweep-line glides over the plane, a set of so-called open trapezoids is generated and maintained. It is shown that a boundary case (more polygon vertices are located on the sweep-line) can be solved safely and does not slow down the algorithm. If desired, the polygon holes can be trapezoidated simultaneously. This proposed algorithm when compared with the fastest known algorithm developed by Seidel resulted in more efficiency for different classes of polygons.
Ključne besede
mnogokotniki;deljenje mnogokotnikov;trapezoidacija;računalniška geometrija;
Podatki
| Jezik: | Angleški jezik |
|---|---|
| Leto izida: | 2003 |
| Tipologija: | 1.01 - Izvirni znanstveni članek |
| Organizacija: | UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko |
| UDK: | 004.4:514.116 |
| COBISS: |
8326422
|
| ISSN: | 0097-8493 |
| Št. ogledov: | 1394 |
| Št. prenosov: | 111 |
| Ocena: | 0 (0 glasov) |
| Metapodatki: |
|
Ostali podatki
| Sekundarni jezik: | Angleški jezik |
|---|---|
| Sekundarne ključne besede: | polygon;polygon decomposition;trapezoidation;computational geometry; |
| URN: | URN:SI:UM: |
| Strani: | str. 791-800 |
| Letnik: | ǂVol. ǂ27 |
| Zvezek: | ǂiss. ǂ5 |
| Čas izdaje: | 2003 |
| ID: | 8718865 |
Priporočena dela:
Polygon trapezoidation by sets of open trapezoids
2003,
ni podatka o podnaslovu
Triangulacija ravninskih mnogokotnikov
1998,
diplomsko delo visokošolskega študijskega programa
Triangulirajmo mnogokotnik
2000,
ni podatka o podnaslovu
Aplikacija trapezne delitve mnogokotnika
2018,
diplomsko delo
Boolove operacije z enostavnimi ravninskimi mnogokotniki
1999,
diplomska naloga univerzitetnega študijskega programa