多边形的面积

Question

我需要计算2D多边形的面积（任何形状，任何大小等...） 我只有一个点列表，每个点都包含X和Y。

多边形位于2D块地图中，因此：
但是因为我必须使用块/矩形，所以多边形看起来更像这样：
所以必须计算出这个：
仅当超过50％的块在多边形内或者是该多边形的角/点时（如图像下方的手臂），块才在区域内。

是否可能进行计算？ 而不用获取最小值和最大值，然后检查每个块...
我只找到了一些普通多边形的代码：

public int getArea(List<BlockVector2D> blockPoints)
{
    double result = 0;
    int j = blockPoints.size() - 1;

    for (int i = 0; i < blockPoints.size(); ++i)
    {
        result += (blockPoints.get(j).getBlockX() + blockPoints.get(i).getBlockX()) * (blockPoints.get(j).getBlockZ() - blockPoints.get(i).getBlockZ());
        j = i;
    }
    return (int) Math.abs(result / 2);
}

但我不知道如何使用块点来实现这一点...

对于大小和奇怪的图像以及我的英语表示抱歉。

- user2250333

---

如果一个区块超过50%在多边形内，那么它就被算作在多边形内。但是根据您的示例，显然并不总是这种情况。我猜带有角落的区块总是被包括在内？ - tobias_k

不用道歉，图片虽然有点大但对于我们所有人来说都非常有帮助，可以更好地理解你所做的事情。而且你的英语很好 :) - takendarkk

我同意tobias_k的观点，如果你尝试计算轮廓的积分，这既更容易又更可靠。 - Mohsen Kamrani

也许这可以帮助：对于每个角落块以外的块（无论如何似乎都“在”多边形内），当且仅当其中心在多边形内时，该块超过50％地“在”多边形内。（如果极细而尖的多边形“臂”通过中心，则可能有例外情况，就像右下角几乎是这种情况一样。） - tobias_k

或者，您可以使用像Chazelle Dobkin这样的算法将多边形分割成凸多边形，假设您不必担心自相交。 这里是普林斯顿大学关于该算法的PDF。 - Sam

Answer 1

看看这个算法，它有些复杂，但是可以解释你所需的内容。

http://www.mathopenref.com/coordpolygonarea2.html

- Karimsou

---

我认为这相当简单。否则，使用蒙特卡罗方法。 - VH-NZZ

这个和我的代码一样，10x10的区域只有89个方块而不是100个。(p1 = (1, 1), p2 = (1, 10), p3 = (10,10), p4 = (10, 1))。 - user2250333

我指的是那个页面中的“更复杂的情况”部分。 - Karimsou

Answer 2

我没有完美的解决方案，只有一个想法..（也许很蠢，不保证）：

我明白你需要非常快速地计算它。所以像这样遍历每个点：

area = 0;
foreach(point p : points) {
    area += testIfInsidePolygon(p);
}

“is not an option.”不是一个选项。

我相信这个问题没有解析解，也不会有如你提供的这样好的算法。所以我的想法是：

• 沿着每个多边形顶点遍历，并使用Bresenham线算法(http://en.wikipedia.org/wiki/Bresenhams_line_algorithm)计算特定点是否在多边形的边缘上
• 将点位置存储在2D k-d树(http://en.wikipedia.org/wiki/K-d_tree)中，它非常适合空间划分
• 如果某些点已经存储在k-d树内，则意味着你正在处理像你爱人的右下角点那样的情况
• 使用k-d树查找最高点和最低点
• 从最高坐标到最低坐标遍历，从侧面投射光线，并再次查询k-d树以获取光线<->多边形边缘交点
• 使用交点X坐标之间的差值之和即可计算出面积

需要进行特殊情况的更正是极其可能的 :)

这个算法比遍历所有点的O(n^2)要快得多。不过，你会付出更高的复杂度。

- infi