Method and apparatus for tiled polygon traversal
US6714196B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Aug 20, 2001 |
| Grant date | Mar 30, 2004 |
| Priority date | — |
| Expiry date | Sep 4, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG09G2360/122
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for visiting all stamps that are relevant to a two-dimensional convex polygonal object. The object is visited with a rectangular stamp, which contains one or more discrete sample points. A relevant location is one for which the object contains at least one of the stamp's sample points when the stamp is placed at that location. Stamp locations are discrete points that are separated vertically by the stamp's height, and horizontally by the stamp's width. The stamp may move to a nearby position, or to a previously saved position, as it traverses the object. The plane in which the object lies is partitioned into rectangular tiles, which are at least as wide and high as the stamp. The invention visits stamp locations in an order that respects tile boundaries—that is, it visits all locations within one tile before visiting any locations within another tile. The invention may also be used with further partitioning of the plane (metatiles), so that it will visit all locations within a metatile before visiting any locations within another metatile, and further visit all locations within a portion of a tile within the current metatile before visiting any location…
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.