<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Fast Point in Polygon Testing Method
Author
Step1:  How to Use
Data preparing
Step2:  The process of building quadtree
Quadtree building process - visualize the building result
Step3:  Visualizing the result of "Point in Polygon" test
Step4:  Test the performance of this quad-tree-structure
Step5:  Validate the correctness of this quad-tree-structure
<ASSISTANT_TASK:>
Python Code:
# Import essential libraries for following calculation
import libpysal as ps
import numpy as np
from libpysal.cg.shapes import Ring, Polygon
from libpysal.cg.segmentLocator import BruteSegmentLocator
from libpysal.cg.polygonQuadTreeStructure import QuadTreeStructureSingleRing
import libpysal.examples as pysal_examples
%matplotlib inline
import matplotlib
import matplotlib.pyplot as plt
import time
# import codecs
# import shapely
# from pysal.cg.shapes import Polygon, Point
# from shapely.geometry import Polygon as spPolygon
# from shapely.geometry import Point as spPoint
# import time
import random
print("import finished!")
Explanation: Fast Point in Polygon Testing Method
Author: Hu Shao &#115;&#104;&#97;&#111;&#104;&#117;&#116;&#105;&#103;&#101;&#114;&#64;&#103;&#109;&#97;&#105;&#108;&#46;&#99;&#111;&#109;
Content
Introduction  
How to Use  
The process of building quadtree  
Visualizing the result of "Point in Polygon" test
Test the performance of this quad-tree-structure
Validate the correctness of this quad-tree-structure
Algorithm of building quadtree cells for study area
Reference
Introduction
Testing whether a point locates inside a polygon is a time consuming work. Especially when the point number is huge and the boundary of study area is complex.
Here we implement a "Fast Point in Polygon Testing Method" to help users determine whether a point is inside a specific polygon rapidly.  
The Quadtree structure is employed to divide a polygon into plenty of lattices. During the dividing, each lattices is marked as in, out or maybe, which means "totally lies inside the polygon", "totally lies out side the polygon" and "intersect with the boundary if the polygon". 
For each point, we firstly allocate it into a lattice. If the lattice is marked as "in" or "out", we will immediately know the result; if the lattice is marked as "maybe", we then need to do some further calculation, which won't be complex.
Once the quadtree structure is constructed, the "point in polygon testing" will be very fast.
This method is suitable for the situations where point numbers are huge, polygon numbers are small and polygon boundary is complex. E.g., simulation in point pattern analysis.
End of explanation
def get_ring_from_file(path):
    vertices = []
    file = open(path, "r")
    for line in file:
        if len(line)<2:
            continue
        coordinates = line.split(",")
        x = (float)(coordinates[0])
        y = (float)(coordinates[1])
        vertices.append((x, y))
    file.close()
    return vertices
# Prepare the polygons for future use.
Texas = Polygon(get_ring_from_file("data/texas_points.txt"))
Pecos = Polygon(get_ring_from_file("data/pecos_points.txt"))
San_Saba = Polygon(get_ring_from_file("data/san_saba_points.txt"))
Texas_with_holes = Polygon(Texas.vertices, 
                           [Pecos.vertices, San_Saba.vertices])
# construct the quadtree structure by explicitly calling the function "build_quad_tree_structure" in polygon
Texas.build_quad_tree_structure()
print "quad tree build finished"
# create some random point and test if these points locate in the polygon
for i in range(0, 10):
    x = random.uniform(Texas.bbox[0], Texas.bbox[2])
    y = random.uniform(Texas.bbox[1], Texas.bbox[3])
    print(x, y, Texas.contains_point([x, y]))
Explanation: How to Use
Data preparing
End of explanation
# The region of Texas, to make the steps more clear, here we only use the main region
texas_main_vertices = Texas.parts[0]
fig, ax = plt.subplots(figsize=(16,11))
qts_singlering = QuadTreeStructureSingleRing(Ring(texas_main_vertices))
patches = []
color_array = []
cells_to_draw = [qts_singlering.root_cell]
while len(cells_to_draw) > 0:
    cell = cells_to_draw.pop()
        
    if cell.children_l_b is None:
        # this is a leaf in the quad tree structure, draw it
        verts = [
            [cell.min_x, cell.min_y],
            [cell.min_x, cell.min_y + cell.length_y],
            [cell.min_x + cell.length_x, cell.min_y + cell.length_y],
            [cell.min_x + cell.length_x, cell.min_y],
            [cell.min_x, cell.min_y]
                ]
        patches.append(verts)
        if cell.status == "in":
            color_array.append("#c8e6c9")  # in color green
        elif cell.status == "out":
            color_array.append("#b0bec5")  # in color grey
        else:  # means "maybe"
            color_array.append("#ffa726")  # in color orange
    else:
        cells_to_draw.append(cell.children_l_b)
        cells_to_draw.append(cell.children_l_t)
        cells_to_draw.append(cell.children_r_b)
        cells_to_draw.append(cell.children_r_t)
