The search scheme for spatial_hash is as follows. From the list of points provided, a bounding box is computed. The bounding box is then subdivided into mXnXo cells, and the points are placed into the cells that each is inside of. The number of cells (i.e., the number of divisions) is computed by two methods. In the first method, the number of cells is computed by specifying the approximate number of points in each cell. Then the bounding box is regularly subdivided into mXnXo cells, where m=n=o, so that on average the number of points in a cell is <= the number specified.
In the second method, the user can specify the mXnXo divisions manually. This is especially useful to gain resolution in one or more directions in order to take advantage of known structure in the data. For example, if points are known to lie in a plane, then m,n >> o, where o is the direction normal to the plane.
Once the points in the list have been associated in the cells (typically done just once), then it is possible to perform the closest point operation. The closest point is determined by finding the cell that contains the specified position. Then the list of points in the list is searched to find the closest one. If no point is found, then the first level neighboring cells are searched. This process continues until an initial closest point is found.
Once the initial closest point is found, it is possible to compute a distance from the specified position and the point. Then a final search of any unsearched neighbors that are within the distance is made to find the correct closest point. (Note: the initial closest point is often not the correct point because of cell resolution effects.)
Spatial hash is also capable of generating a merge index based on a tolerance. This index is generally used internally by other objects (e.g., clean_filter) to perform geometric merging.
position current position from which to search for closest point.
closest_point index into the points list indicating closest point.
no_points_in_cell the average number of points per cell.
divisions a vector of size 3 that indicates the number of divisions in the x, y, and z directions.
size_by_no_points boolean value indicating whether the number of cells is determined from the total number of points and the number of points in a cell, or by manual specification of the number of divisions in the x, y, z directions.
bounds the bounding box of the points. A six-vector containing the two points (xmin,xmax) of the bounding box.
points the list of points. Based on 1-indexing.
tolerance a distance in global coordinates controlling the point merging process.
points=+ data Set/add points data. The argument data may be either a list of x,y,z triplets, the name of a vector containing x,y,z triplets, or a pointer to array of floats containing x.y,z triplets. If data is a pointer, the number of points in the list must also be supplied.
no_points?, number_points? Return the number of points in the list.
subdivide! Initialize spatial hash table by subdividing bounding box of points into a mXnXo array of cells. Place points into appropriate cell.
position? Return the current search position.
position= (x,y,z) Set the current search position.
closest_point? Determine the closest point (from the list of points) to the position specified. Returns index into point list. A value of 0 indicates that position is outside of bounding box or no points were in list.
bounds= (xmin,ymin,zmin, xmax,ymax,zmax) Set the bounding box of the display data. Normally computed automatically, but may be specified manually.
bounds? Get the bounding box of the display data.
no_points_in_cell? Return the average number of points in each cell after subdivision.
no_points_in_cell= value Set the average number of points in each cell after subdivision. By default, value =40.
divisions? Get the number of divisions to subdivide the bounding box of the points.
divisions= (m,n,o) The number of divisions to subdivide the bounding box of the points in the x, y, and z directions. Used only if size_by_no_points is true.
no_cells? Return the total number of cells.
release! Release all memory used by this object, including the point list. Object is not deleted, however, and may be used again.
size_by_no_points!, size_by_no_points_on! Subdivide based on average number of points per cell.
size_by_divisions!, size_by_no_points_off! Subdivide based on manual specification of divisions in x, y, and z directions.
merge_points! Merge the current point list based on tolerance and generate the merge index.
merge_index= data Set the merge index to either the list of floats given, or to a pointer location (useful for sharing memory).
merge_index? Get the merge index. The index is implicit: the value of location n is new point number.
spatial_hash new: sh no_points_in_cell=1 points=(0,0,0, 1,0,0, 0,2,0, 0,0,3, .75,1.5,2.5, 1,1,1, 0,.75,2, 0,0,2.5, 1,0,2.5, 0,2,2.5, 0,0,2.5, 0,.25,1, 1,2,2, 0,.75,3) subdivide! print:no_cells print:divisions ;
sh position= (0.5, 0.5, 0.5) print:closest_point ;
The second example uses spatial_hash in conjunction with a structured grid to determine closest points.
/* * read in the data */ plot3d_reader new: areader file_prefix="./case1" read! ; /* * Create a spatial has */ spatial_hash new: sh points = ([case1_dataset_grid points?],[case1_dataset_grid number_points?])
subdivide! ; parser interactive!; /* * Find the closest point */ sh position = (10.2, 3, 27) print:closest_point ;