KDTree as a NET application.

2026-09-01T21:59:52Z

Been playing quite a bit with Gilles Chanteau's kdtree lisp app published at theSwamp kd-tree (AutoLISP).

So decided to turn it into a dll to use from autolisp. I am attaching the C# code below and a bat file to compile

it for Autocad 2017.

The dll will create the following function for autolisp:

KDtreeLisp.dll Reference & Command

SyntaxIn AutoLISP documentation standards, optional parameters are enclosed in square brackets [optional].

(KD-BUILD pointList [dimensions] [customHandle])
Builds a KD-Tree spatial index from a list of points.
Arguments:
pointList: LIST — List of 2D or 3D point lists ((x y z) ...).
dimensions (optional): INT — 2 for 2D $(X,Y)$ or 3 for 3D $(X,Y,Z)$. Default is 2.
customHandle (optional): STR — Custom string handle identifier.
Returns: STR handle (e.g., "<KD-TREE-1>" or "<KD-TREE-SURVEY>"), or nil on failure.

(KD-NEAREST handle targetPoint [count] [maxRadius])
Finds the nearest n points to a target point.
Arguments:
handle: STR — KD-Tree handle string.
targetPoint: LIST — Target point (x y z).
count (optional): INT — Number of nearest points to retrieve. Default is 1.
maxRadius (optional): REAL or INT — Maximum search radius limit. Points farther
than this distance are ignored.
Returns:If count = 1 (or omitted): A single point (x y z).
If count > 1: A list of points ((x1 y1 z1) (x2 y2 z2) ...).

(KD-NEAREST-INFO handle targetPoint [count] [maxRadius])
Finds nearest points with detailed metadata.
Arguments:
handle: STR — KD-Tree handle string.
targetPoint: LIST — Target point (x y z).
count (optional): INT — Number of points to retrieve. Default is 1.
maxRadius (optional): REAL or INT — Maximum search radius limit.
Returns:
A list of detailed entries (((x y z) index distance) ...).

(KD-RANGE handle centerPoint radius)
Finds all points inside a fixed search radius without a count limit.
Arguments:
handle: STR — KD-Tree handle string.
centerPoint: LIST — Center search coordinate (x y z).
radius: REAL or INT — Search radius.
Returns:
A list of all enclosed points ((x1 y1 z1) (x2 y2 z2) ...) sorted by distance,
or nil if none are found.

(KD-FREE [handle])
Frees tree memory.
Arguments:
handle (optional): STR — Tree handle to free. If omitted, clears all active trees.
Returns: INT — Number of trees removed.

Once you've compiled the C#, kdtreelisp.dll will be created and ready to use in Autocad.

using System;
using System.Collections.Generic;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Geometry;
using Autodesk.AutoCAD.Runtime;

namespace KdTreeLisp
{
    // ==========================================
    // 1. DATA STRUCTURES & TREE ENGINE
    // ==========================================

    public class KdItem
    {
        public Point3d Point { get; set; }
        public int Id { get; set; }

        public KdItem(Point3d pt, int id)
        {
            Point = pt;
            Id = id;
        }
    }

    public class KdNode
    {
        public Point3d Point { get; set; }
        public int Id { get; set; }
        public KdNode Left { get; set; }
        public KdNode Right { get; set; }

        public KdNode(Point3d point, int id)
        {
            Point = point;
            Id = id;
        }
    }

    public class NeighborResult : IComparable<NeighborResult>
    {
        public KdNode Node { get; set; }
        public double DistanceSq { get; set; }

        public NeighborResult(KdNode node, double distSq)
        {
            Node = node;
            DistanceSq = distSq;
        }

        public int CompareTo(NeighborResult other)
        {
            return other.DistanceSq.CompareTo(this.DistanceSq);
        }
    }

    public class KdTree
    {
        public KdNode Root { get; private set; }
        public int ActiveDimensions { get; private set; }

        public void Build(List<KdItem> items, int activeDimensions)
        {
            ActiveDimensions = Math.Max(1, Math.Min(3, activeDimensions));
            Root = BuildRecursive(items, 0);
        }

        private KdNode BuildRecursive(List<KdItem> items, int depth)
        {
            if (items == null || items.Count == 0) return null;

            int axis = depth % ActiveDimensions;
            items.Sort(delegate(KdItem a, KdItem b)
            {
                return GetAxisValue(a.Point, axis).CompareTo(GetAxisValue(b.Point, axis));
            });

            int medianIndex = items.Count / 2;

            KdNode node = new KdNode(items[medianIndex].Point, items[medianIndex].Id);
            node.Left = BuildRecursive(items.GetRange(0, medianIndex), depth + 1);
            node.Right = BuildRecursive(items.GetRange(medianIndex + 1, items.Count - (medianIndex + 1)), depth + 1);

            return node;
        }

