已知这些边界一定构成封闭区域(会回到原点)。
信息包括点和点之间方向向量,点的坐标。
画出图来很容易解决,但是不知道怎样写成程序,囧。
希望 dalao 在喝茶刷帖之余看到本帖能给予小生一些启发,先在此谢过了 :)
dalao 请轻喷,小生刚开始刷题 = =
1
geelaw 2017-05-26 05:52:11 +08:00 1
如果这些点按照绕行顺序排列,你可以随便选一个位置,让它和每对按顺序相邻的点组成三角形,算出每个三角形的面积再加起来。
三角形的面积是平行四边形的一半。 平行四边形的面积可以用行列式算出来。 |
2
shuding 2017-05-26 06:47:59 +08:00 1
|
3
CoX 2017-05-26 07:34:53 +08:00 via iPhone
感觉做减法容易一些
|
4
xzpjerry731 OP |
5
xzpjerry731 OP @CoX #3 我一开始就这么想的,但是没有发现可行的判断条件确定可以减的部分
|
6
noqwerty 2017-05-26 08:22:09 +08:00 via iPhone 1
跟#2 的意思类似,只需要计算投影面积有向和绝对值就可以。比如你这个图从上到下是:
丨(-1)*5 + (-1)*4 + (-3)*3 + 0*2 + 3*1 丨 = 15 |
7
imn1 2017-05-26 08:25:56 +08:00 1
记忆中有公式的,好象是行列式,忘了
|
8
jmc891205 2017-05-26 08:34:49 +08:00 1
如果行数或列数比较小的话 就按行或列切成一个个小的矩形之后再算
|
9
abcdabcd987 2017-05-26 09:08:07 +08:00 1
不一定是格点也很容易算。首先在坐标系上任意取一个点,然后跟封闭图形的每个顶点都做向量,然后把这些向量极角排序一下,然后相邻两个向量求叉积,绕一圈把叉积( x1y2-x2y1 )加起来,最后再除以二就行了。
叉积的结果是以两个向量构成的平行四边形的有向面积,可正可负,像上面绕一圈的话,有向面积多还少补,算出来的就是封闭图形的面积了。 以前学计算几何的时候觉得这个博客还蛮好的: http://www.csie.ntnu.edu.tw/~u91029/Polygon.html 这个页面里面有你要的多边形面积。 |
10
xzpjerry731 OP @abcdabcd987 #9 谢了,我先补下几何。
|
11
xzpjerry731 OP 懂了 原来我和答案只差一点
|
12
xzpjerry731 OP |
13
noqwerty 2017-05-26 11:08:12 +08:00 1
@xzpjerry731 #12 感觉这么平整的图形,你可以看成是几条 y=n 的积分,最后再求和(我也就是个数学渣……)
|