gpt4 book ai didi

algorithm - 具有自相交的多边形的分解

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:53:02 25 4
gpt4 key购买 nike

如何将自相交的多边形分解为简单多边形的集合?

输入多边形 P = {p1, ... pn} 由一组 n 个顶点以逆时针方向给出。我想对一组 m 个多边形 P1, ..., Pm 进行分解。

enter image description here

简单地沿着路段从路口走到下一个路段不会带来任何影响;有 2 个线段,起点相同,用交点表示。

可能,某些字典排序的边缘可能有助于...

最佳答案

计算所有交点,创建新节点并在交点处划分边,为每个节点创建相邻边列表。

从某个点开始。使用当前顶点的最逆时针边(相对于最后一条边)行走。将遍历的边添加到多边形并删除它们(或标记)。当您返回同一顶点时,关闭多边形。

从第一个仍然有边的顶点开始重复。

关于algorithm - 具有自相交的多边形的分解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53884696/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com