        public double CalculateDistanceSq(Point3d p1, Point3d p2)
        {
            double dx = p1.X - p2.X;
            double dy = p1.Y - p2.Y;

            if (ActiveDimensions == 2)
            {
                return dx * dx + dy * dy;
            }

            double dz = p1.Z - p2.Z;
            return dx * dx + dy * dy + dz * dz;
        }

        // K-Nearest Neighbor Search with Optional Maximum Radius Limit
        public List<NeighborResult> FindNearest(Point3d target, int count, double maxRadius = double.MaxValue)
        {
            List<NeighborResult> heap = new List<NeighborResult>();
            if (Root == null || count <= 0) return heap;

            double maxDistSq = (maxRadius == double.MaxValue) ? double.MaxValue : maxRadius * maxRadius;

            SearchNearest(Root, target, count, maxDistSq, heap, 0);

            // Sort ascending by distance before returning
            heap.Sort(delegate(NeighborResult a, NeighborResult b)
            {
                return a.DistanceSq.CompareTo(b.DistanceSq);
            });

            return heap;
        }

        private void SearchNearest(KdNode current, Point3d target, int count, double maxDistSq, List<NeighborResult> heap, int depth)
        {
            if (current == null) return;

            double distSq = CalculateDistanceSq(current.Point, target);

            // Accept point only if inside maximum distance threshold
            if (distSq <= maxDistSq)
            {
                if (heap.Count < count)
                {
                    heap.Add(new NeighborResult(current, distSq));
                    heap.Sort();
                }
                else if (distSq < heap[0].DistanceSq)
                {
                    heap[0] = new NeighborResult(current, distSq);
                    heap.Sort();
                }
            }

            int axis = depth % ActiveDimensions;
            double diff = GetAxisValue(target, axis) - GetAxisValue(current.Point, axis);

            KdNode primary = diff < 0 ? current.Left : current.Right;
            KdNode secondary = diff < 0 ? current.Right : current.Left;

            SearchNearest(primary, target, count, maxDistSq, heap, depth + 1);

            // Pruning condition: check if secondary subtree could contain points closer than current worst candidate
            double currentSearchRadiusSq = (heap.Count < count) ? maxDistSq : Math.Min(heap[0].DistanceSq, maxDistSq);

            if (diff * diff < currentSearchRadiusSq)
            {
                SearchNearest(secondary, target, count, maxDistSq, heap, depth + 1);
            }
        }

        // Range Search: Retrieves ALL points within radius
        public List<NeighborResult> RangeSearch(Point3d center, double radius)
        {
            List<NeighborResult> results = new List<NeighborResult>();
            if (Root == null || radius < 0) return results;

            double radiusSq = radius * radius;
            SearchRangeRecursive(Root, center, radiusSq, results, 0);

            results.Sort(delegate(NeighborResult a, NeighborResult b)
            {
                return a.DistanceSq.CompareTo(b.DistanceSq);
            });

            return results;
        }

        private void SearchRangeRecursive(KdNode current, Point3d center, double radiusSq, List<NeighborResult> results, int depth)
        {
            if (current == null) return;

            double distSq = CalculateDistanceSq(current.Point, center);
            if (distSq <= radiusSq)
            {
                results.Add(new NeighborResult(current, distSq));
            }

            int axis = depth % ActiveDimensions;
            double diff = GetAxisValue(center, axis) - GetAxisValue(current.Point, axis);

            if (diff < 0)
            {
                SearchRangeRecursive(current.Left, center, radiusSq, results, depth + 1);
                if (diff * diff <= radiusSq)
                {
                    SearchRangeRecursive(current.Right, center, radiusSq, results, depth + 1);
                }
            }
            else
            {
                SearchRangeRecursive(current.Right, center, radiusSq, results, depth + 1);
                if (diff * diff <= radiusSq)
                {
                    SearchRangeRecursive(current.Left, center, radiusSq, results, depth + 1);
                }
            }
        }

        private double GetAxisValue(Point3d pt, int axis)
        {
            switch (axis)
            {
                case 0: return pt.X;
                case 1: return pt.Y;
                default: return pt.Z;
            }
        }
    }

    // ==========================================
    // 2. AUTOLISP INTERFACE BRIDGE
    // ==========================================

    public class LispBridge
    {
        private static readonly Dictionary<string, KdTree> _trees = new Dictionary<string, KdTree>();
        private static int _treeCounter = 1;

