N个矩形的交点

N个矩形的交点,第1张

N个矩形的交点

观察1:给定多边形A和矩形B,可以通过与对应于B的每个边的半平面的4个相交来计算相交A∩B。

观察2:从凸多边形上切一个半平面会得到一个凸多边形。第一个矩形是凸多边形。此 *** 作最多增加每1个顶点的数量。

观察3:凸多边形的顶点到直线的符号距离是单峰函数。

这是算法的草图:

以CCW顺序将当前部分交集D保持在平衡的二叉树中。

切割由直线L定义的半平面时,找到D中与L相交的两个边。这可以通过对数时间,通过一些巧妙的二元或三元搜索,利用到L的有符号距离的单峰性来完成。我不完全记得。)从D移除L一侧的所有顶点,并将交点插入D。

对所有矩形的所有边L重复。



欢迎分享,转载请注明来源:内存溢出

原文地址: https://outofmemory.cn/zaji/5643359.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-16
下一篇 2022-12-16

发表评论

登录后才能评论

评论列表(0条)

保存