计算几何_1讲述.ppt

COP POINTS（FOJ 1393） //判断 if(x-y==0) printf(Yes\n); else printf(No\n); 点到面的距离 点与多边形 点是否在圆内（到圆心的距离） 点是否在矩形、多边形内 判断点q是否在多边形（凸或凹多边形）P内 与矩形有关的包含问题（一） 判断矩形是否包含点： 只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。 判断线段、折线、多边形是否在矩形中： 因为矩形是个凸集，所以只要判断所有端点是否都在矩形中就可以了。 与矩形有关的包含问题（二） 判断矩形是否在矩形中： 只要比较左右边界和上下边界就可以了。 判断圆是否在矩形中： 很容易证明，圆在矩形中的充要条件是：圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。 点是否在多边形内(重要) 设多边形P的顶点序列为p1, p2, …,pn. 过q作水平射线L与P的边界不相交，则q在P的外部。否则，L和P的边界相交，计数交点的数目，并依据交点的奇偶性可以判断q是否在P的内部，具体地说就是，交点数为奇（偶）数时，点q 在P的内（外）部。 点是否在多边形内 由于这里的多边形不一定是凸点，所以上述的判断方法对某些情况是不适合的，要注意区分（射线经过多边形的某条边时不成立）。 如图a，此时射线与多边形的端点相交，应该只能算与边交了一次。 如图b，射线也与点相交， 但此时却不能算。 点是否在多边形内 特殊情况1：多边形的水平边不作考虑 P 点是否在多边形内 特殊情况2：若射线经过多边形顶点，则仅对边上纵坐标较大端点进行计数 P P 计数一次 计数一次 P 计数一次 点是否在多边形内 特殊情况3：射线与多边形边重合的情况 p 为了统一起见，我们在计算射线L和多边形的交点的时候： 1、对于多边形的水平边不作考虑； 2、对于多边形的顶点和L相交的情况，如果该顶点是其所属的边上纵坐标较大的顶点，则计数，否则忽略； 3、对于P在多边形边上的情形，直接可判断P在多边形上。 点是否在多边形内 另一种方法： 如果所作的射线经过多边形的某条边， 则重新作一条射线，以此类推，避开这种情况。 判断两条线段是否相交 判断线段[P1, Q1]和[P2, Q2]是否相交 两个步骤： (1)快速排斥试验 设以线段P1P2 为对角线的矩形为R，设以线段Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交。 (2)跨立试验： 如果两线段相交，则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ，则矢量( P1 -Q1 ) 和( P2 -Q1 )位于矢量( Q2 -Q1 ) 的两侧，即 ( P1 -Q1 ) ×( Q2 -Q1 ) * ( P2 -Q1 ) ×( Q2 -Q1 ) ＝0。 线与线 判断两条线段是否相交 判断线段与直线是否相交 判断直线与直线是否相交 若相交求交点 判断两条线段是否相交 bool isIntersected(TPoint s1, TPoint e1, TPoint s2, TPoint e2) { if( (max(s1.x, e1.x) = min(s2.x, e2.x)) (max(s2.x, e2.x) = min(s1.x, e1.x)) (max(s1.y, e1.y) = min(s2.y, e2.y)) (max(s2.y, e2.y) = min(s1.y, e1.y)) (multi(s2, e1, s1) * multi(e1, e2, s1) = 0) (multi(s1, e2, s2) * multi(e2, e1, s2) = 0) ) return true; return false; } 判断线段与直线是否相交 有了判断直线相交的基础，判断线段和直线是否相交就很简单了。比如判断线段[s2, e1]和直线L是否相交，只需要在直线L上取横坐标X无穷大和无穷小的两点s1, e1，然后判断线段[s1, e1]和线段[s2, e2]是否相交即可。 例：处于危险中的飞行员 1941年第二次世界大战还在继续。德国、意大利和匈牙利占领南斯拉夫好几个月。在Tito的带领下，虽然失去了数千条生命并且仍然处于法西斯主义者的威胁下，但是直到敌人逃离他们的祖国前南斯拉夫的人民从未停止过反抗。在东边，虽然德国和苏联在1939年8月23号签了一份协议：两国互不侵犯，但希特勒还是在1941年6月22号对苏联不宣而战这战争变的越来越激烈。十月二号，德国开始向莫斯科进攻，试图在十天内占领它。然而在二个月之后莫斯科仍然没被攻破，随着成千上万的人的牺牲然后，在莫斯科保卫战和斯