algorithm - 多边形算法

Question

我正在尝试编写一种通用算法，该算法可以从遵循某些已知路径(绿线)的圆(红线)扫过的区域中找到多边形，并且当圆进一步向下移动时，圆会变大已知的路径。基本上，有人能给我指出解决这个问题的方向吗？我似乎无法确定哪些切点是路径上任何点(以及圆)的多边形的一部分。

感谢任何帮助。

Answer 1

嗯，最简单的方法是通过小段来近似您的路径，在这些小段上您的路径是线性的，并且您的圆是线性增长的。

您的线段和角度可能会很小，但为了举例，让我们采用更大(且更明显)的角度。

浏览几何图形

多边形边缘的最佳直线是两个圆的切线。请注意，并不总是靠近由圆和路径正交线之间的交点定义的线，特别是在生长速度较强的情况下。请参见下图，其中 (AB) 是路径，我们需要 (OE) 和 (OF) 线，但不需要 (MN) 线:

第一步是识别点 O。它是唯一定义 homothetic transformation 的点。两个圆之间，比例为正。

因此比率 = OA/OB = (半径 C)/(半径 C') 且 O = A + AB/(1-比率)

现在让 u 为从 O 到 A 标准化的向量，而 v 为与 u 正交的向量(让我们将其代入从A到M的方向)。

让我们将从 O 到 E 的归一化向量称为 a，并将 beta 称为角度 EOA。然后，由于 (OE) 和 (AE) 垂直，因此 sin(beta) = (半径 C)/OA。我们还有标量积 a.u = cos(beta)，并且由于 a 的范数为 1，因此 a = u * cos(beta) + v * sin (测试版)

然后很容易得到b从O到F归一化的向量，b = u * cos(beta) - v * sin(beta)

由于 beta 是一个小于 90° 的角度(否则圆的增长速度会比向前快得多，以至于第二个圆完全包含第一个圆)，我们知道 cos(beta) > 0.

伪代码解决方案

对于第一个和最后一个圆，您可以做一些更接近它们的操作 - 为了简单起见，我将使用我正在构建的线与与圆正交的圆的切线之间的交点第一条(或最后一条)路径，如本文第一张图所示。

沿着路径，您可以通过缩小线段来使多边形任意接近真实的扫描区域。

此外，我假设您有一个函数 find_intersection，给定两条线的两个参数方程，该函数返回它们之间的交点。首先，它使得查看它们是否平行(它们不应该平行)变得很简单，并且它可以轻松地表示垂直线。

w = 1; // width of the first circle
C = {x : 0, y : 0}; // first circle center

while( (new_C, new_w) = next_step )
{
    // the vector (seg_x, seg_y) is directing the segment
    seg = new_C - C;
    norm_seg =  sqrt( seg.x * seg.x + seg.y * seg.y );

    // the vector (ortho_x, ortho_y) is orthogonal to the segment, with same norm
    ortho = { x = -seg.y, y = seg.x };

    // apply the formulas we devised : get ratio-1
    fact = new_w / w - 1;

    O = new_C - seg / fact;

    sin_beta = w * fact / norm_seg;
    cos_beta = sqrt(1 - sin_beta * sin_beta);

    // here you know the two lines, parametric equations are O+t*a and O+t*b
    a = cos_beta * seg + sin_beta * ortho;
    b = cos_beta * seg - sin_beta * ortho;

    if( first iteration )
    {
        // initialize both "old lines" to a line perpendicular to the first segment
        // that passes through the opposite side of the circle
        old_a =  ortho;
        old_b = -ortho;
        old_O = C - seg * (w / norm_seg);
    }

    P = find_intersection(old_O, old_a, O, a);
    // add P to polygon construction clockwise

    Q = find_intersection(old_O, old_b, O, b);
    // add Q to polygon construction clockwise

    old_a = a;
    old_b = b;
    old_O = O;
    w = new_w;
    C = new_C;
}

// Similarly, finish with line orthogonal to last direction, that is tangent to last circle
O = C + seg * (w / norm_seg);
a =  ortho;
b = -ortho;

P = find_intersection(old_O, old_a, O, a);
// add P to polygon construction clockwise

Q = find_intersection(old_O, old_b, O, b);
    // add Q to polygon construction clockwise