        // Signature: (KD-BUILD pointList [dimensions] [customHandle])
        [LispFunction("KD-BUILD")]
        public static TypedValue BuildTree(ResultBuffer args)
        {
            if (args == null) return new TypedValue((int)LispDataType.Nil);

            TypedValue[] arr = args.AsArray();
            List<KdItem> items = new List<KdItem>();
            int idCounter = 0;
            int requestedDimensions = 2;
            string customHandle = null;

            foreach (TypedValue tv in arr)
            {
                if (tv.TypeCode == (int)LispDataType.Point3d)
                {
                    items.Add(new KdItem((Point3d)tv.Value, idCounter++));
                }
                else if (tv.TypeCode == (int)LispDataType.Point2d)
                {
                    Point2d pt2 = (Point2d)tv.Value;
                    items.Add(new KdItem(new Point3d(pt2.X, pt2.Y, 0.0), idCounter++));
                }
                else if (tv.TypeCode == (int)LispDataType.Int16 || tv.TypeCode == (int)LispDataType.Int32)
                {
                    requestedDimensions = Convert.ToInt32(tv.Value);
                }
                else if (tv.TypeCode == (int)LispDataType.Text)
                {
                    customHandle = Convert.ToString(tv.Value);
                }
            }

            if (items.Count == 0) return new TypedValue((int)LispDataType.Nil);

            KdTree tree = new KdTree();
            tree.Build(items, requestedDimensions);

            string handle = string.IsNullOrEmpty(customHandle)
                ? string.Format("<KD-TREE-{0}>", _treeCounter++)
                : string.Format("<KD-TREE-{0}>", customHandle.ToUpper());

            _trees[handle] = tree;

            return new TypedValue((int)LispDataType.Text, handle);
        }

        // Signature: (KD-NEAREST handle targetPoint [count] [maxRadius])
        [LispFunction("KD-NEAREST")]
        public static ResultBuffer FindNearest(ResultBuffer args)
        {
            if (args == null) return null;

            List<TypedValue> values = ExtractValues(args);
            if (values.Count < 2) return null;

            if (values[0].TypeCode != (int)LispDataType.Text) return null;
            string handle = Convert.ToString(values[0].Value);

            if (!_trees.ContainsKey(handle)) return null;
            KdTree tree = _trees[handle];
            if (tree.Root == null) return null;

            Point3d target;
            if (values[1].TypeCode == (int)LispDataType.Point3d)
            {
                target = (Point3d)values[1].Value;
            }
            else if (values[1].TypeCode == (int)LispDataType.Point2d)
            {
                Point2d p2 = (Point2d)values[1].Value;
                target = new Point3d(p2.X, p2.Y, 0.0);
            }
            else
            {
                return null;
            }

            int count = 1;
            if (values.Count > 2 && (values[2].TypeCode == (int)LispDataType.Int16 || values[2].TypeCode == (int)LispDataType.Int32))
            {
                count = Convert.ToInt32(values[2].Value);
            }

            double maxRadius = double.MaxValue;
            if (values.Count > 3)
            {
                TypedValue v = values[3];
                if (v.TypeCode == (int)LispDataType.Double || v.TypeCode == (int)LispDataType.Int16 || v.TypeCode == (int)LispDataType.Int32)
                {
                    maxRadius = Convert.ToDouble(v.Value);
                }
            }

            List<NeighborResult> results = tree.FindNearest(target, count, maxRadius);
            if (results.Count == 0) return null;

            ResultBuffer res = new ResultBuffer();

            if (count == 1)
            {
                res.Add(new TypedValue((int)LispDataType.Point3d, results[0].Node.Point));
            }
            else
            {
                res.Add(new TypedValue((int)LispDataType.ListBegin));
                foreach (NeighborResult item in results)
                {
                    res.Add(new TypedValue((int)LispDataType.Point3d, item.Node.Point));
                }
                res.Add(new TypedValue((int)LispDataType.ListEnd));
            }

            return res;
        }