coll = matplotlib.collections.PolyCollection(np.array(patches), facecolors=color_array, edgecolors='#eceff1')
ax.add_collection(coll)
point_x_list = []
point_y_list = []
for point in texas_main_vertices:
    point_x_list.append(point[0])
    point_y_list.append(point[1])    
plt.plot(point_x_list, point_y_list)
ax.autoscale_view()
plt.show()
Explanation: The process of building quadtree
Quadtree building process - visualize the building result
End of explanation
plt.figure(figsize=(16,12))
for vertices in Texas_with_holes.parts:
    line_x_list = []
    line_y_list = []
    for point in vertices:
        line_x_list.append(point[0])
        line_y_list.append(point[1])   
    plt.plot(line_x_list, line_y_list, c="#6a1b9a")
for vertices in Texas_with_holes.holes:
    line_x_list = []
    line_y_list = []
    for point in vertices:
        line_x_list.append(point[0])
        line_y_list.append(point[1])   
    plt.plot(line_x_list, line_y_list, c="#1565c0")
    
point_x_list = []
point_y_list = []
point_colors = []
bbox = Texas_with_holes.bbox
for i in range(0, 1000):
    x = random.uniform(bbox[0], bbox[2])  
    y = random.uniform(bbox[1], bbox[3])
    point_x_list.append(x)
    point_y_list.append(y) 
    if Texas_with_holes.contains_point([x, y]):
        point_colors.append("#e57373") # inside, red 
    else:
        point_colors.append("#4db6ac") # outside, green
plt.scatter(point_x_list, point_y_list, c = point_colors, linewidth = 0)
plt.show()
Explanation: Visualizing the result of "Point in Polygon" test
End of explanation
# construct a study area with 3000+ vertices
Huangshan = Polygon(get_ring_from_file("data/study_region_huangshan_point.txt"))
points = []
bbox = Huangshan.bounding_box
for i in range(0, 10000):
    x = random.uniform(bbox[0], bbox[2])  
    y = random.uniform(bbox[1], bbox[3])
    points.append((x, y))    
    
print str(len(points)) + " random points generated"    
print "------------------------------"
print "Begin test without quad-tree-structure"
time_begin = int(round(time.time() * 1000))
for point in points:
    Huangshan.contains_point(point)
time_end = int(round(time.time() * 1000))
print "Test without quad-tree-structure finished, time used = " + str((time_end-time_begin)/1000.0) + "s"
print "------------------------------"
print "Begin test with quad-tree-structure"
time_begin = int(round(time.time() * 1000))
Huangshan.build_quad_tree_structure()
count_error = 0
for point in points:
    Huangshan.contains_point(point)
time_end = int(round(time.time() * 1000))
print "Test with quad-tree-structure finished, time used = " + str((time_end-time_begin)/1000.0) + "s"
Explanation: Test the performance of this quad-tree-structure
End of explanation
# polygons = ps.open("data/Huangshan_region.shp")  # read the research region shape file
# research_region = polygons[0]  # set the first polygon as research polygon
# len(research_region.vertices)
vertices = get_ring_from_file("data/study_region_huangshan_point.txt")
print "Study region read finished, with vertices of " + str(len(vertices))
huangshan = Ring(vertices)
points = []
bbox = huangshan.bounding_box
for i in range(0, 1000):
    x = random.uniform(bbox[0], bbox[2])  
    y = random.uniform(bbox[1], bbox[3])
    points.append([x, y, True])    
print str(len(points)) + " random points generated"    
# First, test if these points are inside of the polygon by using the conventional method, record the result
for point in points:
    is_in = huangshan.contains_point((point[0], point[1]))
    point[2] = is_in
# Then, build the quad-tree and do the test again. Compare the results of two methods.
count_error = 0
huangshan.build_quad_tree_structure()  
for point in points:
    is_in = huangshan.contains_point((point[0], point[1]))
    if point[2] != is_in:
        print "Error found!!!"
        count_error += 1
    
if count_error == 0:
    print "finished ==================== no error found"
else:
    print "finished ==================== ERROR FOUND"
Explanation: Validate the correctness of this quad-tree-structure
End of explanation
<END_TASK>