Point Location Problem
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided design (CAD). In its most general form, the problem is, given a Space partitioning, partition of the space into Disjoint sets, disjoint regions, to determine the region where a query point lies. For example, the problem of determining which window of a graphical user interface contains a given mouse click can be formulated as an instance of point location, with a subdivision formed by the visible parts of each window, although specialized data structures may be more appropriate than general-purpose point location data structures in this application. Another special case is the point in polygon problem, in which one needs to determine whether a point is inside, outside, or on the boundary of a single polygon. In many applications, one needs ...
[...More Info...]       [...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]