有限度的三位一体？

Question

我需要帮助解决一个问题，这个问题出现在我的一个小型机器人实验中，基本思想是，每个小机器人都有能力逼近距离，从它们自己到一个物体，不管我得到的近似是多么的粗糙，我希望能计算出更精确的东西。

所以：

输入：：顶点(v_1, v_2, ... v_n)的列表，顶点v_* (机器人)

输出：未知顶点v_* (对象)的坐标

每个顶点v_1到v_n的坐标都是众所周知的(通过调用顶点上的getX()和getY()来提供)，并且可以通过调用获得v_*的近似范围；getApproximateDistance(v_*)，函数getApproximateDistance()返回两个变量，即：minDistance和maxDistance。-实际距离在这两个变量之间。

因此，为了获得v_*的坐标，我一直在做的是使用三边法，但是我似乎找不到一个公式来进行带极限(下限和上限)的三边运算，所以这就是我真正想要的(数学不够好，我自己也找不出来)。

注:三角剖分是替代的方法吗？

注:我可能想知道一个方法，性能/准确性权衡。

数据的一个例子：

[Vertex . `getX()` . `getY()` . `minDistance` . `maxDistance`]
[`v_1`  .  2       .  2       .  0.5          .  1  ]
[`v_2`  .  1       .  2       .  0.3          .  1  ]
[`v_3`  .  1.5     .  1       .  0.3          .  0.5]

显示数据的图片：http://img52.imageshack.us/img52/6414/unavngivetcb.png

很明显，v_1的近似可能比[0.5; 1]更好，因为上面的数据创建的图形是环形的小切口(受v_3限制)，但是我如何计算它，并可能在该图形中找到这个近似(这个数字可能是凹的)？

这是否更适合MathOverflow？

Answer 1

我会采取一种简单的离散方法。一个环空的隐式公式是平凡的，如果多个环的数目较高，则可以用基于扫描线的方法有效地计算多个环的相交。

