相关疑难解决方法(0)

我有一些地理数据(下面的图像显示了河流的路径为红点),我想用多段三次贝塞尔曲线近似.通过对计算器等问题,在这里和这里我发现由Philip J.施耐德从"图形宝石"的算法.我成功地实现了它并且可以报告即使有数千个点它也非常快.不幸的是,速度带来了一些缺点,即装配非常不合适.请考虑以下图形:

红点是我的原始数据,蓝线是由Schneider算法创建的多段贝塞尔曲线.如您所见,算法的输入是一个容差,至少与绿线表示的一样高.然而,该算法创建了具有太多急转弯的贝塞尔曲线.你也会在图像中看到这些不必要的急转弯.很容易想象,对于所示数据,具有较小急转弯的贝塞尔曲线,同时仍保持最大公差条件(仅将贝塞尔曲线稍微推向品红色箭头的方向).问题似乎是算法从我的原始数据中选取数据点作为各个贝塞尔曲线的终点(品红箭头指示一些嫌疑人).由于贝塞尔曲线的端点受到限制,很明显该算法有时会产生相当尖锐的曲率.

我正在寻找的是一种算法,它使用具有两个约束的多段贝塞尔曲线来近似我的数据:

• 多段贝塞尔曲线绝不能超过数据点一定距离(由Schneider算法提供)
• 多段贝塞尔曲线绝不能产生过于尖锐的曲率.检查此标准的一种方法是沿多段贝塞尔曲线滚动具有最小曲率半径的圆,并检查它是否沿其路径接触曲线的所有部分.虽然看起来有更好的方法涉及一阶和二阶导数的叉积

我发现可以创造更好拟合的解决方案或者仅适用于单个贝塞尔曲线(并且省略了如何在多段贝塞尔曲线中找到每个贝塞尔曲线的良好起点和终点的问题)或者不允许最小曲率约束.我认为最小曲率约束是这里的棘手条件.

这是另一个例子(这是手绘而不是100%精确):

让我们假设图1显示了两者,曲率约束(圆必须适合整个曲线)以及任何数据点与曲线的最大距离(恰好是绿色圆的半径).图2中红色路径的成功近似显示为蓝色.该近似值符合曲率条件(圆可以在整个曲线内滚动并在任何地方触摸它)以及距离条件(以绿色显示).图3显示了路径的不同近似值.虽然它符合距离条件但很明显圆圈不再适合曲率.图4显示了一条不可能用给定约束近似的路径,因为它太尖了.该示例应该说明为了正确地近似路径中的一些尖转弯,算法必须选择不属于路径的控制点.图3显示,如果选择沿路径的控制点,则不能再满足曲率约束.此示例还显示算法必须退出某些输入,因为无法使用给定的约束来近似它.

这个问题是否存在解决方案？解决方案不一定要快.如果需要一天时间来处理1000点,那就没问题了.解决方案也不必是最佳的,因为它必须导致最小二乘拟合.

最后,我将用C和Python实现它,但我也可以阅读大多数其他语言.

我需要一种比Bresenham线绘制算法慢一点的算法,但必须更精确.使用'exact'我的意思是:应该打印每个触摸的像素.不多也不少!这意味着使用更粗的线或类似物不是一种选择,因为将涉及太多的像素.此外,我并不需要一个图形框架或类似就像是问 之前,我需要的算法!应用程序实际上不是"图形",它位于像素为"图块" 的地理区域.

对我来说主要的问题是我需要子像素精度,这意味着一条线可以从0.75/0.33开始,而不仅仅是0/0,就像整数值的情况一样.我尝试在过去几个小时内创建一个可行的解决方案,但无法使其正常工作 - 边缘情况太多了.

首先,我认为抗锯齿的版本就像从算法吴应,但它打印像素过多(尤其是起点和终点),并在某些情况下,还惦记着,例如在非常短的线条一些像素.

然后我试着让Bresenham在我用'else if'取代第二个'if'的地方工作,这里指出了它,但它更接近但仍然不存在.然后我尝试将Bresenham从整数移动到浮点精度,这导致无限循环(因为x,y值跳过完成条件if (y1 == y2 && x1 == x2)).

我可以使用天真的线条绘图解决方案,但delta我应该使用哪个？例如,如果我使用0.1,我仍然会错过一些像素并使用较小的值,它可能会花费太长时间(仍然会错过像素).

C/Java/...中的工作解决方案将不胜感激.至少它应该适用于八分之一,但一个完整的解决方案会更好.

更新:我提出了以下想法:使用朴素行光栅化,您可以为每个点计算4个像素候选.然后检查这4个像素,如果该线真正穿过它们.但我不确定线/盒交叉点是否足够快.

我有一组希尔伯特值(从希尔伯特曲线的起点到给定点的长度).

将这些值转换为3D点的最佳方法是什么？原始希尔伯特曲线不是3D,所以我想我必须自己选择我需要的希尔伯特曲线等级.我确实有总曲线长度(即,集合中的最大值).

也许现有的实施？一些库可以让我使用希尔伯特曲线/值？语言并不重要.

我正在为CNC铣床实现驱动程序,而我在实现G代码弧命令时遇到了麻烦.

我已经找到了几个中点圆算法的实现,但它实际上并不是真的可用.

我发现中点圆算法的问题在于它是2D并且同时绘制所有八分圆,而我需要通过3D路径的连续步骤,由起点,终点和中心点给出.

我发现了一个很好的多维等效Bresenham的线绘算法使用浮点运算.绘制圆弧可能存在类似的事情吗？

我可以通过大量的思考和实验来改变这种算法,但是由于绘制弧线并不是一个未解决的问题,而且之前已经制造过数控机床,我想知道是否已经存在一个优雅的解决方案？

我正在使用其中一种提议的算法,但结果非常糟糕.

我实现了wiki算法

在Java中(代码如下).x(0)是points.get(0),y(0)是values[points.get(0)],?是alfa和?是mi.其余部分与wiki伪代码相同.

    public void createSpline(double[] values, ArrayList<Integer> points){
    a = new double[points.size()+1];

    for (int i=0; i <points.size();i++)
    {
        a[i] = values[points.get(i)];

    }

    b = new double[points.size()];
    d = new double[points.size()];
    h = new double[points.size()];

    for (int i=0; i<points.size()-1; i++){
        h[i] = points.get(i+1) - points.get(i);
    }

    alfa = new double[points.size()];

    for (int i=1; i <points.size()-1; i++){
        alfa[i] = (double)3 / h[i] * (a[i+1] …

确实存在所谓的超操作序列。它的工作原理就像你a*b=a+a+a+a...+a用许多a重复b次数的加法来构造乘法。然后a^b = a*a*a*a*...*a进行a多次重复乘法的幂运算b。然后，出现tetration，表示为幂的塔，就像a^^b == a^a^a^...^a，重复b次数。

我对如何为浮点数和复数编写此函数感兴趣？

我已经在 glsl 中编写了乘法和幂函数：

// complex multiplication:
vec2 cmul(in vec2 a, in vec2 b) {
    return vec2(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);
}

// complex exponent e^a
vec2 cexp(in vec2 a) {
    float ea = exp(a.x);
    float vl = a.y;
    return ea * vec2( cos(vl), sin(vl) );
}

// complex natural logarithm ln(a)
vec2 cln(in vec2 a) {
    float …