[求助]在一组坐标数据中，找到最接近的，两两配对

leilei4908

各位有什么比较好的方法？
目前只能用穷举法
anb = nil
foreach(xya xys
   xyb = nil
   dLmin = 999999
   foreach(xyt cdr(xys)
      dX = car(xya) - car(xyt)
      dY = cadr(xya) - cadr(xyt)
      dL = sqrt(dX**2 + dY**2)
      when(dL < dLmin && dL > 0
         dLmin = dL
         xyb = xyt
      )
   )
   when(xyb
      anb = cons(list(xya xyb) anb)
      xys = remove(xya xys)
      xys = remove(xyb xys)
   )
)

Getaway

我先看看你的程序

db-_-

只知道有一个经典的“平面最小点对”算法。实现起来不难。

要不，找到最小点对后，从list删掉，然后循环，直到剩下0个或者1个点。

leilei4908

db-_- 发表于 2022-5-19 23:27
只知道有一个经典的“平面最小点对”算法。实现起来不难。

要不，找到最小点对后，从list删掉，然后循环 ...

visible = axlVisibleGet()
        axlClearSelSet()
        axlVisibleDesign(nil)
        axlVisibleLayer("VIA CLASS" t)
        axlSetFindFilter(?enabled '("noall" "vias") ?onButtons '("noall" "vias"))
        vias = axlGetSelSet(axlAddSelectAll())
        axlClearSelSet()
        vias = setof(via vias via->net->diffpair)
        DP = makeTable("DP" nil)
        dpvias = nil
        dpxys = nil
        _ap = 100
        foreach(via vias
                DP[via->net->diffpair] = cons(via DP[via->net->diffpair])
        )
        foreach(dp DP->?
                dpName = dp->name
                vias = DP[dp]
                seln = nil
                for(i 1 length(vias)
                        unless(member(i seln)
                                ap = _ap
                                viai = nthelem(i vias)
                                for(j i+1 length(vias)
                                        unless(member(j seln)
                                                viaj = nthelem(j vias)
                                                ap_ = nthelem(3 axlAirGap(viai viaj))
                                                when(ap_ && ap_ < ap
                                                        vian = viaj
                                                        n = j
                                                        ap = ap_
                                                )
                                        )
                                )
                                when(ap < _ap
                                        seln = cons(i seln)
                                        seln = cons(n seln)
                                        dpvias = cons(list(viai vian) dpvias)
                                        dpxys = cons(list(viai->xy vian->xy ap) dpxys)
                                )
                        )
                )
                ;print(seln)
        )
        axlVisibleSet(visible)
        axlVisibleUpdate(t)

目前用穷举法写的代码
测试没有问题了
有更高效率的，请不吝赐教

db-_-

知道你的意思了，一般一对线，最多也就6个、8个孔。用什么方法完全都可忽略。

如果需要在10万个孔里面找，再考虑用算法比较合适。

db-_-

zs_king 发表于 2022-6-11 16:37
查找最近的两个孔的目的是什么？  不能通过net先筛选一遍过孔？

一对差分线，假如有4个过孔，其中2个网络是一样的，他是想找到哪两个过孔是一对。

xxxxc

zs_king 发表于 2022-6-13 17:27
一对差分线，假如有4个过孔，其中2个网络是一样的，他是想找到哪两个过孔是一对。

[/quote]

大佬 这个牛逼啊  能分享下么