代码之家 › 专栏 › 技术社区 › Drew Noakes

测试多边形是简单的还是复杂的

computational-geometry polygon geometry algorithm

Drew Noakes · 技术社区 · 15 年前

example complex polygon image

有没有比检查每一对时间复杂度为O(N ^2个 )?

3 回复 | 直到 12 年前

Reed Copsey 15 年前

有一些扫描方法可以比暴力方法更快地确定这一点。此外,它们还可用于将非简单多边形分解为多个简单多边形。

Amit Prakash 11 年前

见 Bentley Ottmann Algorithm 对于这种基于扫描的O((N+I)logn)方法。其中N是线段数,I是交点数。

Chao Xu 11 年前

实际上,这可以在线性时间内使用Chazelle的三角剖分算法。它要么对多边形进行三角剖分,要么发现多边形并不简单。

推荐文章

user20003920 · 如何对x y数据进行降采样?

2 年前

John Marston · 如何创建三个角度相等的三维矢量?

2 年前

Swike · 如何在matplotlib中为重叠的圆上色?

2 年前

For · 如何使用c++中的=运算符分别分配复变量的实部和虚部?

2 年前

ryanx · html中的长lat标识符

3 年前

hosoo · 如何在python中找到平面方程

3 年前

Georgia Nissen · 检查两个列表的圆重叠

3 年前

user3384674 · 求一系列圆柱体/圆锥体分段上两点之间最短连接的算法&求连接上的特定点

3 年前

sixtytrees · 在numpy数组中填充圆内的1,其他地方填充零

3 年前

wzl · 如何使用POI绘制圆(而不是椭圆)

3 年前