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

有没有图形学大佬,球指点

  •  
  •   yirius · 2022-10-11 21:41:11 +08:00 · 1508 次点击
    这是一个创建于 533 天前的主题,其中的信息可能已经有所发展或是发生改变。

    现在有一个坐标围成的 Polygon ,例子坐标如[[0,0], [0,10], [15,10], [15,20], [20,20], [20,5], [5,5]],现在想要把这个图形切割成三块 [矩形] ,如[[0,0], [0,10], [5,10], [5,0]]就是其中一块,思索了三天,没有任何头绪。用二维图像布尔计算也无法直接提取出来其中的矩形,有大佬有思路吗?

    9 条回复    2022-10-12 03:26:55 +08:00
    xing7673
        1
    xing7673  
       2022-10-12 01:20:19 +08:00 via iPhone
    实在不行就暴力搜索,对每个节点都 90 度延长线
    Xs0ul
        2
    Xs0ul  
       2022-10-12 01:42:38 +08:00
    1. 切割的块数 n=3 是确定的吗?
    2. 输入确保有解吗?

    1 、2 的回答都是 yes 的情况下,也许可以穷举出所有可能的形状。或者把问题简化成,先切掉一个矩形,剩下的图形能不能分割成俩矩形
    also24
        3
    also24  
       2022-10-12 01:55:28 +08:00
    我没太理解题目,你是说这个形状,能够被切割成三块 矩形 么?

    而且黄色的还是其中一块?

    Xs0ul
        4
    Xs0ul  
       2022-10-12 02:03:12 +08:00
    @also24 #3 看起来应该是描述里漏了个 [5,0] 的点
    also24
        5
    also24  
       2022-10-12 02:11:03 +08:00
    @Xs0ul #4
    哦哦,我也有错,我把 [5,5] 看成 [5,0] 了,这样就合理多了

    bluebirdv2
        6
    bluebirdv2  
       2022-10-12 02:11:33 +08:00
    三个矩形要求覆盖, 只有八个自由度. 首先搜索两条边, 分别作为两个矩形的一条边.
    由于覆盖要求确定两个矩形就可以了, 剩下的矩形直接用其他两个的边.
    确定两个矩形 1 条边后, 只需要确定这两个 x 偏移. 根据覆盖要求, 只需要写出方程. 要求这两条边, 相互平行是矩形.
    documentzhangx66
        7
    documentzhangx66  
       2022-10-12 03:01:49 +08:00
    这还不简单,以 5 楼的形状为例,直接让每条边,在限制区域内,向两端延伸,必然能得到切点的坐标。

    被切成的小块,能组成好几种 3 个矩形。
    ynyounuo
        8
    ynyounuo  
       2022-10-12 03:26:44 +08:00
    搜索 rectangulation algorithm 有挺多线程的例子
    比如: https://www.cise.ufl.edu/~sahni/papers/part.pdf
    ynyounuo
        9
    ynyounuo  
       2022-10-12 03:26:55 +08:00
    现成*
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3507 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 35ms · UTC 11:04 · PVG 19:04 · LAX 04:04 · JFK 07:04
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.