平面图转对偶图及点定位

平面图(planar graph)就是一个可以在平面上画出来的图,并且所有的边只在顶点处相交。平面图的对偶图(dual graph)是将这个平面的每个区域看成点,原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边

比如下面这张图(来源于 Wikipedia)

300px-Duals_graphs.svg

蓝色的部分就是一个平面图,红色的就是它的对偶图

平面图的点定位(point location)就是找出一个点属于这个图的哪个区域

这篇文章介绍如何将一个平面图转换为其对偶图,和基于扫描线的离线的点定位算法(对着代码看了一天终于会了QAQ)

(more…)

Read More