# Interactive Visualization of Geographic Vector Big Data Based on Viewport Generalization Model
## 3 Materials and Methods
### Viewport Pixel Quadtree Index Structure
#### 3.2.2 Construction Method of VPQ  
The core of the VPQ index is to analyze the intersection between geographic vector features and the spatial range corresponding to the VPQ index node, so as to determine the visual mode of the viewport pixels corresponding to the index node. Geographic vector data can be geometrically divided into three types: point, line, and polygon. According to the characteristics of these three features, we design a judgment algorithm to determine the relationship between geographical vector features and index nodes in Algorithm 1. In the algorithm, _p.type_ is the type of the geographic vector feature, _BBox_ is the spatial range represented by a rectangle containing two diagonal points, and _intersect_ and _contain_ are spatial topology judgment operations.  
Figure 2: Structure of viewport pixel quadtree.  
```
input :spatial range rectangle \(BBox\), geographic vector feature \(p\). output :True: intersection; False: non-intersection
1 if\(p.type==point\)then
2 if\(p\) intersect \(BBox\)thenreturn True;
3 else
4 return False
5 elseif\(p.type==line\)then
6 for\(l\in p\)do
7 if\(l\) intersect \(BBox\)thenreturn True;
8 else
9 return False
10 else
11 else
12 else
13 else
14 return False
```  
**Algorithm 1**BBOXIntersectedGeometry: determine the intersection relationship between spatial range and geographic vector features.  
The core idea is that, for point features, the rectangle corresponding to the index node and point is directly used to judge the intersection. For line and polygon data, each simple line segment forming the boundary of line and polygon features is judged. As long as there is a line segment intersecting with the rectangular spatial range of the index node, the vector feature can be considered to have intersected with the index node. For polygon features, there is also a case to deal with; that is, although the polygon boundary does not intersect with the index node, the index node is inside the polygon feature, which is also judged to intersect with the index node. In the above cases, the intersection judgment can be summarized as the intersection of a point and a simple line segment with a rectangular region, which can be quickly judged by geometric computational methods.  
According to the structure design of the VPQ index and the determination algorithm of the intersecting relationship between geographic vector features and index nodes, we designed the construction process of VPQ index as follows:  
1. Create the root node of the VPQ index according to the global spatial range and set the maximum depth of the VPQ index.
2. Perform the necessary coordinate transformation and perform the following Steps 3 to 6 for each feature in the input geographic vector data.
3. Take the VPQ root node as the current index node \(R\).
4. The counter, \(Count\), of the \(R\) increases by 1. If the level, \(level\), does not reach the maximum depth, the spatial range, \(BBox\), of \(R\) is divided into four spatial subranges, \(S_{lu}\) (upper left), \(S_{ru}\) (upper right), \(S_{lb}\) (lower left), and \(S_{rb}\) (lower right), and algorithm 1 is adopted to test the intersection between the current geographic vector feature \(p\) and the four subregions one by one. If it intersects, the pointer will be positioned at the child node. If the child node does not exist, the child node of the corresponding region will be generated.
5. For each newly positioned child node, take it as the new current node \(R\) and skip to Step 4 to continue the execution.
6. Continue until there are no new positioning nodes.  
According to the above process, all regions containing geographic vector data have corresponding nodes in the VPQ index, and the number of geographic vector features is reflected in the Count attribute of the node. Any region without geographic vector data has no corresponding node in the VPQ index.