4

我正在做一个项目，Matlab需要找到正方形内两条线之间的区域，[-1,+1]x[-1,+1]相交于一个点(xIntersection,yIntersection)。所以想法是减去两条线并在 [-1, xIntersection] 和 [xIntersection, +1] 之间积分，将结果相加，如果为负，则更改其符号。

有关如何找到两条线的交点的详细信息，请查看此链接。

我正在使用Matlab'sfunction integral()，这里是我的代码片段：

xIntersection = ((x_1 * y_2 - y_1 * x_2) * (x_3 - x_4) - (x_1 - x_2) * (x_3 * y_4 - y_3 * x_4) ) / ((x_1 - x_2) * (y_3 - y_4) - (y_1 - y_2) * (x_3 - x_4));

d = @(x) g(x) - f(x);
result = integral(d, -1, xIntersection) - int( d, xIntersection, 1)
if(result < 0),
    result = result * -1;
end

请注意，我之前在代码中定义过，g(x)但f(x)没有在代码段中报告它。

问题是我很快意识到线条可以在正方形的内部或外部相交，而且它们可以在正方形的任何边上相交，并且可能的组合数量增长得非常快。

IE：

在此处输入图像描述在此处输入图像描述在此处输入图像描述在此处输入图像描述

这只是 4 种情况，但考虑到 f(+1), f(-1), g(+1), g(-1) 可能在区间 [-1,+1] 内，在它之上或之下并且交叉点可能在正方形内部或外部，总数为 3*3*3*3*2 = 162。

显然，在每种情况下，为了获得两条线之间的区域而进行集成的显式函数是不同的，但我不可能想到为每条线编写一个 switch 案例。

有任何想法吗？

4

3 回答 3

3

我认为我对您之前问题的回答在很大程度上仍然适用。

如果要计算以两条线的较小角度和正方形边界为界的区域的面积，则可以忘记交点，并忘记所有不同的情况。

您可以使用以下事实

  • 正方形 S 的面积等于 4

  • 这个积分的值

    A = quadgk(@(x) ...
    abs( max(min(line1(x),+1),-1) - max(min(line2(x),+1),-1) ), -1, +1);

    给你线之间的区域（有时是大角度，有时是小角度）

  • 的值min(A, S-A)是正确答案（总是小角度）。
于 2013-09-12T05:33:40.243 回答
2

假设“线条之间”是指“线条形成的较小角度内”：

用线条l和h, S := [-1,+1]x[-1,+1]和B作为 的边界S。

转换l为l_1 + t*l_2带有l_1和l_2being 向量的形式。对 h 做同样的事情。

  • 如果交点不在内部S，则找到 和 的 4l个h交点B。对它们进行排序，得到一个凸四边形。计算它的面积。
  • 别的：
    • 求交点p，求和的交角 。然后检查： αl_2h_2
      • 如果αin[90°,180°]或αin [270°,360°]，则交换l和h。
      • 如果α > 180°，设置l_2 = −l_2
    • 设置l_1 := h_1 := p。做一次正面t和负面（沿着和从t 向前和向后）： l_2h_2p
      • 查找s_l和s_h的l和h与的交点B。
      • 如果在 的同一边界上B：计算三角形的面积 s_l, s_h,p
      • 如果在 : 的相邻边界上B找到命中边界之间的角c，B然后再次对四个点s_l、进行排序s_h，这样你就得到了一个凸四边形并计算它的面积。pc
      • 如果在相反的边界上，找到匹配的一侧B（您可以通过查看 的方向来做到这一点s_l-p）。使用它的两个角点c_1和c_2，您现在有 5 个点构成一个多边形。对它们进行排序，使多边形凸出并计算其面积。

这仍然是相当多的情况，但我认为没有办法解决这个问题。您还可以通过使用三角形和四边形的多边形公式来稍微简化这一点。

如何对点进行排序以获得凸多边形/四边形：选择其中任何一个作为p_1，然后根据角度对其余点进行排序p_1。

如果你定义一个intersection函数和一个polygon_area点列表，对它们进行排序并返回区域，那么这个算法应该很容易实现。

编辑：帮助解释评论的图片： 在此处输入图像描述

于 2013-09-12T02:43:03.413 回答
1

嘿，谢谢大家的回答，我还想到了一种经验方法来找到线之间的区域，并为了讨论和完整性而想分享它。

如果您在正方形内取大量随机点，则[-1,+1]x[-1,+1]可以将面积测量为落在两条线之间区域内的点的分数。

这是一个小片段和两张图像，以显示使用不同点数获得的经验结果的不同准确性。

minX = -1;
maxX = +1;

errors = 0;
size = 10000;

for j=1:size,

    %random point in [-1,+1]
    T(j,:) = minX + (maxX - minX).*rand(2,1); 

    %equation of the two lines is used to compute the y-value
    y1 = ( ( B(2) - A(2) ) / ( B(1) - A(1) ) ) * (T(j,1) - A(1)) + A(2);
    y2 = (- W(1) / W(2)) * T(j,1) -tresh / W(2);

    if(T(j,2) < y1),
        %point is under line one
        Y1 = -1;
    else
        %point is above line one
        Y1 = +1;
    end

    if(T(j,2) < y2),
        %point is under line two 
        Y2 = -1;
    else
        %point is above line two
        Y2 = +1;
    end

    if(Y1 * Y2 < 0),

        errors = errors + 1;
        scatter(T(j,1),T(j,2),'fill','r')
    else
        scatter(T(j,1),T(j,2),'fill','g')
    end

end

area = (errors / size) / 4;

这里有两张图片，它肯定比@Rody 发布的解决方案花费的时间更长，但正如您所见，您可以使其准确。

  • 点数 = 2000

点数 = 2000

点数 = 10000

点数 = 10000

于 2013-09-12T16:16:02.480 回答