        // Signature: (KD-NEAREST-INFO handle targetPoint [count] [maxRadius])
        [LispFunction("KD-NEAREST-INFO")]
        public static ResultBuffer FindNearestInfo(ResultBuffer args)
        {
            if (args == null) return null;

            List<TypedValue> values = ExtractValues(args);
            if (values.Count < 2) return null;

            if (values[0].TypeCode != (int)LispDataType.Text) return null;
            string handle = Convert.ToString(values[0].Value);

            if (!_trees.ContainsKey(handle)) return null;
            KdTree tree = _trees[handle];

            Point3d target;
            if (values[1].TypeCode == (int)LispDataType.Point3d)
                target = (Point3d)values[1].Value;
            else if (values[1].TypeCode == (int)LispDataType.Point2d)
                target = new Point3d(((Point2d)values[1].Value).X, ((Point2d)values[1].Value).Y, 0.0);
            else
                return null;

            int count = 1;
            if (values.Count > 2 && (values[2].TypeCode == (int)LispDataType.Int16 || values[2].TypeCode == (int)LispDataType.Int32))
                count = Convert.ToInt32(values[2].Value);

            double maxRadius = double.MaxValue;
            if (values.Count > 3)
            {
                TypedValue v = values[3];
                if (v.TypeCode == (int)LispDataType.Double || v.TypeCode == (int)LispDataType.Int16 || v.TypeCode == (int)LispDataType.Int32)
                    maxRadius = Convert.ToDouble(v.Value);
            }

            List<NeighborResult> results = tree.FindNearest(target, count, maxRadius);
            if (results.Count == 0) return null;

            ResultBuffer res = new ResultBuffer();
            res.Add(new TypedValue((int)LispDataType.ListBegin));
            foreach (NeighborResult item in results)
            {
                res.Add(new TypedValue((int)LispDataType.ListBegin));
                res.Add(new TypedValue((int)LispDataType.Point3d, item.Node.Point));
                res.Add(new TypedValue((int)LispDataType.Int32, item.Node.Id));
                res.Add(new TypedValue((int)LispDataType.Double, Math.Sqrt(item.DistanceSq)));
                res.Add(new TypedValue((int)LispDataType.ListEnd));
            }
            res.Add(new TypedValue((int)LispDataType.ListEnd));

            return res;
        }

        // Signature: (KD-RANGE handle centerPoint radius)
        [LispFunction("KD-RANGE")]
        public static ResultBuffer RangeSearch(ResultBuffer args)
        {
            if (args == null) return null;

            List<TypedValue> values = ExtractValues(args);
            if (values.Count < 3) return null;

            if (values[0].TypeCode != (int)LispDataType.Text) return null;
            string handle = Convert.ToString(values[0].Value);

            if (!_trees.ContainsKey(handle)) return null;
            KdTree tree = _trees[handle];

            Point3d center;
            if (values[1].TypeCode == (int)LispDataType.Point3d)
                center = (Point3d)values[1].Value;
            else if (values[1].TypeCode == (int)LispDataType.Point2d)
                center = new Point3d(((Point2d)values[1].Value).X, ((Point2d)values[1].Value).Y, 0.0);
            else
                return null;

            double radius = 0.0;
            TypedValue rVal = values[2];
            if (rVal.TypeCode == (int)LispDataType.Double || rVal.TypeCode == (int)LispDataType.Int16 || rVal.TypeCode == (int)LispDataType.Int32)
            {
                radius = Convert.ToDouble(rVal.Value);
            }
            else
            {
                return null;
            }

            List<NeighborResult> results = tree.RangeSearch(center, radius);
            if (results.Count == 0) return null;

            ResultBuffer res = new ResultBuffer();
            res.Add(new TypedValue((int)LispDataType.ListBegin));
            foreach (NeighborResult item in results)
            {
                res.Add(new TypedValue((int)LispDataType.Point3d, item.Node.Point));
            }
            res.Add(new TypedValue((int)LispDataType.ListEnd));

            return res;
        }

        // Signature: (KD-FREE [handle])
        [LispFunction("KD-FREE")]
        public static TypedValue FreeTree(ResultBuffer args)
        {
            if (args == null)
            {
                int count = _trees.Count;
                _trees.Clear();
                return new TypedValue((int)LispDataType.Int32, count);
            }

            List<TypedValue> values = ExtractValues(args);
            if (values.Count == 0 || values[0].TypeCode != (int)LispDataType.Text)
            {
                int count = _trees.Count;
                _trees.Clear();
                return new TypedValue((int)LispDataType.Int32, count);
            }

            string handle = Convert.ToString(values[0].Value);
            bool removed = _trees.Remove(handle);
            return new TypedValue((int)LispDataType.Int32, removed ? 1 : 0);
        }

        private static List<TypedValue> ExtractValues(ResultBuffer resbuf)
        {
            List<TypedValue> list = new List<TypedValue>();
            foreach (TypedValue tv in resbuf.AsArray())
            {
                if (tv.TypeCode != (int)LispDataType.ListBegin &&
                    tv.TypeCode != (int)LispDataType.ListEnd)
                {
                    list.Add(tv);
                }
            }
            return list;
        }
    }
}

ymg

KDtreeLisp.cs Build.bat

Sign In

KDTree as a NET application.

Recommended Posts

ymg3

Join the conversation

Tutorials

Forums

Activity