5

我只是想知道是否有任何简单/有效的方法来检查正方形是否落在三角形内。或至少一个角落入内部或一些重叠。例如考虑下图，我应该可以看出 3 个方块落在里面。即正方形1明显在里面，正方形2的一个角在里面，3重叠。 示例图

4

6 回答 6

4

将您的三角形视为三个向量，全部按固定的旋转顺序：A->B、B->C 和 C->A

现在，考虑对于每个三角形顶点，从该顶点到每个方形顶点都有四个向量。您计算每个三角形边矢量和每个三角形-正方形矢量（总共 12 个）之间的叉积。如果叉积都是相同的符号（或零），则您的正方形在里面。

从概念上讲，您正在尝试确定正方形顶点是在线条的左侧还是右侧。你实际上并不关心它是左还是右，或者你是顺时针还是逆时针......只是正方形顶点在所有三角形向量的同一侧。

于 2012-09-15T22:42:28.160 回答
2

我正在查看这个不错的教程。它解释了如何使用各种技术测试一个点是否在三角形内。当一个方角落在里面时，它似乎会有所帮助。

而且我喜欢重心技术，在这里我为 matlab 重新实现了它：

function d = isinside(p,a,b,c)

    % Test if a point p(x,y) is inside a triangle
    % with vertices a(x,y), b(x,y) and c(x,y)

    v0 = c - a;
    v1 = b - a;
    v2 = p - a;

    A = [dot(v0,v0) dot(v1,v0);dot(v0,v1) dot(v1,v1)];
    b = [dot(v2,v0); dot(v2,v1)];

    x  = A\b;

    % Check if point is in triangle
    if (x(1) > 0) && (x(2) > 0) && (sum(x) < 1)
        d = true;
    else
        d = false;
    end

然后我会测试正方形的每个顶点，如果其中一个落在里面，我会返回。相当多的计算，但值得一试。

对于重叠，我会测试交叉点，正如在这个线程中讨论的那样，对于三角形和正方形的线的每个组合。

于 2012-09-15T22:34:37.143 回答
1

新手来了 想到的一个想法如下。这可能效率不高，但相当简单。

1) 计算正方形的 4 个角。

2）选择每个角/点将“行走”的方向。基本上为该点选择一个矢量方向。

3）让这些点沿着向量“走”，看看它是否对三角形的边界感兴趣。

4）如果一个点的行走向量相交奇数次，这意味着它在里面。如果它相交偶数次，则意味着它在外面。记住 0 是偶数。

5）如果你真的沿着三角形的边缘走，必须做出特殊情况。在大多数情况下，这可以通过选择不同的方向来避免。

于 2012-09-15T20:40:10.680 回答
1

也许这可以提供一个想法。

在此处输入图像描述

创建具有 0-1 值的三角形图像（这是困难的部分）；然后对每个正方形，创建它的 0-1 图像，这很简单；添加两个图像，并计算不同三角形或正方形坐标处的值。您甚至可以计算重叠区域的面积。

于 2012-09-16T15:56:26.613 回答
0

您实际上要做的是确定正方形是否可以与三角形线性分离，即您是否有一条线将两个对象分开。如果存在这样的线，则它们不相交。有几种算法可以测试线性可分性。好处是它们是通用的，因此它可以与其他多边形一起使用。不利的一面是，由于它们的普遍性，它们可能不会使用问题的特定特征来简化解决方案。

于 2012-09-17T09:23:55.427 回答
0

由于您询问了matlab，并且因为其他答案解释了直接方法，所以我将提到一些可用的解决方案。您可能想看看polyxpoly（如果您有 Mapping Toolbox）。它可以处理更一般的情况。否则，文件交换上有很多贡献，请参见Curve Intersect 2。另一方面， Polygon_Intersection返回重叠区域，而不仅仅是交点。

于 2012-09-20T11:54:18.883 回答