为了获得高精度的快速计算，一种选择可能是使用多分辨率方法(即首先从低分辨率开始，然后在高分辨率仅在接近有效点的样本中重新计算。

我编写的一个小python玩具可以在大约0.5秒内生成一个400×400像素的相交区域图像(如果用C完成，这种计算将得到100倍的加速)。

​

​

# x, y, r0, r1
data = [(2.0, 2.0, 0.5, 1.0),
        (1.0, 2.0, 0.3, 1.0),
        (1.5, 1.0, 0.3, 0.5)]

x0 = max(x - r1 for x, y, r0, r1 in data)
y0 = max(y - r1 for x, y, r0, r1 in data)
x1 = min(x + r1 for x, y, r0, r1 in data)
y1 = min(y + r1 for x, y, r0, r1 in data)

def hit(x, y):
    for cx, cy, r0, r1 in data:
        if not (r0**2 <= ((x - cx)**2 + (y - cy)**2) <= r1**2):
            return False
    return True

res = 400
step = 16
white = chr(255)
grey = chr(192)
black = chr(0)
img = [black] * (res * res)

# Low-res pass
cells = {}
for i in xrange(0, res, step):
    y = y0 + i * (y1 - y0) / res
    for j in xrange(0, res, step):
        x = x0 + j * (x1 - x0) / res
        if hit(x, y):
            for h in xrange(-step*2, step*3, step):
                for v in xrange(-step*2, step*3, step):
                    cells[(i+v, j+h)] = True

# High-res pass
for i in xrange(0, res, step):
    for j in xrange(0, res, step):
        if cells.get((i, j), False):
            img[i * res + j] = grey
            img[(i + step - 1) * res + j] = grey
            img[(i + step - 1) * res + (j + step - 1)] = grey
            img[i * res + (j + step - 1)] = grey
            for v in xrange(step):
                y = y0 + (i + v) * (y1 - y0) / res
                for h in xrange(step):
                    x = x0 + (j + h) * (x1 - x0) / res
                    if hit(x, y):
                        img[(i + v)*res + (j + h)] = white

open("result.pgm", "wb").write(("P5\n%i %i 255\n" % (res, res)) +
                               "".join(img))

另一个有趣的选择可能是使用GPU，如果可用的话。从一幅白色的图片开始，用黑色绘制，每个圆环的外部将在最后以白色离开交叉口区域。

例如，对于Python/Qt，执行此计算的代码很简单：

img = QImage(res, res, QImage.Format_RGB32)
dc = QPainter(img)
dc.fillRect(0, 0, res, res, QBrush(QColor(255, 255, 255)))
dc.setPen(Qt.NoPen)
dc.setBrush(QBrush(QColor(0, 0, 0)))
for x, y, r0, r1 in data:
    xa1 = (x - r1 - x0) * res / (x1 - x0)
    xb1 = (x + r1 - x0) * res / (x1 - x0)
    ya1 = (y - r1 - y0) * res / (y1 - y0)
    yb1 = (y + r1 - y0) * res / (y1 - y0)
    xa0 = (x - r0 - x0) * res / (x1 - x0)
    xb0 = (x + r0 - x0) * res / (x1 - x0)
    ya0 = (y - r0 - y0) * res / (y1 - y0)
    yb0 = (y + r0 - y0) * res / (y1 - y0)
    p = QPainterPath()
    p.addEllipse(QRectF(xa0, ya0, xb0-xa0, yb0-ya0))
    p.addEllipse(QRectF(xa1, ya1, xb1-xa1, yb1-ya1))
    p.addRect(QRectF(0, 0, res, res))
    dc.drawPath(p)

而800x800分辨率图像的计算部分大约需要8ms (我不确定它是不是硬件加速了)。

如果只计算交集的重心，那么根本就没有内存分配。例如，“蛮力”方法只是C的几行代码。

typedef struct TReading {
    double x, y, r0, r1;
} Reading;

int hit(double xx, double yy,
        Reading *readings, int num_readings)
{
    while (num_readings--)
    {
        double dx = xx - readings->x;
        double dy = yy - readings->y;
        double d2 = dx*dx + dy*dy;
        if (d2 < readings->r0 * readings->r0) return 0;
        if (d2 > readings->r1 * readings->r1) return 0;
        readings++;
    }
    return 1;
}

int computeLocation(Reading *readings, int num_readings,
                    int resolution,
                    double *result_x, double *result_y)
{
    // Compute bounding box of interesting zone
    double x0 = -1E20, y0 = -1E20, x1 = 1E20, y1 = 1E20;
    for (int i=0; i<num_readings; i++)
    {
        if (readings[i].x - readings[i].r1 > x0)
          x0 = readings[i].x - readings[i].r1;
        if (readings[i].y - readings[i].r1 > y0)
          y0 = readings[i].y - readings[i].r1;
        if (readings[i].x + readings[i].r1 < x1)
          x1 = readings[i].x + readings[i].r1;
        if (readings[i].y + readings[i].r1 < y1)
          y1 = readings[i].y + readings[i].r1;
    }

    // Scan processing
    double ax = 0, ay = 0;
    int total = 0;
    for (int i=0; i<=resolution; i++)
    {
        double yy = y0 + i * (y1 - y0) / resolution;
        for (int j=0; j<=resolution; j++)
        {
            double xx = x0 + j * (x1 - x0) / resolution;
            if (hit(xx, yy, readings, num_readings))
            {
                ax += xx; ay += yy; total += 1;
            }
        }
    }
    if (total)
    {
        *result_x = ax / total;
        *result_y = ay / total;
    }
    return total;
}

在我的电脑上，可以用resolution = 100在0.08ms (x=1.50000，y=1.383250)或resolution = 400在1.3ms (x=1.500000，y=1.383308)计算重心。当然，一个双步加速比可以实现，即使是在重心纯版本。

Answer 2

我会从"max/min“切换到尽量减少错误函数。这将让您看到在Finding a point that best fits the intersection of n spheres中讨论的问题，这个问题更容易处理，而不是交叉一系列复杂的形状。(如果一个机器人的传感器搞砸了，并给出了一个不可能的值，那该怎么办呢？这种变化通常仍然会给出一个合理的答案。)

Answer 3

不确定你的情况，但在一个典型的机器人应用程序中，你将定期读取传感器并对数据进行处理。如果是这样的话，您将尝试根据噪声数据来估计位置，这是一个常见的问题。作为一种简单(不那么严格)的方法，您可以将现有的位置调整到或远离每个已知的点。取测量到的距离减去目标的当前距离，将该增量(误差)乘以0到1之间的某个值，然后将估计的位置移向目标。对每个目标重复。然后，每次你得到一组新的测量数据时，重复一遍。乘法器会产生类似于低通滤波器的效果，较小的值会给你一个更稳定的位置估计，同时对运动的响应也会更慢。对于距离，使用最小和最大的平均值。如果你能对一个目标的范围设置更严格的限制，你就可以将这个目标的乘数增加到接近1。

这当然是一个粗略的头寸估计。数学方面的人可能更严格，但也更复杂。解决方案绝对不是任何与相交区域和几何形状的工作。