KDTree as a NET application.

[ymg3]

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

[BIGAL]

Whilst I probably won't use it, have you looked at compiling for Non Acad, say Bricscad a lot of users here.

[ymg3]

I am kind of a Green Horn when it comes to compiling.  I don't even have vstudio.  So I still use the legacy csc compiler.  On top of that i only have access to acad 2017, so I am not aware of what would be needed to compile it for more recent version of Autocad.

 

[Danielm103]

Nice! I used Nanoflann for the python wrappers, Ge.Point2dTree, Ge.Point3dTree https://github.com/jlblancoc/nanoflann

it builds the tree multi-threaded. Nanoflann can be made dynamic in that it can add or remove points, though I didn’t add that in to the python wrappers.

 

I also created a wrapper for AutoLISP here https://github.com/CEXT-Dan/ads_geo

 

Wrappers are limited though, in C++ you can create a payload I.e.

{

                Point

                Data

}

 

Otherwise, you have to create a hashmap to link the point with the payload.

 

A professional C# version might use an interface for X,Y,Z, so you can expand the tree to allow any class or structure that has the proper interface  

Edited September 2 by Danielm103

[Danielm103]

1 hour ago, BIGAL said:

Whilst I probably won't use it, have you looked at compiling for Non Acad, say Bricscad a lot of users here.

all you would need to do is edit the bat file to point at the target platform.

 

AI says you can jut create a project file next to the .cs, then use “dotnet build -c Release”

 

<Project Sdk="Microsoft.NET.Sdk">
  <PropertyGroup>
    <!-- Use net48 for AutoCAD 2021-2024, or net8.0-windows for AutoCAD 2025+ -->
    <TargetFramework>net8.0-windows</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
    <Platforms>x64</Platforms>
  </PropertyGroup>

  <!-- Reference your AutoCAD libraries -->
  <ItemGroup>
    <Reference Include="AcCoreMgd">
      <HintPath>C:\Program Files\Autodesk\AutoCAD 2017\AcCoreMgd.dll</HintPath>
      <Private>False</Private> <!-- Prevents copying AutoCAD DLLs to your output folder -->
    </Reference>
    <Reference Include="AcDbMgd">
      <HintPath>C:\Program Files\Autodesk\AutoCAD 2017\AcDbMgd.dll</HintPath>
      <Private>False</Private>
    </Reference>
    <Reference Include="AcMgd">
      <HintPath>C:\Program Files\Autodesk\AutoCAD 2017\AcMgd.dll</HintPath>
      <Private>False</Private>
    </Reference>
  </ItemGroup>
</Project>

 

[ymg3]

@Danielm103

 

Interesting,  so many ways to skin a cat.

[gile]

Hi,

The GeometryExtensions.NET library provides a generic KdTree<T> class which uses parallel computation for building the tree.

It also provides an example of Point3dTree class but can used with any type of object providing a 'getPosition' function.

// public KdTree(IEnumerable<T> source, Func<T, Point3d>?getPosition, int dimension)
var tree = new KdTree<BlockReference>(blockList, br => br.Position, 2);

 

Edited Monday at 02:16 PM by gile

[ymg3]

@gile,

 

Quote

The GeometryExtensions.NET library provides a generic KdTree<T> class which uses parallel computation for building the tree.

It also provides an example of Point3dTree class but can used with any type of object providing a 'getPosition' function.

 

Did not know that.  At least I learned something while doing mine.

 

I've look at the extension and there are many interesting things in there.

Edited Monday at 08:54 PM by ymg3

[ymg3]

@gile,

 

Here I build a bridge to your GeometryExtensions.NET library, exposing essentially the same command that I had in mine .

The only addition being GC:KD-MINNODE.

 

I have also built a concavehull in C# using your kd-tree if anybody is interested.

 

ymg

 

using System;
using System.IO;
using System.Linq;
using System.Globalization;
using System.Collections.Generic;
using Autodesk.AutoCAD.Runtime;
using Autodesk.AutoCAD.ApplicationServices;
using Autodesk.AutoCAD.DatabaseServices;
using Autodesk.AutoCAD.Geometry;
using Gile.AutoCAD.R20.Geometry; 

