Planar Case
In the planar case, we are given a planar subdivision S, formed by multiple polygons called faces, and need to determine which face contains a query point. A brute force search of each face using the point-in-polygon algorithm is possible, but usually not feasible for subdivisions of high complexity. Several different approaches lead to optimal data structures, with O(n) storage space and O(log n) query time, where n is the total number of vertices in S. For simplicity, we assume that the planar subdivision is contained inside a square bounding box.
Read more about this topic: Point Location
Famous quotes containing the word case:
“I am absurdly fearful about this voyage. Various little omens have combined to give me a dark feeling.... Perhaps we shall live to laugh at these. But in case of mishap I should perish with my husband and child, perhaps to be transferred to some happier state.”
—Margaret Fuller (1810–1850)