文档介绍：平面图的处理方法一、平面几何中的基本元素点、向量角度直线、射线、线段简单多边形求向量夹角向量旋转点与线的位置关系点到线的投影线段求交点与简单多边形的位置关系给定一个凸多边形A,查询一个点是否在它内部。——O(n)预处理,O(logn)在线回答给定一个顶点满足极角序的多边形B,查询一个点是否在它内部。——O(n)预处理,O(logn)在线回答给定一个多边形C,查询一个点是否在它内部。给定一个平面图D,查询一个点在哪个域。O(nlogn)预处理,O(logn)回答!这就是我们今天的目标!二、平面图的基本性质定义:若图G可画在平面上,使得任意两条边都不会在非端点处相交,则称G是平面图。n:平面图中的点数m:平面图中的边数k:平面图中连通块的数量r:平面图中域的数量性质1:r=m–n+k+1证明:对于n个点,生成为k个连通块的森林,需要n-k条边在此基础上,保持连通块数量不变,每增加一条边,会导致增加一个域由于初始有1个域,增加的边数为m-(n-k),故域数为m–n+k+1。性质2:r<=2*n–4性质3:m<=3*n-6证明:每个域最少也要有3条边包围,每条边可用2次,故有2*m>=3*r。带入等式r=m–n+k+1,再结合k>=1即可。结论:平面图中边、域的数量均是O(n)的。三、平面图的存储一个优秀的存储结构应满足:占用空间小构建时间复杂度低支持快速的查询邻接矩阵邻接表占用空间:构建时间:查询相邻边:遍历全图:O(n^2)O(n+m)O(n^2+m)O(n+m)O(n)O(n^2)O(deg(u))O(n+m)平面图需要支持哪些查询操作?对于一个域,查询其周围的点和边为每个域创建一个列表,存储其边界上的点和边(1)对于一个域,查询其相邻的域为平面图创建对偶图(2)对于一个点,查询其相邻的边——邻接表步骤0:化无界为有界步骤1:将每条边拆成两条有向边,需要有指针指向对方步骤2:将每个点发出的有向边按照顺时针排序步骤3:任取一条未访问的边出发,在每个节点处选择顺时针第一条边,直到返回出发的边为止。构建结构(1):