我有一个未排序的嘈杂 X、Y 点列表。然而,它们确实形成了一条穿越世界的道路。我想要一种算法来使用线段绘制该数据的近似值。

这类似于使用直线拟合算法来选择线性数据的近似值。我的问题变得更加困难,因为这条路在世界各地弯曲和蜿蜒。替代文本 http://www.praeclarum.org/so/pathfinder.png

有谁知道任何标准/强大/易于理解的算法来完成此任务?

问答:

你说的吵闹是什么意思? 如果我对路径有一个理想的实现,那么我的点集将从该理想路径中采样,并将高斯噪声添加到 X 和 Y 元素。我不知道该噪音的平均值或标准差。我也许可以猜测标准开发......

这些点是否位于您寻求近似的理想但复杂的路径附近,但不在其上? 是的。

您有关于路径形状的先验信息吗?还有其他方法可以获取此类信息吗? 不幸的是没有。

有帮助吗?

解决方案

使用未排序的列表,你不会真正知道每个段中包含哪些点,所以我猜你可以选择最接近的点。

一种方法是随机选择一个起始点,并选择最近的点作为每个步骤中的下一个点。将前两个点添加到集合S。

在S中的点拟合直到RMS超过某个值,然后清除S并开始换行。

连续线的交点将是段的终点。

其他提示

贝塞尔曲线插值 可能适合你的问题。

Bezier Interpolation

然而,这并没有解决路径中点的排序问题。有多种方法可供考虑:

  • 任何“最佳”类型的路径(例如路径上每个点的最小方向变化,*通过所有点的最短路径)可能会完全归结为 NP 旅行商问题 (TSP)。
  • 对节点进行集群的“合理”路径,然后在集群之间和集群内进行路由。当然,集群越大,或者集群数量越多,这个较小的问题看起来就越像一个大的 n TSP。
  • 按一个轴对点进行排序。如果轴数远多于 2 个,则有些 降维 策略可能有用。例如独立成分分析。

如果你的分数彼此接近,你可以正常<!>“直线<!>”;线(正交线)。使用正常的平滑算法。你可以看到这个世界是扁平的。

如果它们相隔很远,你需要通过使用大圆圈来弥补地球的四舍五入从一点到另一点导航。否则你的直线会走得更远。

如果一个点太远而无法创建直线,则可以选择。

此外,您必须知道是否需要<!>“访问<!>”;每个点,或者只是需要靠近,以及附近的距离。

如果您需要将课程发送到飞机,船舶或其他旅行者,您可能需要访问每个点。如果您从对象获取GPS数据,您可能只想在屏幕上绘制一条路线,并消除噪音。


看到您的修改后 如果这是一个移动您想要绘制的轨迹的对象,您可能希望平滑方向和速度而不是x / y值。 (使您的测量值(x)具有固定且增加的Y间隔使得平滑变得更容易。)

这是一个启发式技巧,可以解决数据的排序问题,如果

  • 你有足够的积分
  • 与路径预期的最小曲率半径相比,点之间的平均距离较小
  • 与标准相比,点之间的平均距离并不大。开发人员。噪音的
  • 路径不是自交叉的(你可能会很幸运,但不能保证)

像这样进行:

  1. 选择(希望通过有意义的而不是随机的方式)一个起点, p1.
  2. 找到位于某个聚类距离内的所有点, r_cp1. 。选择 r_c 与预期转弯半径相比较小,但与分散相比较大。
  3. 调用这个集群 C1.
  4. 找点 q1 位置的平均值 C1.
  5. 将一条线拟合到其中的点 C1 并投影到(或超出)簇的边缘,并找到原始数据中最近的点。标记该点 p2.
  6. 重复步骤 2-5,直到用完数据。

现在您有了一个新的点列表 q1..qn 已订购的。

从我的头顶上看,非常粗糙,并且只能在相当好的条件下工作......


通过在步骤(5)中要求新的投影线位于前一条投影线的某个最大角度内,可以改善自交叉行为。

Bezier曲线的问题在于,实际上并没有通过您采样的点,即使点样本有点失真; bezier曲线可能实际上是数英里之外。

更好的近似,并且似乎更好地类似于原始图像方式的解决方案是 Catmull-Rom Spline 因为它确实在曲线中的所有点上运行。

我的方法是首先对点列表进行排序,然后使用贝塞尔曲线。

诀窍当然是排序。从一个随机点开始,找到最近的点。假设这两个是相连的。使用这两个端点,找到最近的点。假设与其端点距离较小的那个连接到该点。重复,直到所有点都连接起来。

我认为这种方法仍然存在一些问题,但也许你可以将它作为一个起点(双关语)。

修改:您可以使用不同的起点多次执行此操作,然后查看结果的不同之处。这至少会给你一些信心,哪些点相互联系。

完全不同的方法,不需要其他约束,但细节可能取决于您的应用程序。如果你有一个<!>密集的点云<!>,那么它会发挥得最好。在路径周围。

使用<!>“;费用<!>”;定义曲线和点云之间差异的函数。使用参数化曲线和标准优化算法。 - 要么 - 从头到尾以直线曲线开始,然后使用遗传算法对其进行修改。

典型的成本函数是采用每个点和曲线之间的最小距离,并对平方进行求和。

我没有足够的经验建议优化或遗传算法,但我相信它可以做到:)

我可以想象一个遗传算法如下: 路径将从Waypoints构建。首先从开始到结束将N个航点放在一条直线上。 (可根据问题选择N)。突变可能是:

  1. 对于每个段,如果rnd()<!> lt; x,中间引入了新的航点。
  2. 对于每个航点,X和Y坐标略有不同。
  3. 您需要在费用函数中包含总长度。可能不需要拆分,或者可能需要减少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 的建议构建集群。

然而你 需要另一个约束来定义点的顺序。关于如何选择点有很多好的建议,但是除非引入另一个约束,否则任何都给出了可能的解决方案。

我能想到的可能的限制:

  • 最短的路径
  • 最直的线段
  • 最小总绝对旋转
  • 方向偏好(即水平/垂直比纵横交错的可能性更大)

在所有情况下,为了满足约束,您可能需要测试序列的所有排列。如果你从“正确的猜测”开始,你就不可能很快终止其他人。

许可以下: CC-BY-SA归因
不隶属于 StackOverflow
scroll top