为了序列化,将一系列点转化为曲线的最优化方法是什么?

我正在做一个电子游戏,我需要展示一个实际的欧洲大城市(巴黎,伦敦,马德里…那种大)的地图(2D),以及在地图上显示为简单点的玩家,沿着街道线路可以采取不同的路线。

为此,我从OpenStreetMap.org提取真实的数据。 多亏了它,我可以访问大量的数据和地理信息,其中我有街道视觉设置作为一系列的坐标(长/经纬度转换为X / Y点使用正确的投影)。 在OpenStreetMap中,街道由一组点组成,因此在这些点之间画一条线就足以显示街道。

然而它代表了大量的加载点,这意味着处理数据的时间很长,这意味着:不理想。 比如像巴黎这样的大城市就有65000个街点。 这是巨大的。 为了减less这个数字,仍然能够绘制/遵循街道曲线,我正在考虑使用一个只包含在街道交叉点暗示的曲线图和曲线方程来描述街道显示的图。 这样一个由2000分组成的街道,其理论上不会比由10分组成的大得多。

最初的技术 最后的目标

在这个例子中,我的初始设置是由13个点(红十字)组成的,以显示一条街道。 在这种情况下,我的目标是保持4点(与其他街道的交叉点)和每个点之间的实际“方程”(或类似的东西),以减小最终地图的磁盘上的大小。

这是我卡住的地方。 我吮吸math(每天都后悔)。 所以我不能确定什么是将一系列点转化为一个简单方程的最好方法,这个方程将允许我在运行时遵循实际的街道曲线。

我不知道该怎么做…我读过关于贝塞尔曲线的东西,关于Clothoids,Circular Arcs …但我不知道从哪里开始,这里最好的解决scheme是什么,如何使用我的一系列点这些技术之一,或者如果它真的是聪明的事情,以减less地图的大小(以字节为单位)…

任何帮助,将不胜感激。

谢谢。

街道可以很时髦,充满曲折。 这可以使得用y = f(x)forms的函数来描述一个函数是困难的或不可能的,其中xy是笛卡尔坐标。 无论你在哪里select原点,极坐标也常常会失败。 因此,我认为你最好的办法是创建一个参数曲线 – 即一个关系,使得任何一个点(x,y)都可以用某个参数t函数表示:

 (x,y) = (f(t), g(t)) 

当你做这样的曲线拟合时,最好让t与弧长s成比例,这就告诉你曲线上的哪个位置。 然后你可以把t作为以某个恒定速度沿着曲线移动的时间(通常设置为1 )。

步骤1:一个好的近似

假设网格上有十个点{p1,p2,p3,p4,p5,p6,p7,p8,p9,p10} ,每个点的坐标为pj=(xj,yj) 。 你想创建一个包含它们的曲线P(t) 。 曲线从p1开始,从pjp(j+1)直到到达p10 ,停止。

我们需要弄清曲线上的人到达下一个点的时间,即两点之间的距离。 如果它们足够接近,那么线性近似就足够了。 在伪代码中:

 p1 = (x1,y1) p2 = (x2,y2) xdiff = x2 - x1 ydiff = y2 - y1 dist = sqrt(xdiff^2+ydiff^2) 

我们每两分钟做一次。 如果P(t1) = p1 ,则P(t2 - t1) = p2 ,其中t2p1p2之间的直线距离。 如果我们想要的话,我们可以设置t1 = 0 ,为了简单起见,假设p1是端点之一。

在我们完成所有要点之后,我们有三组数字:

 T = {t1,t2,t3,t4,t5,t6,t7,t8,t9,t10} X = {x1,x2,x3,x4,x5,x6,x7,x8,x9,x10} Y = {y1,y2,y3,y4,y5,y6,y7,y8,y9,y10} 

所以在t=tj ,曲线在点pj(xj,yj) 。 现在我们可以插入。 您可以构造两个拉格朗日多项式 1 ,每个xy坐标各一个,每个都用t 。 这个公式很简单,但手工显然更难。

我们现在有一个描述所有点的参数曲线。

可是等等! 这仍然需要很多系数,我们正试图减less这个系数。 那么为什么我们甚至这样做呢?

第2步:删除一些点。

假设我们只想使用四点。 这是合理的。 我将select端点和其他两个端点: {p1,p4,p7,p10} 。 现在,我们可以像以前一样做同样的事情。 事实上,我们可以通过find线性距离来完成我们在第一步中做的插值。 如果你的曲线在每段中只有一点偏离直线,那就没问题了。 但是,情况往往不是这样。 通过简单地findp4p7之间的最短距离,我们会认为这两者距离更近,使得曲线有很大的不同。

因此,我们从第一步开始。 我们根据我们的插值曲线Pfind这两点之间的长度,使用全部十个点。 这可以通过find弧长来完成。 我建议使用数字方法。 然后我们有三组:

 T = {t1',t4',t7',t10'} X = {x1,x4,x7,x10} Y = {y1,y4,y7,y10} 

我用质数来表明我们发现的时间与我们在第一步所做的不同。 他们可能会更准确。 现在我们做同样的插值,只有四点。

我们现在有一个曲线的参数方程,只用了四个点。 它比第一个方程式准确得多,但它使用的数据less得多,并且保证了曲线仍然会穿过这四个点(这是多项式回归的一个问题 – 很less有最佳拟合曲线会通过任何一个点)。

现在,我们可以跳过第一步。我知道,也许你感到失望。 如前所述,我们可以使用四点之间的线性距离。 但是这样会忽略曲线的大部分细节,如果将曲线从20点缩短到6点,跳过第一次插值可能会非常昂贵。


1拉格朗日多项式(未参数化)的forms

在这里输入图像描述

哪里

在这里输入图像描述

这是拉格朗日多项式背后的推理(在这种情况下,没有参数化 – y直接是x的函数)。 你有n个坐标为{(x1,y1),(x2,y2), . . . ,(xn,yn)} {(x1,y1),(x2,y2), . . . ,(xn,yn)} {(x1,y1),(x2,y2), . . . ,(xn,yn)} 。 你想要一个非参数化函数y = f(x) 。 要做到这一点的最简单的方法是用n术语来提出一个函数。 在每个点pj ,即当x = xj ,除了一个项外,我们称之为第j项 – 将变为零,剩余项将等于yj 。 从这里开始,为任意点pl构造第二个expression式是简单的,并且您只需将n项相加,每个项对应于不同的plxlyl 。 这给你一组点的拉格朗日多项式。

在您将拉格朗日多项式应用到街道上时,我们做了同样的事情 – 只是参数化。