Jag accepterar att kakor lagras på min dator

Läs mer

Algoritmer för geometriska beräkningar på enkelt slutna polygoner, baserade på konvex uppdelning.

Algoritmer för geometriska beräkningar på enkelt slutna polygoner, baserade på konvex uppdelning. Beställ tryckt exemplar Lägg i kundvagnen
Författare: Fristedt Erland
Ort: Stockholm
Sidor: 45
Utgivningsår: 1993
Publiceringsdatum: 1993-10-04
Rapportnummer: (FOA C 20930-2.7)
Nyckelord konvex dekomposition, geometriska beräkningar, spatiell databas
Sammanfattning För att hantera komplexa geografiska objekt, beskrivna av enkla polygoner med hål, i en databas krävs metoder med bra tidskomplexitet. Metoden som studerats i den här rapporten är att dela upp polygonerna i konvexa delpolygoner.Genom att dela upp objekten till mindre komplexa delar, vilket utförs en gång, minskas tiden för beräkningar och återkomst mot minnet. Förutom dekomponeringsalgoritmen beskrivs algoritmer för beräkning av area, snitt, union och geometrisk skillnad, baserad på konvex uppdelning. Varje objekt i databasen lagra med en minsta omslutande rektangel, dvs objektet approximeras med en rektangle. Rektangeln används för att söka efter ett objekt i databasen. När objektet delas upp till konvexa delpolygoner blir approximationen bättre, ty flera minsta omslutande rektanglar används. Den förbättrade approximationen gör så att objekten överlappar varandra mindre och därmed är databasen mer disjunkt. Uppdelningen medför också att inte hela polygonen behöver läsas upp när en operation ska utföras. Operationen som utförs på konvexa delpolygoner har bra tidskomplexitet, betydligare bättre än om uppdelningen inte används.
Abstract To handle complex geographical objects in a database, described by simple polygons with holes, methods with good time complexity is required. By splitting objects into less complex parts, computation and access to secondary memory can be faster. Methods described in this text are algorithms for decomposition of objects into convex polygons used in computation of geometric difference, intersection, union and area. Algorithms for convex polygons have better time complexity than algorithms for simple polygons with holes. Each object in the databas is stored with a minimal bounding rectangle, i e the single object is approximated with a box. The minimal bounding box is used to select an object in the databas. When the object is decomposed into convex parts the approximation will be better, since more boxes will give less overhead. The improved approximation will give less overlaps among the objects which results in a more disjoint dataspace. When an operation is top be executed, only those parts of the object that is affected have to be read into main memory.

Kundvagn

Inga rapporter i kundvagnen

FOI, Totalförsvarets forskningsinstitut

FOI
Totalförsvarets forskningsinstitut
164 90 Stockholm

Tel: 08-555 030 00
Fax: 08-555 031 00

Orgnr: 202100-5182