namespace LispGileBridge
{
   public class ExtensionLoader : IExtensionApplication
   {
      public void Initialize()
      {
         try
         {
            var ed = Autodesk.AutoCAD.ApplicationServices.Application.DocumentManager.MdiActiveDocument.Editor;
            
            // Extracts the absolute running file path dynamically via Reflection
            string assemblyPath = System.Reflection.Assembly.GetExecutingAssembly().Location;
            string assemblyName = System.IO.Path.GetFileName(assemblyPath);

            ed.WriteMessage($"\n--> Assembly File Loaded: \"{assemblyName}\"");
            ed.WriteMessage($"\n--> Full Path: {assemblyPath}");
            ed.WriteMessage("\n--> Available commands:");
            ed.WriteMessage("\n       (GC:KD-BUILD pointList [dimensions] [customHandle])");
            ed.WriteMessage("\n       (GC:KD-NEAREST handle Point [count] [maxRadius] [sortFlag])");
            ed.WriteMessage("\n       (GC:KD-NEAREST-INFO handle Point [count] [maxRadius])");
            ed.WriteMessage("\n       (GC:KD-RANGE handle Point radius)");
            ed.WriteMessage("\n       (GC:KD-MINNODE handle dimension)");
            ed.WriteMessage("\n       (GC:KD-FREE [handle])");
         }
         catch 
         {
            // Fallback safety silent escape check
         }
      }

      public void Terminate()
      {
      }
   }
   public class KdTreeBridge
   {
      // Thread-safe dictionary tracking string handles to their specific tree instances and properties
      private static readonly Dictionary<string, (Point3dTree Tree, bool Is2D)> _registry = 
      new Dictionary<string, (Point3dTree, bool)>(StringComparer.OrdinalIgnoreCase);
      private static int _autoId = 1;

      // --------------------------------------------------------------------------------
      // 1. (gc:kd-build pointList [dimensions] [customHandle])
      // --------------------------------------------------------------------------------
      [LispFunction("GC:KD-BUILD")]
      public static object GileKdBuild(ResultBuffer args)
      {
         if (args == null) return null;
         TypedValue[] arr = args.AsArray();
         if (arr.Length == 0) return null;

         try
         {
            List<Point3d> pts = ParseLispPoints(arr, 0, out int pointsReadCount);
            if (pts.Count == 0) return null;

            // Default dimension to 2D unless explicitly specified as 3
            int dimensions = 2;
            string customHandle = null;

            if (arr.Length > pointsReadCount)
            {
               int nextIdx = pointsReadCount;
               if (arr[nextIdx].TypeCode == (int)LispDataType.Int32 || arr[nextIdx].TypeCode == (int)LispDataType.Int16)
               {
                  dimensions = Convert.ToInt32(arr[nextIdx].Value);
                  nextIdx++;
               }
               if (arr.Length > nextIdx && arr[nextIdx].TypeCode == (int)LispDataType.Text)
               {
                  customHandle = Convert.ToString(arr[nextIdx].Value);
               }
            }

            bool is2D = (dimensions == 2);
            // Gilles' constructor: ignoreZ parameter directly matches our is2D rule
            Point3dTree tree = new Point3dTree(pts, is2D);

            string handle = string.IsNullOrEmpty(customHandle) ? $"<KD-TREE-{_autoId++}>" : customHandle;
            _registry[handle] = (tree, is2D);

            return handle;
         }
         catch (System.Exception ex)
         {
            Application.DocumentManager.MdiActiveDocument.Editor.WriteMessage($"\nError in KD-BUILD: {ex.Message}\n");
            return null;
         }
      }

      // --------------------------------------------------------------------------------
      // 2. (gc:kd-nearest handle targetPoint [count] [maxRadius] [sortFlag])
      // --------------------------------------------------------------------------------
      [LispFunction("GC:KD-NEAREST")]
      public static object GileKdNearest(ResultBuffer args)
      {
         if (args == null) return null;
         TypedValue[] arr = args.AsArray();
         if (arr.Length < 2) return null;

