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

平面内四个点,怎样保证能构建四角面?

  •  
  •   zeronofreya · 69 天前 · 577 次点击
    这是一个创建于 69 天前的主题,其中的信息可能已经有所发展或是发生改变。

    比如

    verts = [(x0,y0),(x1,y1),(x2,y2),(x3,y3)]
    

    怎样保证能创建这样的面

    image.png

    而不是这样

    image.png

    要求这四个点坐标不变,最小限度修改前 3 个点的下标(顺序),逆时针,否则面法线就会朝内,最后一个点不能动? 有什么好办法吗?

    6 条回复    2021-10-23 16:02:53 +08:00
    vance123
        1
    vance123   69 天前 via Android
    以最左下方的点为原点,算出三个向量和 y 轴正向的夹角,然后排序
    vance123
        2
    vance123   69 天前 via Android
    不过只有既然四个点,枚举然后像你说的那样算法线方向也可以
    MoYi123
        4
    MoYi123   68 天前
    https://oi-wiki.org/geometry/convex-hull/
    不是太明白你最后一句话是什么意思
    看看这个算法能用吗?
    XiXiLocked
        5
    XiXiLocked   68 天前
    比叉乘,(p1-p4)x(p2-p4) ,(p3-p4)x(p2-p4) ,轮换 123 。3 次里会出现一次一正一负,用那次的下标绕 1234 就不会重叠。
    necomancer
        6
    necomancer   38 天前
    from scipy.spatial import ConvexHull
    hull = ConvexHull(verts) # 你的例子里 points = (4,2) array ,一般来说数组形状是(点数,维度)
    剩下的看看 hull 的 vertices 就行,这个是寻找平面最大凸多边形算法,详情查书。

    当然,如果你的 4 个点里有一个藏在内部了,这个算法返回的是三角形。比如你的 4 个点这么排列,那么返回的是外面的三角形。
    *
    ----*----*
    *
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1348 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 17:55 · PVG 01:55 · LAX 09:55 · JFK 12:55
    ♥ Do have faith in what you're doing.