KD-Tree in Python for AutoCAD

[Danielm103]

I incorporated nanoflann( https://github.com/jlblancoc/nanoflann) wrappers into PyRx.

Although other efficient KD-Tree implementations exist in Python, such as pykdtree, the wrapper is specifically designed for AcGePoint2d/AcGePoint3d, eliminating the need for type conversions.

 

How can these structures be beneficial in CAD?

in this example, we search for a phone within a certain radius of each computer. Additionally, we can identify computers that do not have phones.

We could also do something like, search all MTexts on the Layer "Employee" to determine whether they are near a chair, phone, or computer.

 

import traceback
from pyrx import Ap, Ax, Db, Ed, Ge, Gi, command

# radiusSearch
@command
def doit():
    db = Db.curDb()
    phones, computers = getBlocks(db)
    result = []

    # create the tree of phone locations
    phonePoints = Ge.Point3dArray()
    for phone in phones:
        phonePoints.append(phone[1])
    phoneTree = Ge.Point3dTree(phonePoints)

    # search for nerby phones
    for computer in computers:
        idxs, _ = phoneTree.radiusSearch(computer[1], 50 * 50)# sqrd
        if len(idxs) == 0:
            print("no phone")
            continue
        for idx in idxs:
            result.append((computer, phones[idx]))

    for cpu, phn in result:
        Ed.Core.grDraw(cpu[1], phn[1], 2, 0)


# helper, store the id and position
def getBlocks(db: Db.Database):
    phones = []
    computers = []
    model = Db.BlockTableRecord(db.modelSpaceId())
    refs = [Db.BlockReference(id) for id in model.objectIds(Db.BlockReference.desc())]
    for ref in refs:
        if ref.getBlockName() == "COMPUTER":
            computers.append((ref.objectId(), ref.position()))
        elif ref.getBlockName() == "FNPHONE":
            phones.append((ref.objectId(), ref.position()))
    return phones, computers

 

Edited yesterday at 10:11 AM by Danielm103

[BIGAL]

Very interesting, did something similar, I made a "where are they" map, it had a grid over the office floor so had a big staff list Bigal lev 5, A 1. I used the phone number as a link to an image of each staff member, so their picture appeared on their desk I simply saved each staff image as the extension number. It was reasonably fast making the new dwg inserting around 100 photo's per floor we worked in a 5 story building. 

[Danielm103]

KD-Trees are amazingly powerful, and most always overlooked because of their complexity to create and use. I’m always guilty of using brute-force tactics before forcing myself into using a better algorithm. Hopefully Point2dTree and Point3dTree will remove most of the complexities, make them more accessible

The particular tree (nanoflann) is more geared towards point clouds, very fast. Should do 10^7 points in the blink of an eye