【排序】关于点排序的误差值问题

ll_j · 发表于 2013-10-23 16:35:22

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？立即注册

×

最近关于点排序的函数不少，似乎都默认了一个设置，就是坐标的误差值，今天晓东自己出了一系列原始函数的点排序函数，其中也包括了“误差”，那么，这个使用了“误差”后结果是否还正确呢？
看看一个例子：

(setq lst '((1.0 1.0)
(0.9 0.9)
(0.8 0.8)
(0.7 0.7)
(0.6 0.6)
(0.5 0.5)
(0.4 0.4)
(0.3 0.3)
(0.2 0.2)
(0.1 0.1)
(0.0 0.0)
)
)

结果（原函数链接：http://bbs.xdcad.net/thread-671240-1-1.html）：
_$ (XD::PNTS:MinY->MinX lst 0.11)
((0.2 0.2) (0.1 0.1) (0.0 0.0) (0.5 0.5) (0.4 0.4) (0.3 0.3) (0.8 0.8) (0.7 0.7) (0.6 0.6) (1.0 1.0) (0.9 0.9))
_$
可以看出，这里因为误差大了点，就出问题了，结果不是排好的表，倒是可以看出vl-sort函数采用的排序算法。
似乎0.11的误差对于前后坐标差值为1应该不算什么，但结果为什么错呢？，仔细考虑vl-sort函数的工作原理就可以看出，函数是只把相邻的两个值进行比较，不满足条件就前后变换，并不考虑整体的情况，也就是说，误差是“积累”的，当某些同向的误差积累在一起时，结果就不正确了。
个人以为，排序时完全不必考虑所谓误差，虽然浮点运算本身也会带来误差，但这些误差多数只是发生在某些点，因而不会积累，计算结果也就不会出错。
至于以后再进行二次分拆，应该是另外的过程，而且，二次分拆的参考点也不应该是浮动的。

eachy · 发表于 2013-10-23 21:25:17

以前考虑过这个误差，涉及到一个基点问题，比如一个 Net 格点， X Y 都是等距，不能按蚂蚁算法，由基点找到下一个点，再由找到的点作基点，这样整个 Net 就是一个 Equal 了，对这种情况要基点不变才能分出来， vl-sort 应该也是按这个规则才有意义，基点确定，误差限定

(equal p1 p2 fuzz) 含义见下图

ysq101 · 发表于 2013-10-23 16:37:42

高手华山论剑........我等小辈只有看热闹的份了

/db_自贡黄明儒_ · 发表于 2013-10-23 16:52:32

学习了，原来vl-sort是这么干的呀

XDSoft · 发表于 2013-10-23 17:58:39

任何一个使用误差的地方都是相对要求的，误差主要是用在点相等的时候判断上，因为要找最小或者最大的，

当然这个误差取值多少由程序员定，如果定的误差值，很大，超过了点的距离范围，那么就会乱了，就不是希望的结果了。

这个误差，主要是把在一排的，比如文字，虽然不是严格的对齐，但行内还是算一行的时候，排序就当做一排来做了。所以，这个时候这个误差给值就不要超过字的行高，或者半高（由写程序者定）。

如果不给误差参数的话，对这种近似一行处理成一行的时候就没办法做了。

Free-Lancer · 发表于 2013-10-23 18:30:24

前几天实验这个点表怎么算误差，就是 x y 分别±这个数，点为圆心，数为半径，圆内的为 equal

newer · 发表于 2013-10-23 19:30:39

本帖最后由 newer 于 2013-10-23 19:31 编辑

实际上，看了代码，这个误差是在算 X,Y实数值的误差，就是上面老大说的近似一行的算一行，并不是算点。就是这个误差值的设置，是把一些误差内的都当做一行或者一列，这个是程序的目的，所以就有了长老测试时候发现乱了，因为你给的误差值大了，把他们都当做一行或者一列了。

(defun XD::PNTS:MinY->MaxX (pts Tol / pt1 pt2)
  (vl-sort pts '(lambda (pt1 pt2)
               (if (equal (cadr pt1) (cadr pt2) tol)
                  (if (equal (car pt1) (car pt2) tol)
                  (< (caddr pt1) (caddr pt2))
                  (> (car pt1) (car pt2))
                  )
                  (< (cadr pt1) (cadr pt2))
               )
            )
  )

账号		自动登录	找回密码
密码			立即注册

[研讨] 【排序】关于点排序的误差值问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。