Week3: 05 Spatial Data Struct1: Spaghetti

Question 1

Spatial data structures requirement

Answer 1

In general, it is important to be able to manipulate efficiently, still maintaining a low spatial complexity
Requirement:
The stored information must allow for an unambiguous representation of the dataset

Question 2

Spatial data structures can be evaluated in terms of…

Answer 2

1) Space complexity: amount of space (memory) needed for storing all information (entities and relations) that is explicitly represented
2) Time complexity: of the algorithms that calculate important info. (e.g. connectivity relations) that is not explicitly stored/represented

Question 3

Topological relations

Answer 3

intersections of different components of entities (interior, boundary, exterior)

Question 4

Two types of vector datasets:

Answer 4

1) Generic sets of entities : any possible top relations

2) Overlayed sets of entities (plane subdivisions): only meet and disjoint

Question 5

A relation is constant if ..

Answer 5

if it involves a constant number of entities

Question 6

A relation is variable if ..

Answer 6

if it involves a variable number of entities

Question 7

Spaghetti data structure properties

Answer 7

1) represents sets of points, lines & polygons
2) can be used for both generic sets of entities and overlayed sets (plane subdivision)
3) the geometry of any spatial entity is described independently of other entities
4) No topology info is recorded
5} For each polygon, we store an (ordered) list of coordinates of points on its boundary (not the same as FV relation)

Question 8

Another data structure

Answer 8

Points and polygons are related: for each polygon, we store ordered list of points (IDs not coordinates) on its boundary: FV relation

Question 9

Spaghetti data structure Pros and cons

Answer 9

Pros:
1) simplicity
2) easy insertions of new entities (all entities are independent)
Cons:
1) inefficient for topological queries
2) redundancies (& consequently, possible inconsistencies)

Note 1: coordinates of points along common boundary are recorded twice
Note 2: No easy way of solving queries e.g. adjacency queries