07 Feb 10 dancing links 的简单介绍及应用

很早以前写的一个文章的初稿。可惜的是底稿找不到了。。。

很多内容都没有修正和添加，不过大体内容差不多，有兴趣的将就着看看吧。

地址如下：

http://gaoyunxiang.com/wp-content/uploads/2010/02/Dancing_Links.pdf

07 Feb 10 圆的面积并

摘要

设想生活中往往需要知道很多图形的面积,但是当图形有多个的情况下,我们怎么知道这些图形的面积的并集呢? 现实中的图形往往可以转化成一些多边形和圆的组合. 本文介绍了一个O(n^2logn)求圆的面积并的算法. 并将其拓展,使其可以求得复杂现实图形的并集.与经典的扫描线相比,本文介绍的方法效率高,占用空间少,容易实现及拓展,而且几乎没有难以处理的几何特殊情况. (more…)

Tags: 圆的面积并, 计算几何