V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xzpjerry731
V2EX  ›  算法

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

  •  
  •   xzpjerry731 · 2017-05-26 05:41:00 +08:00 · 4090 次点击
    这是一个创建于 2743 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Imgur

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

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

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

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

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

    第 1 条附言  ·  2017-05-26 07:10:36 +08:00
    补充下条件,边的走位都是绕着网格走,每步固定是一个单位。
    13 条回复    2017-05-26 11:08:12 +08:00
    geelaw
        1
    geelaw  
       2017-05-26 05:52:11 +08:00   ❤️ 1
    如果这些点按照绕行顺序排列,你可以随便选一个位置,让它和每对按顺序相邻的点组成三角形,算出每个三角形的面积再加起来。

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

    平行四边形的面积可以用行列式算出来。
    shuding
        2
    shuding  
       2017-05-26 06:47:59 +08:00   ❤️ 1
    每两个相邻点与 x 轴投影围成梯形的有向面积总和:
    CoX
        3
    CoX  
       2017-05-26 07:34:53 +08:00 via iPhone
    感觉做减法容易一些
    xzpjerry731
        4
    xzpjerry731  
    OP
       2017-05-26 08:02:57 +08:00
    @geelaw #1 想了一下,不知道我的理解对不对:找边界上任意一个点,然后求 它和随后按顺序的两个能组成三角形的点组成的三角形的 面积之和。
    感觉怪怪的 T_T

    @shuding #2 感觉缺了什么,比如(3,1) -> (4, 1) 这两个点,投影过去算面积的话不是多算了吗?
    xzpjerry731
        5
    xzpjerry731  
    OP
       2017-05-26 08:03:57 +08:00
    @CoX #3 我一开始就这么想的,但是没有发现可行的判断条件确定可以减的部分
    noqwerty
        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
    imn1
        7
    imn1  
       2017-05-26 08:25:56 +08:00   ❤️ 1
    记忆中有公式的,好象是行列式,忘了
    jmc891205
        8
    jmc891205  
       2017-05-26 08:34:49 +08:00   ❤️ 1
    如果行数或列数比较小的话 就按行或列切成一个个小的矩形之后再算
    abcdabcd987
        9
    abcdabcd987  
       2017-05-26 09:08:07 +08:00   ❤️ 1
    不一定是格点也很容易算。首先在坐标系上任意取一个点,然后跟封闭图形的每个顶点都做向量,然后把这些向量极角排序一下,然后相邻两个向量求叉积,绕一圈把叉积( x1y2-x2y1 )加起来,最后再除以二就行了。

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

    以前学计算几何的时候觉得这个博客还蛮好的: http://www.csie.ntnu.edu.tw/~u91029/Polygon.html 这个页面里面有你要的多边形面积。
    xzpjerry731
        10
    xzpjerry731  
    OP
       2017-05-26 10:02:22 +08:00
    @abcdabcd987 #9 谢了,我先补下几何。
    xzpjerry731
        11
    xzpjerry731  
    OP
       2017-05-26 10:14:50 +08:00
    懂了 原来我和答案只差一点
    xzpjerry731
        12
    xzpjerry731  
    OP
       2017-05-26 10:40:47 +08:00
    @noqwerty #6 感觉你的算法思路清奇啊,是有窍门吗?感觉一对一对叉乘还是慢了点

    总结:感觉献丑了 = =,我现在才想起高数 2 有教过
    noqwerty
        13
    noqwerty  
       2017-05-26 11:08:12 +08:00   ❤️ 1
    @xzpjerry731 #12 感觉这么平整的图形,你可以看成是几条 y=n 的积分,最后再求和(我也就是个数学渣……)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5773 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 06:32 · PVG 14:32 · LAX 22:32 · JFK 01:32
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.