Implementation of a trapezoidal map (building and search)
https://github.com/marinimau/GAS-Trapezoidal-maps-final-prject
The organization of the project is as follows:
contains the algorithms for the construction of the trapezoidal map and the dag. The flow of construction is as follows:
- Segment normalization (leftP.x < right.P)
- FollowSegment
- Evaluation of the number of trapezoid interested by the insertion: a. Simple insertion b. Two interested trapezoids insertion c. Many: combine methods of a and b.
- In all three cases the flow of the insertion is: a. Create new trapezoids b. Update internal and external adjacencies c. Update the dag d. Deactivate old trapezoids.
Implements the methods to execute a point query on the dag.
Implements the dag (a pointer to the root, and a list to store the nodes to avoid
dynamic allocation).
data structure used to save the nodes of the dag. It has an attribute “type” to
specify the type of the node (p, q, segment, trapezoid). Each node has an attribute value
that points at the object linked to the node. Node also has pointers to left and right
childs.
Already implemented.
data Structure used to store the single trapezoid using: topSegment,
bottomSegment, leftP and rightP, saves also 4 pointers to manage the adjacency, and a
pointer to the node that saves it in the dag.
data structure used to save all the trapezoids of the trapezoidalMap
(using list). Save also a pointer to the trapezoids resulting from the pointQuery, it is used by the drawable to enhance it.
Already implemented.
used to manage the vertical segment separately in the ui. Vertical
segments are obtained from the list of trapezoids.
drawable for the trapezoids of the trapezoidalMap
drawable for the vertical segments of the trapezoidalMap
Already implemented.
Implements some tests which are executed at each segment insertion. It is evaluated:
- The correctness of followSegment output
- The equality of the sum of the areas of the trapezoids affected by the insertion and those inserted in their place.
- The correctness of adjacencies
These tests heavily affect performance , for this reason they are executed only in debug mode.
Already implemented.
contains a method to calculate the fill color of each trapezoids based on the value of its vertices.
contains methods for calculate intersections, evaluate if 2 points are
degenerate and others.
Tests are performed with the provided dataset and in release mode (except for 10.000). Time expressed in seconds
| test | time (seconds) |
|---|---|
| random10.txt | 4.4e-05 |
| random20.txt | 9.5e-05 |
| random40.txt | 0.000178 |
| random50.txt | 0.000228 |
| random100.txt | 0.000464 |
| random500.txt | 0.001485 |
| random1000.txt | 0.002385 |
| random2000.txt | 0.005249 |
| random5000.txt | 0.014229 |
| random 10000 | 0.034327 |
10 segments:
10 segments (no fill):
query:
5000 segments:
