钱桥平面图处理方法.pptxVIP

平面图的处理方法;一、平面几何中的基本元素;给定一个凸多边形A，查询一个点是否在它内部。;二、平面图的基本性质;性质1：r = m – n + k + 1;性质2：r = 2*n – 4 性质3：m = 3*n - 6;三、平面图的存储;邻接矩阵;平面图需要支持哪些查询操作？;步骤0：化无界为有界;构建结构（2）：;对于不连通的图，应如何处理？;对于不连通的图，应如何处理？;对偶图的应用：;Case 1：;Case 2：;Case 3：;四、梯形图及其查找结构;一种思路是，引入若干条垂直竖线将平面图切割：;域的数量会增加至O(n^2); 另一种思路是，每个点沿竖直方向发出射线，碰到其他点或线段即停止;证明： 每个点引出两条射线，至多增加两个节点。故节点总数不超过3*n。;除了这张梯形图外，我们还需要一个查找结构：;五、构造梯形图查找结构——随机增量法;将i个点随机排列，则第i个点在前i-1个点的轮廓圆外的概率不大于3/i。;已得到前i-1个点的轮廓圆，判断第i个点是否在该圆内： (i-3)/i的概率：在圆内或圆上，可直接忽略该点 3/i的概率：在圆外，需要重新构造前i个点的轮廓圆;已得到点a与前j-1个点的轮廓圆，判断第j个点是否在该圆内： (j-2)/j的概率：在圆内或圆上，可直接忽略该点 2/j的概率：在圆外，需要重新构造前j个点的轮廓圆;子任务：在O(j)时间内，为前j个点构造轮廓圆。 已知其中点a与点b（j号点）一定在圆上！;构造梯形图及其查找结构： 最初，梯形图中没有任何点和边，只有一个梯形域，对应的查找结构中只有一个三角节点。 以一个随机的顺序向梯形图中插入平面图的边，同时维护梯形图及其查找结构。 整个过程中，先不要过于纠结时间复杂度的问题。;插入一条新的线段时： 1、查询待插入线段的两个端点在原梯形图的哪个域 这就是我们的查询操作，可直接套用！ 若该点在某条竖直的射线上，算哪个域？ 若该点在某条边上，算哪个域？;2、插入线段，维护梯形图及查找结构 情况1：待插入线段的两个端点在同一个梯形域中：;对应的一些边界情况如何处理？;情况2：待插入线段横???了若干个梯形域;通过邻居的信息，可以顺藤摸瓜找到所有涉及到的梯形：;问题：这是一个梯形，应该合并！如何合并？;合并后，梯形域的数量增加了常数个。如何证明？;证明： 对于相邻的两个梯形域，他们共用一条边。 插入前，有k个梯形域，则有k+1条边。 合并后，除了两端分别多出一个域外，每条边最多对应一个梯形域。 故合并后最多有k+3个梯形域。;情况2：域增加O(1)个，引入新节点O(k)个，时间复杂度O(k)。;*复杂度的分析;*处理退化情况： 去掉基本假设“所有点横坐标互异”，该如何处理？;剪切变换法：;过点P做一条竖直垂线，判断点Q在其左侧、右侧或线上 对于点P(Xp+aYp, Yp)和点Q(Xq+aYq, Yq)： 若Xp != Xq，（由于a足够小）已经可以比较出他们横坐标的大小关系。 若Xp = Xq ，则Yp与Yq的大小关系，就是两个点横坐标的大小关系。 所以，我们把x当做第一关键字，y当做第二关键字进行两次比较，就可判断出点Q的位置。;对于线段P1P2，判断点Q在其上方、下方或线上 剪切变换前后，点与线的位置关系不变！ 只需对未经过剪切变换的Q与P1P2作比较即可。;行胜于言;谢谢大家！