Package com.hypixel.hytale.component.spatial

Class KDTree<T>

java.lang.Object

com.hypixel.hytale.component.spatial.KDTree<T>

All Implemented Interfaces:

SpatialStructure<T>

public class KDTree<T>
extends Object
implements SpatialStructure<T>

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
private static class	KDTree.ClosestState<T>
private static class	KDTree.Node<T>
private static class	KDTree.OrderedEntry<T>

Field Summary

Fields

Modifier and Type	Field	Description
private final Predicate<T>	collectionFilter
private final List<List<T>>	dataListPool
private int	dataListPoolIndex
private final List<KDTree.Node<T>>	nodePool
private int	nodePoolIndex
private KDTree.Node<T>	root
private int	size

Constructor Summary

Constructors

Constructor	Description
KDTree(Predicate<T> collectionFilter)

Method Summary

Modifier and Type	Method	Description
private void	_internal_ordered3DAxis(List<KDTree.OrderedEntry<T>> results, KDTree.Node<T> node, Vector3d center, double xSearchRadius, double ySearchRadius, double zSearchRadius, int depth)
private void	build0(SpatialData<T> spatialData, int start, int end)
T	closest(Vector3d point)
private void	closest0(KDTree.ClosestState<T> closestState, KDTree.Node<T> node, Vector3d vector, int depth)
void	collect(Vector3d center, double radius, List<T> results)
private void	collect0(List<T> results, KDTree.Node<T> node, Vector3d vector, double distanceSq, int depth)
void	collectBox(Vector3d min, Vector3d max, List<T> results)
private void	collectBox0(List<T> results, KDTree.Node<T> node, Vector3d min, Vector3d max, int depth)
void	collectCylinder(Vector3d center, double radius, double height, List<T> results)
private void	collectCylinder0(List<T> results, KDTree.Node<T> node, Vector3d center, double radiusSq, double halfHeight, double radius, int depth)
private static int	compare(Vector3d v1, Vector3d v2, int axis)
String	dump()
private static double	get(Vector3d v, int axis)
private List<T>	getPooledDataList()
private KDTree.Node<T>	getPooledNode(Vector3d vector, List<T> data)
void	ordered(Vector3d center, double radius, List<T> results)
private void	ordered0(List<KDTree.OrderedEntry<T>> results, KDTree.Node<T> node, Vector3d vector, double distanceSq, int depth)
void	ordered3DAxis(Vector3d center, double xSearchRadius, double YSearchRadius, double zSearchRadius, List<T> results)
private void	put0(KDTree.Node<T> node, Vector3d vector, List<T> list, int axis)
void	rebuild(SpatialData<T> spatialData)
int	size()

Methods inherited from class java.lang.Object

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

Field Details

nodePool

@Nonnull
private final List<KDTree.Node<T>> nodePool

nodePoolIndex

private int nodePoolIndex

dataListPool

@Nonnull
private final List<List<T>> dataListPool

dataListPoolIndex

private int dataListPoolIndex

size

private int size

collectionFilter

@Nonnull
private final Predicate<T> collectionFilter

root

@Nullable
private KDTree.Node<T> root

Constructor Details

KDTree

public KDTree(@Nonnull
 Predicate<T> collectionFilter)

Method Details

size

public int size()

Specified by:

size in interface SpatialStructure<T>

rebuild

public void rebuild(@Nonnull
 SpatialData<T> spatialData)

Specified by:

rebuild in interface SpatialStructure<T>

closest

@Nullable
public T closest(@Nonnull
 Vector3d point)

Specified by:

closest in interface SpatialStructure<T>

collect

public void collect(@Nonnull
 Vector3d center,
 double radius,
 @Nonnull
 List<T> results)

Specified by:

collect in interface SpatialStructure<T>

collectCylinder

public void collectCylinder(@Nonnull
 Vector3d center,
 double radius,
 double height,
 @Nonnull
 List<T> results)

Specified by:

collectCylinder in interface SpatialStructure<T>

collectBox

public void collectBox(@Nonnull
 Vector3d min,
 @Nonnull
 Vector3d max,
 @Nonnull
 List<T> results)

Specified by:

collectBox in interface SpatialStructure<T>

ordered

public void ordered(@Nonnull
 Vector3d center,
 double radius,
 @Nonnull
 List<T> results)

Specified by:

ordered in interface SpatialStructure<T>

ordered3DAxis

public void ordered3DAxis(@Nonnull
 Vector3d center,
 double xSearchRadius,
 double YSearchRadius,
 double zSearchRadius,
 @Nonnull
 List<T> results)

Specified by:

ordered3DAxis in interface SpatialStructure<T>

dump

@Nonnull
public String dump()

Specified by:

dump in interface SpatialStructure<T>

getPooledNode

@Nonnull
private KDTree.Node<T> getPooledNode(Vector3d vector,
 List<T> data)

getPooledDataList

private List<T> getPooledDataList()

build0

private void build0(@Nonnull
 SpatialData<T> spatialData,
 int start,
 int end)

put0

private void put0(@Nonnull
 KDTree.Node<T> node,
 @Nonnull
 Vector3d vector,
 @Nonnull
 List<T> list,
 int axis)

closest0

private void closest0(@Nonnull
 KDTree.ClosestState<T> closestState,
 @Nullable
 KDTree.Node<T> node,
 @Nonnull
 Vector3d vector,
 int depth)

collect0

private void collect0(@Nonnull
 List<T> results,
 @Nullable
 KDTree.Node<T> node,
 @Nonnull
 Vector3d vector,
 double distanceSq,
 int depth)

collectCylinder0

private void collectCylinder0(@Nonnull
 List<T> results,
 @Nullable
 KDTree.Node<T> node,
 @Nonnull
 Vector3d center,
 double radiusSq,
 double halfHeight,
 double radius,
 int depth)

collectBox0

private void collectBox0(@Nonnull
 List<T> results,
 @Nullable
 KDTree.Node<T> node,
 @Nonnull
 Vector3d min,
 @Nonnull
 Vector3d max,
 int depth)

ordered0

private void ordered0(@Nonnull
 List<KDTree.OrderedEntry<T>> results,
 @Nullable
 KDTree.Node<T> node,
 @Nonnull
 Vector3d vector,
 double distanceSq,
 int depth)

_internal_ordered3DAxis

private void _internal_ordered3DAxis(@Nonnull
 List<KDTree.OrderedEntry<T>> results,
 @Nullable
 KDTree.Node<T> node,
 @Nonnull
 Vector3d center,
 double xSearchRadius,
 double ySearchRadius,
 double zSearchRadius,
 int depth)

compare

private static int compare(@Nonnull
 Vector3d v1,
 @Nonnull
 Vector3d v2,
 int axis)

get

private static double get(@Nonnull
 Vector3d v,
 int axis)