在JavaScript中判断一个点是否在多边形内部

Question

在JavaScript中判断一个点是否在多边形内部

javascriptpolygon

3

我正在使用JavaScript编写程序，目的是判断一个点是否在多边形内部。我使用了射线投射算法来比较点是否在多边形内部。

对于某些情况，该算法可以完美地工作。但是对于某些情况，即使所有点都在多边形内部，它也会显示该点在外部。

!https://www.dropbox.com/s/rpxqnw9re3q6vsi/Screen%20Shot.png?dl=0

标记为A1的区域是父多边形，A2和A3位于父多边形内。以下是我使用的函数来检查点是否在内部。

function isPointInside(point, vs)
{
// ray-casting algorithm based on
var x = point[0], y = point[1];

var inside = false;
for (var i = 0, j = vs.length - 1; i < vs.length; j = i++)
{
    var xi = vs[i][0], yi = vs[i][1];
    var xj = vs[j][0], yj = vs[j][1];
    var intersect = ((yi > y) != (yj > y))&& (x < (xj - xi) * (y - yi) / (yj - yi) + xi);
    if (intersect) inside = !inside;
}

return inside;
};

以下是父多边形和子多边形的点数组。

 A1 Array 
0[0, 0] (2)
1[6096000, 0] (2)
2[6096000, 0] (2)
3[6096000, 6096000] (2) 
4[6096000, 6096000] (2)
5[0, 6096000] (2)
6[0, 6096000] (2)
7[0, 0] (2)
8[0, 0] (2)
9[0, 0] (2)


A2 Array (10)
 0[0, 0] (2)
 1[0, 3048000] (2)
 2[0, 3048000] (2)
 3[1524000, 3048000] (2)
 4[1524000, 3048000] (2)
 5[1524000, 0] (2)
 6[1524000, 0] (2)
 7[0, 0] (2)
 8[0, 0] (2)
 9[0, 0] (2)


A3 Array (10)
 0[4572000, 0] (2)
 1[4572000, 6096000] (2)
 2[4572000, 6096000] (2)
 3[6096000, 6096000] (2)
 4[6096000, 6096000] (2)
 5[6096000, 0] (2)
 6[6096000, 0] (2)
 7[4572000, 0] (2)
 8[4572000, 0] (2)
 9[4572000, 0] (2)

为什么A3的点没有被考虑在内？算法有问题吗？任何帮助都将不胜感激。

- gurmandeep

你的多边形总是矩形吗？ - Kamen Stoykov

不，它可以是任何形状。 - gurmandeep

我知道的算法适用于凸多边形，如果你有一个非凸多边形，你需要将它分割成几个凸多边形。然后对每个多边形的点进行排序并迭代。算法复杂度为n*logn。这是否满足您的需求，您是否希望完全描述它？（这是关于2D而不是3D的） - Kamen Stoykov

如果您能稍微描述一下，那就太好了，我会找到一种方法将多边形分割成几个多边形。 - gurmandeep

谢谢Kamen，那太棒了。 - gurmandeep

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kamen Stoykov · Accepted Answer

让我们从几个实用函数开始。

首先是area(Point, Point, Point)。它以3个点作为参数（顺序非常重要）。第一个和第二个点形成一个向量，如果第三个点在这个向量的左侧，函数返回正值；如果第三个点在右侧，则返回负值；最后，如果第三个点位于向量上，则返回0。

function area(p1 , p2, p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
};

下一个实用函数是sortCMP(Point, Point)，在对每个多边形点进行排序时用作比较器。

function sortCMP(p1, p2) {
    var result_area = area(target, p1 ,p2);
    if(result_area == 0.0) {
        return (sqrtDist(target, p1) - sqrtDist(target, p2) > 0.0)? 1 : -1;
    }
    return (result_area > 0.0)? -1 : 1;
};

让我们考虑您的多边形由从P1到PN的N个点组成，它们存储在名为POINTS的数组中。在先前的函数（sortCMP）中，有一个名为TARGET的变量，它应该是从P1到PN中所有点中具有最低X和Y坐标的点。

下一个函数是sqrdDist，实际上返回两点之间的距离。

function sqrtDist(p1, p2) {
        var dx = p1.x - p2.x;
        var dy = p1.y - p2.y;
        return dx * dx + dy * dy;
};

现在让我们回到数组名称POINTS，其中包含您的多边形中的所有点。我们已经找到了一个具有最低X和Y坐标的点（目标变量）。现在我们必须将其移动到数组中的第一个元素，然后从索引1的元素开始对整个数组进行排序。

数组排序后，我们只需迭代它并检查area（Pi，Pi + 1，T）始终返回正值（或者如果您想放在多边形本身上，则为0）。如果某处区域函数返回负值，则点T始终是您的多边形。点T是您正在测试其是否在多边形内部的点。

正如我在评论中所说，为使此方法有效，您的多边形应为凸多边形。这可以在先前算法的最后一步中检查。因此，当您将所有多边形的点排序时，您可以检查area（Pi，Pi + 1，Pi + 2）是否始终为所有多边形的点返回正值（或0）。如果某处返回负值，则意味着您的多边形不是凸多边形。当它返回负值时，也意味着索引i + 1的点是您必须拆分多边形的点。有关如何拆分它的详细信息，您可能需要在Google中搜索，因为我现在无法记住。

希望这能对你有所帮助。如果你有任何进一步的问题，请随时提出，我会在白天尽力回答你 :)