如何从嘈杂的 X、Y 数据确定路径
-
04-07-2019 - |
题
我有一个未排序的嘈杂 X、Y 点列表。然而,它们确实形成了一条穿越世界的道路。我想要一种算法来使用线段绘制该数据的近似值。
这类似于使用直线拟合算法来选择线性数据的近似值。我的问题变得更加困难,因为这条路在世界各地弯曲和蜿蜒。替代文本 http://www.praeclarum.org/so/pathfinder.png
有谁知道任何标准/强大/易于理解的算法来完成此任务?
问答:
你说的吵闹是什么意思? 如果我对路径有一个理想的实现,那么我的点集将从该理想路径中采样,并将高斯噪声添加到 X 和 Y 元素。我不知道该噪音的平均值或标准差。我也许可以猜测标准开发......
这些点是否位于您寻求近似的理想但复杂的路径附近,但不在其上? 是的。
您有关于路径形状的先验信息吗?还有其他方法可以获取此类信息吗? 不幸的是没有。
解决方案
使用未排序的列表,你不会真正知道每个段中包含哪些点,所以我猜你可以选择最接近的点。
一种方法是随机选择一个起始点,并选择最近的点作为每个步骤中的下一个点。将前两个点添加到集合S。
在S中的点拟合直到RMS超过某个值,然后清除S并开始换行。
连续线的交点将是段的终点。
其他提示
如果你的分数彼此接近,你可以正常<!>“直线<!>”;线(正交线)。使用正常的平滑算法。你可以看到这个世界是扁平的。
如果它们相隔很远,你需要通过使用大圆圈来弥补地球的四舍五入从一点到另一点导航。否则你的直线会走得更远。
如果一个点太远而无法创建直线,则可以选择。
此外,您必须知道是否需要<!>“访问<!>”;每个点,或者只是需要靠近,以及附近的距离。
如果您需要将课程发送到飞机,船舶或其他旅行者,您可能需要访问每个点。如果您从对象获取GPS数据,您可能只想在屏幕上绘制一条路线,并消除噪音。
看到您的修改后 如果这是一个移动您想要绘制的轨迹的对象,您可能希望平滑方向和速度而不是x / y值。 (使您的测量值(x)具有固定且增加的Y间隔使得平滑变得更容易。)
这是一个启发式技巧,可以解决数据的排序问题,如果
- 你有足够的积分
- 与路径预期的最小曲率半径相比,点之间的平均距离较小
- 与标准相比,点之间的平均距离并不大。开发人员。噪音的
- 路径不是自交叉的(你可能会很幸运,但不能保证)
像这样进行:
- 选择(希望通过有意义的而不是随机的方式)一个起点, p1.
- 找到位于某个聚类距离内的所有点, r_c 的 p1. 。选择 r_c 与预期转弯半径相比较小,但与分散相比较大。
- 调用这个集群 C1.
- 找点 q1 位置的平均值 C1.
- 将一条线拟合到其中的点 C1 并投影到(或超出)簇的边缘,并找到原始数据中最近的点。标记该点 p2.
- 重复步骤 2-5,直到用完数据。
现在您有了一个新的点列表 q1..qn 已订购的。
从我的头顶上看,非常粗糙,并且只能在相当好的条件下工作......
通过在步骤(5)中要求新的投影线位于前一条投影线的某个最大角度内,可以改善自交叉行为。
Bezier曲线的问题在于,实际上并没有通过您采样的点,即使点样本有点失真; bezier曲线可能实际上是数英里之外。
更好的近似,并且似乎更好地类似于原始图像方式的解决方案是 Catmull-Rom Spline 因为它确实在曲线中的所有点上运行。
我的方法是首先对点列表进行排序,然后使用贝塞尔曲线。
诀窍当然是排序。从一个随机点开始,找到最近的点。假设这两个是相连的。使用这两个端点,找到最近的点。假设与其端点距离较小的那个连接到该点。重复,直到所有点都连接起来。
我认为这种方法仍然存在一些问题,但也许你可以将它作为一个起点(双关语)。
修改:您可以使用不同的起点多次执行此操作,然后查看结果的不同之处。这至少会给你一些信心,哪些点相互联系。
完全不同的方法,不需要其他约束,但细节可能取决于您的应用程序。如果你有一个<!>密集的点云<!>,那么它会发挥得最好。在路径周围。
使用<!>“;费用<!>”;定义曲线和点云之间差异的函数。使用参数化曲线和标准优化算法。 - 要么 - 从头到尾以直线曲线开始,然后使用遗传算法对其进行修改。
典型的成本函数是采用每个点和曲线之间的最小距离,并对平方进行求和。
我没有足够的经验建议优化或遗传算法,但我相信它可以做到:)
我可以想象一个遗传算法如下: 路径将从Waypoints构建。首先从开始到结束将N个航点放在一条直线上。 (可根据问题选择N)。突变可能是:
- 对于每个段,如果rnd()<!> lt; x,中间引入了新的航点。
- 对于每个航点,X和Y坐标略有不同。 醇>
您需要在费用函数中包含总长度。可能不需要拆分,或者可能需要减少x(<!>“拆分机会<!>”;),因为引入了更多的航路点。您可能想要也可能不想将(2)应用于起点和终点。
尝试这个会很有趣......
我认为<!> quot; unsorted list <!> quot;意味着当你的点数完成时,你不知道他们通过了什么顺序?
必须基本忽略高斯噪声。我们绝对没有任何信息可以让我们尝试重建原始的,不嘈杂的路径。所以我认为我们能做的最好就是假设这些点是正确的。
此时,任务包含<!>“;找到通过一组点<!>”的最佳路径,带有<!> quot; best <!> quot;离开模糊。我掀起了一些试图在欧几里德空间中订购一组点的代码,更喜欢导致线条更直的订单。虽然该指标很容易实现,但我想不出一个改进基于此的排序的好方法,所以我只是随机交换点以寻找更好的安排。
所以,这里有一些PLT Scheme代码可以做到这一点。
#lang scheme
(require (only-in srfi/1 iota))
; a bunch of trig
(define (deg->rad d)
(* pi (/ d 180)))
(define (rad->deg r)
(* 180 (/ r pi)))
(define (euclidean-length v)
(sqrt (apply + (map (lambda (x) (expt x 2)) v))))
(define (dot a b)
(apply + (map * a b)))
(define (angle-ratio a b)
(/ (dot a b)
(* (euclidean-length a) (euclidean-length b))))
; given a list of 3 points, calculate the likelihood of the
; angle they represent. straight is better.
(define (probability-triple a b c)
(let ([av (map - a b)]
[bv (map - c b)])
(cos (/ (- pi (abs (acos (angle-ratio av bv)))) 2))))
; makes a random 2d point. uncomment the bit for a 3d point
(define (random-point . x)
(list (/ (random 1000) 100)
(/ (random 1000) 100)
#;(/ (random 1000) 100)))
; calculate the likelihood of an entire list of points
(define (point-order-likelihood lst)
(if (null? (cdddr lst))
1
(* (probability-triple (car lst)
(cadr lst)
(caddr lst))
(point-order-likelihood (cdr lst)))))
; just print a list of points
(define (print-points lst)
(for ([p (in-list lst)])
(printf "~a~n"
(string-join (map number->string
(map exact->inexact p))
" "))))
; attempts to improve upon a list
(define (find-better-arrangement start
; by default, try only 10 times to find something better
[tries 10]
; if we find an arrangement that is as good as one where
; every segment bends by 22.5 degrees (which would be
; reasonably gentle) then call it good enough. higher
; cut offs are more demanding.
[cut-off (expt (cos (/ pi 8))
(- (length start) 2))])
(let ([vec (list->vector start)]
; evaluate what we've started with
[eval (point-order-likelihood start)])
(let/ec done
; if the current list exceeds the cut off, we're done
(when (> eval cut-off)
(done start))
; otherwise, try no more than 'tries' times...
(for ([x (in-range tries)])
; pick two random points in the list
(let ([ai (random (vector-length vec))]
[bi (random (vector-length vec))])
; if they're the same...
(when (= ai bi)
; increment the second by 1, wrapping around the list if necessary
(set! bi (modulo (add1 bi) (vector-length vec))))
; take the values from the two positions...
(let ([a (vector-ref vec ai)]
[b (vector-ref vec bi)])
; swap them
(vector-set! vec bi a)
(vector-set! vec ai b)
; make a list out of the vector
(let ([new (vector->list vec)])
; if it evaluates to better
(when (> (point-order-likelihood new) eval)
; start over with it
(done (find-better-arrangement new tries cut-off)))))))
; we fell out the bottom of the search. just give back what we started with
start)))
; evaluate, display, and improve a list of points, five times
(define points (map random-point (iota 10)))
(define tmp points)
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 100))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 1000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
似乎你从问题的答案中知道了“黄金曲线”,我建议找到@jamesh建议的“黄金曲线”的Bezier曲线并绘制它。
你有多少积分?
如前所述,如果点相对较少,贝塞尔曲线是一个好主意。如果您有很多点,请按照 dmckee 的建议构建集群。
然而你 还 需要另一个约束来定义点的顺序。关于如何选择点有很多好的建议,但是除非引入另一个约束,否则任何都给出了可能的解决方案。
我能想到的可能的限制:
- 最短的路径
- 最直的线段
- 最小总绝对旋转
- 方向偏好(即水平/垂直比纵横交错的可能性更大)
在所有情况下,为了满足约束,您可能需要测试序列的所有排列。如果你从“正确的猜测”开始,你就不可能很快终止其他人。