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

问一个多边形的相关问题

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

    给定数据

    1. 一个点集,每个点形式为(x, y, area),xy是点的坐标,area值后面再说;
    2. 一个多边形,由一系列首尾相连的点组成。 上述点集所有的点都在这个多边形内,且上面点集中所有的点area之和小于这个多边形的面积。

    要求

    1. 根据点集的点生成小多边形,小多边形的面积为点的area值;
    2. 小多边形必须在多边形的范围内;
    3. 小多边形不能相互重叠。

    请问这种问题有没有什么图形分割的相关算法推荐?

    4 条回复    2023-05-26 22:03:07 +08:00
    misdake
        1
    misdake  
       307 天前 via Android   ❤️ 1
    帮你补一条要求就是每个点必须在自己对应的小多边形内部。

    需求有点城市生成的感觉。还没什么思路。
    liplushe
        2
    liplushe  
    OP
       307 天前
    @misdake 感谢补充,确实有这个要求
    soar0712
        3
    soar0712  
       307 天前   ❤️ 1
    具体的算法没有研究过,不过简单想了一下,有两个思路你可以试试是否可行,纯讨论,不一定有效:
    1 、如果对小多边形的边数没有数量要求,或者不要求边数越少越好,可以将整个平面用 x 和 y 轴分割成很多小网格,然后用尝试生成法,从每个点开始扩散,不断蚕食周围的小网格,直到蚕食的区域达到 area 值;
    2 、如果要求小多边形的边数越少越好,那就先计算一下每个点距离大多边形的边的距离,从离边最近的点开始尝试生成小多边形,一开始以三角形尝试,三角形的一条边顶到大多边形的边后就开始扩展另外两条边,直到凑够 area 范围,如果三条边都挨着其他点还凑不够 area ,就继续尝试四边形;按照离大多边形边界的距离,由近及远的尝试生成,最后生成最中心的小多边形。
    liplushe
        4
    liplushe  
    OP
       307 天前
    @soar0712 非常感谢,第一个思路很有用
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3270 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:07 · PVG 22:07 · LAX 07:07 · JFK 10:07
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.