Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Point location
open-in-new
<p>The point location class of problems is a fundamental topic of <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>. It finds applications in areas that deal with processing geometrical data: <a href="/facts/Computer_graphics/lapBE8wv">computer graphics</a>, <a href="/facts/Geographic_information_system/PoP1kVoa">geographic information systems</a> (GIS), <a href="/facts/Motion_planning/DoSPv4dB">motion planning</a>, and <a href="/facts/Computer_aided_design/5gSXrmmN">computer aided design</a> (CAD). </p><p>In one of its general forms, the problem is, given a <a href="/facts/Space_partitioning/znppkQCM">partition of the space</a> into <a href="/facts/Disjoint_sets/nLr8XRVd">disjoint</a> regions, to determine the region where a query point lies. For example, the problem of determining which window of a <a href="/facts/Graphical_user_interface/wBlQFWDP">graphical user interface</a> 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. A special case is the <a href="/facts/Point_in_polygon/acr2LQ1n">point in polygon</a> problem, in which one needs to determine whether a point is inside, outside, or on the boundary of a single <a href="/facts/Polygon/xvkmYhvG">polygon</a>. Other special cases exist. </p><p>The problem may be stated for a set of arbitrary regions in space, not necessarily disjoint and not necessarily constituting a partition. </p><p>Further, one may need to determine the location of several points with respect to the same partition of the space. Or, alternatively, partitions may be changing. In the latter case the class of problems overlaps with <a href="/facts/Range_search/Fkls9MD3">range search</a> problems. To solve the problems with varying queries or regions efficiently, it is useful to build a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> that, given a query point, quickly determines which region contains the query point (e.g. the <a href="/facts/Voronoi_diagram/AhQY5LD8">Voronoi diagram</a>). </p>