Method for polygon decomposition
US5771045A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Oct 23, 1995 |
| Grant date | Jun 23, 1998 |
| Priority date | — |
| Expiry date | Oct 23, 2015 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06T17/20
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method for decomposing a polygon into trapezoids and further decomposing the trapezoids. During the decomposition process, the method classifies vertices having a horizontal edge by traversing the active trapezoid list, and using the trapezoids found in the list to aid in classifying the vertex. When a polygon fully contains another polygon, the method slits a diagonal between the outside polygon and the inside polygon to create a single polygon. During the slitting produces, vertices are duplicated and diagonals connecting to the original vertex are left connected to the original vertex or are connected to the duplicated vertex. The method corrects improper ordering of the inside polygon, and the method provides consistency checks during the decomposition process to detect polygons with intersecting edges.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.