Package org.tinfour.utils

Class HilbertSort

java.lang.Object

org.tinfour.utils.HilbertSort

public class HilbertSort
extends Object

A utility that sorts points according to the Hilbert space-filling curve and ensures a high-degree of spatial locality in the sequence of points.

During the insertion of points into a TIN, the incremental TIN locates the triangle the contains the insertion point through a "walk" method that traverses the mesh. The walk always on are the triangle that it visited on the previous insertion. Thus, if the insertion vertices are ordered so that subsequent points are close together, the walk is short and the insertion proceeds more efficiently.

The Hilbert sort orders points according to their ranking in a Hilbert space-filling curve. One of the characteristics of Hilbert functions is that each ordered point is always close to its predecessor.

The code for the Hilbert ranking is based on the Lam&Shapiro method as described in "Hackers Delight (2nd ed.)" by H. Warren (2013)

Constructor Summary

Constructors

Constructor	Description
HilbertSort()	Standard constructor

Method Summary

Modifier and Type	Method	Description
boolean	sort(List<Vertex> vertexList)	Sort the vertices in the list by their Hilbert ranking.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

HilbertSort

public HilbertSort()

Standard constructor

Method Detail

sort

public boolean sort(List<Vertex> vertexList)

Sort the vertices in the list by their Hilbert ranking. Because this method temporarily modifies the index element of the input vertices and then restores their values when complete, it is generally unwise to use it on a set of vertices that may be accessed concurrently by more than one thread.

Parameters:

vertexList - the input vertex list.

Returns:

if the list meets the conditions of the sort (has enough points, etc.) and a sort is performed, true; otherwise, false.