如果知道边界点的信息，如何求封闭区域的面积？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2737 天前的主题，其中的信息可能已经有所发展或是发生改变。

Imgur

已知这些边界一定构成封闭区域（会回到原点）。

信息包括点和点之间方向向量，点的坐标。

画出图来很容易解决，但是不知道怎样写成程序，囧。

希望 dalao 在喝茶刷帖之余看到本帖能给予小生一些启发，先在此谢过了：）

dalao 请轻喷，小生刚开始刷题 = =

第 1 条附言 · 2017-05-26 07:10:36 +08:00

补充下条件，边的走位都是绕着网格走，每步固定是一个单位。

dalao

小生

边界

包括点

13 条回复 • 2017-05-26 11:08:12 +08:00

geelaw

2017-05-26 05:52:11 +08:00

如果这些点按照绕行顺序排列，你可以随便选一个位置，让它和每对按顺序相邻的点组成三角形，算出每个三角形的面积再加起来。

三角形的面积是平行四边形的一半。

平行四边形的面积可以用行列式算出来。

shuding

2017-05-26 06:47:59 +08:00

每两个相邻点与 x 轴投影围成梯形的有向面积总和：

CoX

2017-05-26 07:34:53 +08:00 via iPhone

感觉做减法容易一些

xzpjerry731

2017-05-26 08:02:57 +08:00

@geelaw #1 想了一下，不知道我的理解对不对：找边界上任意一个点，然后求它和随后按顺序的两个能组成三角形的点组成的三角形的面积之和。
感觉怪怪的 T_T

@shuding #2 感觉缺了什么，比如(3,1) -> (4, 1) 这两个点，投影过去算面积的话不是多算了吗？

xzpjerry731

2017-05-26 08:03:57 +08:00

@CoX #3 我一开始就这么想的，但是没有发现可行的判断条件确定可以减的部分

noqwerty

2017-05-26 08:22:09 +08:00 via iPhone

跟#2 的意思类似，只需要计算投影面积有向和绝对值就可以。比如你这个图从上到下是：

丨(-1)*5 + (-1)*4 + (-3)*3 + 0*2 + 3*1 丨 = 15

imn1

2017-05-26 08:25:56 +08:00

记忆中有公式的，好象是行列式，忘了

jmc891205

2017-05-26 08:34:49 +08:00

如果行数或列数比较小的话就按行或列切成一个个小的矩形之后再算

abcdabcd987

2017-05-26 09:08:07 +08:00

不一定是格点也很容易算。首先在坐标系上任意取一个点，然后跟封闭图形的每个顶点都做向量，然后把这些向量极角排序一下，然后相邻两个向量求叉积，绕一圈把叉积（ x1y2-x2y1 ）加起来，最后再除以二就行了。

叉积的结果是以两个向量构成的平行四边形的有向面积，可正可负，像上面绕一圈的话，有向面积多还少补，算出来的就是封闭图形的面积了。

以前学计算几何的时候觉得这个博客还蛮好的： http://www.csie.ntnu.edu.tw/~u91029/Polygon.html 这个页面里面有你要的多边形面积。

xzpjerry731

2017-05-26 10:02:22 +08:00

@abcdabcd987 #9 谢了，我先补下几何。

xzpjerry731

2017-05-26 10:14:50 +08:00

懂了原来我和答案只差一点

xzpjerry731

2017-05-26 10:40:47 +08:00

@noqwerty #6 感觉你的算法思路清奇啊，是有窍门吗？感觉一对一对叉乘还是慢了点

总结：感觉献丑了 = =，我现在才想起高数 2 有教过

noqwerty

2017-05-26 11:08:12 +08:00

@xzpjerry731 #12 感觉这么平整的图形，你可以看成是几条 y=n 的积分，最后再求和（我也就是个数学渣……）