| | | 1 | | using System; |
| | | 2 | | using System.Collections.Generic; |
| | | 3 | | using System.Linq; |
| | | 4 | | using UnityEngine; |
| | | 5 | | |
| | | 6 | | // K-D tree node. |
| | | 7 | | public class KDNode<T> { |
| | | 8 | | public T Data; |
| | | 9 | | public KDNode<T> Left = null; |
| | | 10 | | public KDNode<T> Right = null; |
| | | 11 | | |
| | | 12 | | public KDNode(T data) { |
| | | 13 | | Data = data; |
| | | 14 | | } |
| | | 15 | | } |
| | | 16 | | |
| | | 17 | | // K-D tree with 2D coordinates. |
| | | 18 | | public class KDTree<T> { |
| | | 19 | | private KDNode<T> _root; |
| | | 20 | | private Func<T, Vector2> _getCoordinates; |
| | | 21 | | |
| | 32 | 22 | | public KDTree(in IReadOnlyList<T> points, Func<T, Vector2> getCoordinates) { |
| | 16 | 23 | | _getCoordinates = getCoordinates; |
| | 16 | 24 | | _root = BuildTree(points, depth: 0); |
| | 16 | 25 | | } |
| | | 26 | | |
| | 982 | 27 | | private KDNode<T> BuildTree(in IReadOnlyList<T> points, int depth) { |
| | 982 | 28 | | if (points.Count == 0) |
| | 499 | 29 | | return null; |
| | | 30 | | |
| | 483 | 31 | | int k = 2; |
| | 483 | 32 | | int axis = depth % k; |
| | | 33 | | |
| | | 34 | | // Sort the points by axis and find the median. |
| | 483 | 35 | | List<T> sortedPoints = |
| | 2799 | 36 | | points.OrderBy(point => (axis == 0 ? _getCoordinates(point).x : _getCoordinates(point).y)) |
| | | 37 | | .ToList(); |
| | 483 | 38 | | int medianIndex = sortedPoints.Count / 2; |
| | 483 | 39 | | T medianPoint = sortedPoints[medianIndex]; |
| | | 40 | | |
| | 483 | 41 | | KDNode<T> node = new KDNode<T>(medianPoint); |
| | 483 | 42 | | List<T> leftPoints = sortedPoints.GetRange(0, medianIndex); |
| | 483 | 43 | | List<T> rightPoints = |
| | | 44 | | sortedPoints.GetRange(medianIndex + 1, sortedPoints.Count - medianIndex - 1); |
| | | 45 | | |
| | 483 | 46 | | node.Left = BuildTree(leftPoints, depth + 1); |
| | 483 | 47 | | node.Right = BuildTree(rightPoints, depth + 1); |
| | 483 | 48 | | return node; |
| | 982 | 49 | | } |
| | | 50 | | |
| | 45 | 51 | | public T NearestNeighbor(Vector2 target) { |
| | 45 | 52 | | KDNode<T> neighbor = NearestNeighbor(_root, target, depth: 0, best: null); |
| | 49 | 53 | | if (neighbor == null) { |
| | 4 | 54 | | return default(T); |
| | | 55 | | } |
| | 41 | 56 | | return neighbor.Data; |
| | 45 | 57 | | } |
| | | 58 | | |
| | 583 | 59 | | private KDNode<T> NearestNeighbor(KDNode<T> node, Vector2 target, int depth, KDNode<T> best) { |
| | 583 | 60 | | if (node == null) |
| | 193 | 61 | | return best; |
| | | 62 | | |
| | 390 | 63 | | float currentDistance = Vector2.Distance(_getCoordinates(node.Data), target); |
| | 390 | 64 | | float bestDistance = |
| | | 65 | | best == null ? float.MaxValue : Vector2.Distance(_getCoordinates(best.Data), target); |
| | 390 | 66 | | if (currentDistance < bestDistance) |
| | 109 | 67 | | best = node; |
| | | 68 | | |
| | 390 | 69 | | int axis = depth % 2; |
| | 390 | 70 | | KDNode<T> nextBranch = (axis == 0 ? target.x < _getCoordinates(node.Data).x |
| | | 71 | | : target.y < _getCoordinates(node.Data).y) |
| | | 72 | | ? node.Left |
| | | 73 | | : node.Right; |
| | 390 | 74 | | KDNode<T> otherBranch = (nextBranch == node.Left) ? node.Right : node.Left; |
| | | 75 | | |
| | | 76 | | // Check the next branch. |
| | 390 | 77 | | best = NearestNeighbor(nextBranch, target, depth + 1, best); |
| | | 78 | | |
| | | 79 | | // Check the other branch. |
| | 390 | 80 | | if ((axis == 0 && Mathf.Abs(target.x - _getCoordinates(node.Data).x) < bestDistance) || |
| | 148 | 81 | | (axis == 1 && Mathf.Abs(target.y - _getCoordinates(node.Data).y) < bestDistance)) { |
| | 148 | 82 | | best = NearestNeighbor(otherBranch, target, depth + 1, best); |
| | 148 | 83 | | } |
| | | 84 | | |
| | 390 | 85 | | return best; |
| | 583 | 86 | | } |
| | | 87 | | } |