Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Bin (computational geometry)
open-in-new
<p>In <a href="/facts/Computational_geometry/eeaotQtl">computational geometry</a>, the bin is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> that allows efficient region queries. Each time a data point falls into a bin, the frequency of that bin is increased by one. </p><p>For example, if there are some <a href="/facts/Cartesian_Coordinate_System/lkTqvMmB">axis</a>-aligned rectangles on a 2D <a href="/facts/Plane_(geometry)/tAUtRFcn">plane</a>, the structure can answer the question, <i>"Given a query rectangle, what are the rectangles intersecting it?"</i> In the example in the top figure, <i>A, B, C, D, E</i> and <i>F</i> are existing rectangles, so the query with the rectangle <i>Q</i> should return <i>C, D, E</i> and <i>F</i>, if we define all rectangles as <a href="/facts/Closed_interval/e9se3vTe">closed intervals</a>. </p><p>The data structure partitions a region of the 2D plane into uniform-sized <i>bins</i>. The <a href="/facts/Bounding_box/oFHL8bxI">bounding box</a> of the bins encloses all <i>candidate</i> rectangles to be queried. All the bins are arranged in a 2D array. All the candidates are represented also as 2D arrays. The size of a candidate's array is the number of bins it intersects. </p><p>For example, in the top figure, candidate <i>B</i> has 6 elements arranged in a 3 row by 2 column array because it intersects 6 bins in such an arrangement. Each bin contains the head of a <a href="/facts/Singly_linked_list/Ik4JTgJW">singly linked list</a>. If a candidate intersects a bin, it is chained to the bin's linked list. Each element in a candidate's array is a link node in the corresponding bin's linked list. </p>