Polygon trapezoidation by sets of open trapezoids
Abstract
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.
Keywords
mnogokotniki;deljenje mnogokotnikov;trapezoidacija;računalniška geometrija;
Data
| Language: | English |
|---|---|
| Year of publishing: | 2003 |
| Typology: | 1.01 - Original Scientific Article |
| Organization: | UM FERI - Faculty of Electrical Engineering and Computer Science |
| UDC: | 004.4:514.116 |
| COBISS: |
8326422
|
| ISSN: | 0097-8493 |
| Views: | 1394 |
| Downloads: | 111 |
| Average score: | 0 (0 votes) |
| Metadata: |
|
Other data
| Secondary language: | English |
|---|---|
| Secondary keywords: | polygon;polygon decomposition;trapezoidation;computational geometry; |
| URN: | URN:SI:UM: |
| Pages: | str. 791-800 |
| Volume: | ǂVol. ǂ27 |
| Issue: | ǂiss. ǂ5 |
| Chronology: | 2003 |
| ID: | 8718865 |
Recommended works:
Polygon trapezoidation by sets of open trapezoids
2003,
no subtitle data available
Triangulacija ravninskih mnogokotnikov
1998,
diplomsko delo visokošolskega študijskega programa
Triangulirajmo mnogokotnik
2000,
no subtitle data available
Aplikacija trapezne delitve mnogokotnika
2018,
diplomsko delo
Boolove operacije z enostavnimi ravninskimi mnogokotniki
1999,
diplomska naloga univerzitetnega študijskega programa