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:
“It is almost everywhere the case that soon after it is begotten the greater part of human wisdom is laid to rest in repositories.”
—G.C. (Georg Christoph)