平面图(planar graph)就是一个可以在平面上画出来的图,并且所有的边只在顶点处相交。平面图的对偶图(dual graph)是将这个平面的每个区域看成点,原图每一条边所属的两个相邻的区域对应在对偶图中的点有连边
比如下面这张图(来源于 Wikipedia)
蓝色的部分就是一个平面图,红色的就是它的对偶图
平面图的点定位(point location)就是找出一个点属于这个图的哪个区域
这篇文章介绍如何将一个平面图转换为其对偶图,和基于扫描线的离线的点定位算法(对着代码看了一天终于会了QAQ)