         try
         {
            string handle = Convert.ToString(arr[0].Value);
            if (!_registry.TryGetValue(handle, out var entry)) return null;

            if (arr[1].TypeCode != (int)LispDataType.Point3d) return null;
            Point3d targetPt = (Point3d)arr[1].Value;

            int count = 1;
            double maxRadius = double.MaxValue;
            int sortFlag = 1; // Default: Sort by Angle

            if (arr.Length >= 3) count = Convert.ToInt32(arr[2].Value);
            if (arr.Length >= 4) maxRadius = Convert.ToDouble(arr[3].Value);
            if (arr.Length >= 5) sortFlag = Convert.ToInt32(arr[4].Value);

            var searchCollection = entry.Tree.GetNearestNeighbours(targetPt, count);
            if (searchCollection == null) return null;

            // Filter by radius limit and compile working list
            List<Point3d> filtered = new List<Point3d>();
            foreach (Point3d pt in searchCollection)
            {
               double dist = entry.Is2D ? targetPt.DistanceTo(new Point3d(pt.X, pt.Y, targetPt.Z)) : targetPt.DistanceTo(pt);
               if (dist <= maxRadius) filtered.Add(pt);
            }

            if (filtered.Count == 0) return null;

            // Execute selected Sort mode
            if (sortFlag == 0)
            {
               filtered = filtered.OrderBy(p => entry.Is2D ? targetPt.DistanceTo(new Point3d(p.X, p.Y, targetPt.Z)) : targetPt.DistanceTo(p)).ToList();
            }
            else
            {
               filtered = filtered.OrderBy(p => {
                  double angle = Math.Atan2(p.Y - targetPt.Y, p.X - targetPt.X);
                  return angle < 0 ? angle + (2 * Math.PI) : angle;
               }).ToList();
            }

            // API Standard Rule Check: If count is 1, return single item. Else, return list.
            if (count == 1)
            {
               return filtered[0];
            }

            ResultBuffer rb = new ResultBuffer();
            rb.Add(new TypedValue((int)LispDataType.ListBegin));
            foreach (Point3d pt in filtered) rb.Add(new TypedValue((int)LispDataType.Point3d, pt));
            rb.Add(new TypedValue((int)LispDataType.ListEnd));
            return rb;
         }
         catch { return null; }
      }

      // --------------------------------------------------------------------------------
      // 3. (gc:kd-nearest-info handle targetPoint [count] [maxRadius])
      // --------------------------------------------------------------------------------
      [LispFunction("GC:KD-NEAREST-INFO")]
      public static object GileKdNearestInfo(ResultBuffer args)
      {
         if (args == null) return null;
         TypedValue[] arr = args.AsArray();
         if (arr.Length < 2) return null;

         try
         {
            string handle = Convert.ToString(arr[0].Value);
            if (!_registry.TryGetValue(handle, out var entry)) return null;

            Point3d targetPt = (Point3d)arr[1].Value;
            int count = 1;
            double maxRadius = double.MaxValue;

            if (arr.Length >= 3) count = Convert.ToInt32(arr[2].Value);
            if (arr.Length >= 4) maxRadius = Convert.ToDouble(arr[3].Value);

            var searchCollection = entry.Tree.GetNearestNeighbours(targetPt, count);
            if (searchCollection == null) return null;

            ResultBuffer rb = new ResultBuffer();
            rb.Add(new TypedValue((int)LispDataType.ListBegin));

            // Re-locate matches to extract array index mappings cleanly
            int idx = 0;
            foreach (Point3d pt in searchCollection)
            {
               double dist = entry.Is2D ? targetPt.DistanceTo(new Point3d(pt.X, pt.Y, targetPt.Z)) : targetPt.DistanceTo(pt);
               if (dist <= maxRadius)
               {
                  rb.Add(new TypedValue((int)LispDataType.ListBegin));
                  rb.Add(new TypedValue((int)LispDataType.Point3d, pt));
                  rb.Add(new TypedValue((int)LispDataType.Int32, idx)); // Metadata index placement
                  rb.Add(new TypedValue((int)LispDataType.Double, dist));
                  rb.Add(new TypedValue((int)LispDataType.ListEnd));
               }
               idx++;
            }

            rb.Add(new TypedValue((int)LispDataType.ListEnd));
            return rb;
         }
         catch { return null; }
      }

      // --------------------------------------------------------------------------------
      // 4. (gc:kd-range handle centerPoint radius)
      // --------------------------------------------------------------------------------
      [LispFunction("GC:KD_RANGE")]
      public static object GileKdRange(ResultBuffer args)
      {
         if (args == null) return null;
         TypedValue[] arr = args.AsArray();
         if (arr.Length < 3) return null;

