我有一个未排序的嘈杂 X、Y 点列表。然而，它们确实形成了一条穿越世界的道路。我想要一种算法来使用线段绘制这些数据的近似值。
这类似于您如何使用线拟合算法来选择线性数据的近似值。我的问题更加困难，因为这条路在世界各地弯曲和蜿蜒。 替代文字 http://www.praeclarum.org/so/pathfinder.png
有谁知道任何标准/强大/易于理解的算法来实现这一点？
问答：
你说的吵是什么意思？如果我有一个理想的路径实现，那么我的一组点将从该理想路径中采样，并将高斯噪声添加到 X 和 Y 元素。我不知道该噪声的平均值或标准偏差。我也许可以猜到std dev ...
这些点是否靠近但不在您寻求近似的理想但复杂的路径上？是的。
你有关于路径形状的任何先验信息吗？还有其他方法可以获取此类信息吗？不幸的是没有。
使用未排序的列表，您将不会真正知道每个段中要包含哪些点，所以我想您可以选择最近的点。
一种方法是随机选择一个起点，然后在每一步中选择最近的点作为下一个点。将前两个点添加到集合 S。
将一条线拟合到 S 中的点，直到 RMS 超过某个值，然后清除 S 并开始一条新线。
连续线的交点将是线段的端点。
如果您的点彼此靠近，则可以使用普通的“直线”（正交线）。使用正常的平滑算法。你可以看到世界是平的。
如果它们相距很远，您需要通过使用大圆圈从一个点导航到另一个点来补偿地球的圆度。否则你的直线会走得更远。
如果一个点太远而无法创建直线，这是您的选择。
此外，您必须知道您是否需要“访问”每个点，或者只需要靠近，以及该附近有多近。
如果您需要将课程发送给飞机、轮船或其他旅行者，您可能需要访问每个点。如果您从一个对象获取 GPS 数据，您可能只想在屏幕上绘制一条路线，并消除噪音。
看到你的编辑后： 如果这是一个移动你想要绘制的轨迹的对象，你可能想要平滑方向和速度而不是 x/y 值。（使您的测量值 (x) 具有固定且增加的 Y 间隔使平滑变得更容易。）
这是一个启发式技巧，可以解决数据的排序问题，如果
像这样进行：
现在你有一个新的点q1 .. qn列表。
在我的头顶上，非常粗糙，只有在相当好的条件下才能工作......
通过在步骤 (5) 中要求新投影线位于前一个投影线的某个最大角度内，可能可以改进自交叉行为。
贝塞尔曲线的问题在于它实际上并没有通过您采样的点，即使点样本有点失真；贝塞尔曲线实际上可能相距几英里。
Catmull-Rom Spline是一个更好的近似值，并且似乎更接近原始图像的解决方案是Catmull-Rom Spline，因为它确实通过了曲线中的所有点。
我的方法是首先对点列表进行排序，然后使用贝塞尔曲线。
诀窍当然是排序。从一个随机点开始，找到最近的点。假设这两个是连接的。使用这两个端点，找到离它们最近的点。假设到它的端点距离较小的那个连接到那个点。重复直到所有点都连接。
我认为这种方法仍然存在一些问题，但也许您可以将其用作起点（双关语）。
编辑：你可以用不同的起点做几次，然后看看结果有什么不同。这至少给了你一些信心，哪些点是相互连接的。
一种完全不同的方法，不需要其他约束，但细节可能取决于您的应用程序。如果您在路径周围有“密集的点云”，它应该效果最好。
使用定义曲线和点云之间差异的“成本”函数。使用参数化曲线和标准优化算法。- 或 - 从头到尾从一条直线开始，然后使用遗传算法对其进行修改。
典型的成本函数是取每个点和曲线之间的最小距离，并对平方求和。
我没有足够的经验来建议优化或遗传算法，但我相信可以做到:)
我可以想象一个遗传算法如下：路径将从航点构建。首先将 N 个航路点从头到尾排成一条直线。（可以根据问题选择N）。突变可能是：
您需要在成本函数中包含总长度。可能不需要拆分，或者随着更多航路点的引入，x（“拆分机会”）可能需要减少。您可能希望也可能不希望将 (2) 应用于起点和终点。
尝试一下会很有趣...
我认为“未排序的列表”意味着虽然您的点集是完整的，但您不知道它们经过的顺序是什么？
基本上必须忽略高斯噪声。我们绝对没有任何信息可以让我们尝试重建原始的、无噪音的路径。所以我认为我们能做的最好的就是假设这些观点是正确的。
此时，任务包括“通过一组点找到最佳路径”，其中“最佳”保持模糊。我编写了一些代码，试图在欧几里得空间中对一组点进行排序，更喜欢产生直线的排序。虽然该指标很容易实现，但我想不出一个基于此改进排序的好方法，所以我只是随机交换点以寻找更好的安排。
所以，这里有一些 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 的建议找到“黄金曲线”的贝塞尔曲线并绘制它。
你有多少分？
如前所述，如果您的点数相对较少，则贝塞尔曲线是一个好主意。如果您有很多点，请按照 dmckee 的建议构建集群。
但是，您还需要另一个约束来定义点的顺序。关于如何选择点有很多很好的建议，但除非你引入另一个约束，否则任何一个都可以提供可能的解决方案。
我能想到的可能限制：
在所有情况下，为了满足约束，您可能需要测试序列的所有排列。如果您从“好猜测”开始，您可以快速终止其他人。