         try
         {
            string handle = Convert.ToString(arr[0].Value);
            if (!_registry.TryGetValue(handle, out var entry)) return null;

            Point3d centerPt = (Point3d)arr[1].Value;
            double radius = Convert.ToDouble(arr[2].Value);

            // Passing a double directly to GetNearestNeighbours switches Gilles' engine to range search
            var searchCollection = entry.Tree.GetNearestNeighbours(centerPt, radius);
            if (searchCollection == null) return null;

            // Enforce distance sort ordering
            var sorted = searchCollection.OrderBy(p => entry.Is2D ? centerPt.DistanceTo(new Point3d(p.X, p.Y, centerPt.Z)) : centerPt.DistanceTo(p)).ToList();

            ResultBuffer rb = new ResultBuffer();
            rb.Add(new TypedValue((int)LispDataType.ListBegin));
            foreach (Point3d pt in sorted) rb.Add(new TypedValue((int)LispDataType.Point3d, pt));
            rb.Add(new TypedValue((int)LispDataType.ListEnd));
            return rb;
         }
         catch { return null; }
      }

      // --------------------------------------------------------------------------------
      // 5. NEW! (gc:kd-minnode handle dimension) -> Useful for Concave Hull base logic
      // --------------------------------------------------------------------------------
      [LispFunction("GC:KD-MINNODE")]
      public static object GileKdMinNode(ResultBuffer args)
      {
         if (args == null) return null;
         TypedValue[] arr = args.AsArray();
         if (arr.Length < 2) return null;

         try
         {
            string handle = Convert.ToString(arr[0].Value);
            if (!_registry.TryGetValue(handle, out var entry)) return null;

            int dimension = Convert.ToInt32(arr[1].Value); // 0=X, 1=Y, 2=Z

            // Target standard range query over all nodes to run aggregate matching
            var allPoints = entry.Tree.GetNearestNeighbours(Point3d.Origin, double.MaxValue);
            if (allPoints == null || !allPoints.Any()) return null;

            Point3d minPoint;
            switch (dimension)
            {
            case 0: // Minimum X coordinate
               minPoint = allPoints.OrderBy(p => p.X).First();
               break;
            case 1: // Minimum Y coordinate
               minPoint = allPoints.OrderBy(p => p.Y).First();
               break;
            case 2: // Minimum Z coordinate
               minPoint = allPoints.OrderBy(p => p.Z).First();
               break;
            default:
               return null;
            }

            return minPoint;
         }
         catch { return null; }
      }

      // --------------------------------------------------------------------------------
      // 6. (gc:kd-free [handle])
      // --------------------------------------------------------------------------------
      [LispFunction("GC:KD-FREE")]
      public static object GileKdFree(ResultBuffer args)
      {
         int removedCount = 0;
         if (args == null)
         {
            removedCount = _registry.Count;
            _registry.Clear();
            _autoId = 1;
         }
         else
         {
            TypedValue[] arr = args.AsArray();
            if (arr.Length > 0 && arr[0].TypeCode == (int)LispDataType.Text)
            {
               string handle = Convert.ToString(arr[0].Value);
               if (_registry.Remove(handle)) removedCount = 1;
            }
            else
            {
               removedCount = _registry.Count;
               _registry.Clear();
               _autoId = 1;
            }
         }

         GC.Collect();
         GC.WaitForPendingFinalizers();
         return removedCount;
      }

      // --------------------------------------------------------------------------------
      // INTERNAL ROUTINE: Streamlined input coordinate list extractor
      // --------------------------------------------------------------------------------
      private static List<Point3d> ParseLispPoints(TypedValue[] arr, int startIndex, out int readCount)
      {
         var collected = new List<Point3d>();
         readCount = 0;
         for (int i = startIndex; i < arr.Length; i++)
         {
            if (arr[i].Value is Point3d pt)
            {
               collected.Add(pt);
               readCount++;
            }
            else if (arr[i].TypeCode == (int)LispDataType.ListEnd || arr[i].TypeCode == (int)LispDataType.Int32 || arr[i].TypeCode == (int)LispDataType.Text)
            {
               break; // Stopped at non-point parameter boundaries
            }
         }
         return collected;
      }
   }
}

essentially the same command that I had in my post.  

[Danielm103]

this was a fun challenge using KDTrees  https://www.theswamp.org/index.php?topic=59487.0