北京大学ACM暑期课讲义-计算几何教程

1、计算几何学教程、计算几何图形、计算几何恶心的地方，代码很长，很难写。 有必要讨论各种边界情况。 稍后要介绍的算法可能需要自己处理边界，除非一些边界情况处理得很完美，不需要讨论。 有精度误差、二维向量、向量、大小和方向的量。 也称为矢量。 大家中学毕业后，我就不怎么说话了。 可以利用向量的表现、点积、角度、向量的垂直、向量的缩放、向量的投影、向量的对称、二维交叉积、有向面积、有向面积的符号、点积和二维交叉积的方向性、点积来判断向量的前后。 可以利用二维交叉乘积来确定向量的左右。 可以求出二维向量的旋转、二维向量的极角、二维计算几何、约定、直线、点到直线的距离、点、三角形的面积、两条直线的交点、两

2、条直线的交点，判断是否位于两条线段上。 请注意，平行不一定不相交，才能判断两条线是否相交。 可能有两条线段一致的部分或一致点。 三角形的重心、多边形、多边形在平面上由有限的线段(大于2 )构成，是连接首尾描绘的封闭图形。 教程后的多边形通常是指不相交边的简单多边形. 多边形的记录一般通过依次记录顶点的方式、即依次记录构成多边形的线段的方式来进行。 方向通常是逆时针方向。 然后，判定点在多边形内外，以判定点为起点生成任意的放射线，计算该放射线和多边形的交点数。 有偶数个交点就在形状之外，否则就在形状之内。 线段和端点相交或重叠的话，需要复杂的判断。 在这种情况下，可以采取别的放射线。 求多边形面

3、积，基本的想法是进行三角分割。 如果用普通面积的累计来计算多边形的面积，三角分割就会变得非常复杂。 但是，如果使用有向面积的话，这个过程会简单自然地通用。 算法、算法演示、算法演示、算法演示、算法演示、算法演示、算法演示、算法演示、算法演示、三角分割、三角分割将多边形分成几个三角形部分，其中“正的部分”和“负的用这个方法可以解决很多问题。 例题：求出多边形的重心，给出名字正确、简单的多边形，求出重心的位置。 预备知识：求出质点组的重心，利用解答、三角分割，计算各三角形的面积和重心，把这个三角形作为一个质量作为其面积，把坐标作为其重心的质点。 如果这个三角形是“负的部分”，则具有“负的质量”。

4、最后计算质点群的重心即可。凸集、凸集的例子、空集直线、放射线、线段凸多边形圆及内部、二次曲线及内部的几种原料，根据各原料a成分和b成分的比率不同，混合这些原料而得到的产品的a、b两成分的比例、凸包、点集s，将包含s中所有点的最小凸集称为s的凸包。 如果s是有限集合，则其凸包是凸多边形。 直观上看，s中的所有点都贴在板上，用橡皮筋包围所有的点，松开手，橡皮筋表示s的凸包。 凸包、水平序Graham扫描算法和Graham扫描算法分为水平序和极角序两种。 极角序算法可以一次确定整个凸包，但计算极角需要三角函数，速度慢，精度差，特殊情况很多。 水平顺序算法需要扫描两次，但排序简单，讨论简单，不易出错。

5、 算法流程、算法演示，首先对所有点进行排序。 将算法演示，1和2推入堆栈。 算法演示，2堆叠，3堆叠。 算法演示，没有弹出要点，4个堆栈。 算法演示，4被堆叠，5被堆叠。 算法演示，5被堆叠，6被堆叠。 算法演示，6堆叠，7堆叠。 的双曲馀弦值。 算法演示，按相反顺序扫描找到上凸案例。 格拉汉姆扫描的时间很复杂，这是个傻瓜。由于该算法的瓶颈是排序的，所以时间复杂度是O(N log N )。 如果坐标都是整数，可以通过基数排序将复杂性优化为O(N )。 的双曲馀弦值。 旋转卡算法如何计算n个点中距离最大的两个点的距离？ 请求O(N log N )的算法。 很容易证明距离最大的两点必须是凸包的两点

6、，这一点在求出凸包后才能作文章。 然后按一下。 凸包的两个顶点在一对平行切线上时，称为脚后跟点。 简单地证明，答案一定是一对脚后跟点之间的距离。 对于脚后跟点的列举，从一对脚后跟点逆时针列举下一对脚后跟点的话，观察下图的角和角的大小，选择其中小的一方旋转即可。 算法，最左边的点和最右边的点一定是脚后跟点。 从这个时候开始列举即可。 注意：除了“点-点”之外，还有“点-边”和“边-边”的情况。 在这些情况下，列举所有的点对。 看起来很简单，但写起来很辛苦。 求出以旋转卡盘练习问题、POJ 2178点集中最远点POJ 3608点集中最远点POJ 2079点集中点为顶点的三角形的最大面积，求出O(N

7、2 )算法。半平面、半平面的显示、半平面的交叉、半平面为凸集，因此半平面的交叉也是凸集。 有限半平面的交点可以是空集合、点、直线、放射线、线段、凸多边形、有开口的形状、半平面。 质朴的每次O(N )算法，为了保证结果是凸多边形或其退化，首先要做非常非常大的框。 你知道的。 依次列举多边形的边，与半平面相交，并将相交部分添加到新的多边形中。 得到半平面边界和凸多边形相交形成的边后，就会立即添加到新多边形中。 算法演示、关注的边界情况1、关注的边界情况2、关注的边界情况3、合计O(NlogN )算法是朱泽园在其国家集训团队论文半平面交的新算法及其实用价值中提出的算法。 因为形成了非常非常大的框，半

8、平面交叉的结果一定是凸多边形。 凸多边形分为下凸壳体和上凸壳体。 把这两部分分开处理，可以得到非常好的性质。 下凸壳体和上凸壳体，分别以极角，筛选有可能属于下凸壳体和上凸壳体的半平面，按极角大小从小到大的顺序排列。 上凸壳排序时，在极角位于第三象限的半平面上加上2.来消除障碍，选择极角相对于同一半平面位于最左侧的，并丢弃剩馀部分。 这保证了所有半平面的极角都不同。 处理下凸壳，进行算法演示，首先将前两个半平面放入堆栈中。 算法演示，x0 x1，将新的半平面推入堆栈。 算法演示，x0 x1，弹出堆栈顶部。 算法演示，x0 x1，将新的半平面推入堆栈。 这样类推。 处理上凸壳、上凸壳的集成，只要凸

9、壳有多个半平面，就可能形成无用的半平面。 如图所示，下图的p-1的一半平面是没有用的。 然后按一下。 指针p1指下凸壳体的最左侧，p2指上凸壳体的最左侧。 如果下壳至少有两个半平面，则检查p2和p1边界的交点以及下壳p1右侧的半平面和p1边界的交点。 如果这两个交点之和为空或只有一个端点，则丢弃半平面p1，并将指针p1向右移动。 处理了p1之后，与处理了p2的情况相同。 当p2向右移动时，重复p1的处理，并类推，直到p1和p2不向右移动为止。 就像过滤了右边不需要的半平面。 实际上“这两个交点的和是空的，或者只有一个端点”只讨论交点的坐标的大小。 但是，这两个交点的x坐标可能相同，但y坐标不相

10、同。 不能像前面那样只讨论x坐标。 算法演示，p1上两者的交叉是空集合。 把p1向右移动。 算法演示，p2上两者的交叉是空集合。 将p2向右移动，再次检查p1。 算法演示，p1和p2满足要求，结束左侧检查。总而言之，时间的复杂性是O(N log N )，因为算法的瓶颈仍在排序中。 使用桶排序还可以得到O(N )的半平面交叉算法，但没有明显的性能提高。 总体上讨论很困难，写起来并不困难。 精度有很大的问题，且半平交主题通常被不太常用，因为其允许O(N2 )算法。 半平面交叉练习题，求POJ 1279多边形的核。 核内的点满足到多边形边界的任意点的线段，只有多边形在该点相交。 POJ 3525求出

11、凸多边形的最大内接圆半径。 POJ 2451裸体的半平面交叉。 朱泽园专门针对他的算法问题，要求了O(N log N )算法。 POJ 3384求出在凸多边形的内部能放入两个半径为r的圆的最大面积。 两个圆可以重叠，但不能与多边形相交。 需要旋转卡盒。 到圆、定点o的距离等于值r的点的集合。 根据上下文的不同，也可以包含内部的点。 o是圆心，r是半径。 日元只要用这两个东西表示就行了。圆与直线的交点、圆与直线的交点、圆与圆的交点、圆与圆的交点、圆与圆的交点、圆的面积合并，主题： SPOJ CIRU提供N (N 1000 )个圆，求出和的面积。 请求O(N2 log N )的算法。 后面所示的算

12、法是AekdyCoin的原始算法。 解析，如图所示，最后形成的图形由很多弓形和多边形构成。 弓形可以单独计算，多边形可以利用叉积分成各边来计算，所以可以按圆分别考虑。 每个日元的状况没有联系吗？ 各连通块中的弓形和多边形的边实际上被处理得很好，所以图形不连通也没有问题。 有“洞”吗？ 现在发生了非常NB的事。 我们累积的是有向面积，因为孔中的多边形是反向(顺时针)旋转的，所以孔会自动取消，时间的复杂性，每圆求出O(N )次的交点，出现了O(N )个交点。 为了找到不被垄断的弧，要对交点进行排序，所以要花O(N log N )的时间对每个圆进行处理。 总时间复杂度O(N2 log N )。 算法

13、得到了扩展，SPOJ CIRUT正好求了1次、2次、 n次的面积。 算法的本质是处理“裸体”部分。 这个方法也可以用于求出很多圆和很多凸多边形的面积，但是情况非常复杂，也经常进行讨论。3-Dimension Vector、3维向量、3维、3维交叉积、左手系和右手系、x、y、z轴方向、传统上应该满足右手系。 也就是说，伸出右手，将4根手指从x轴方向转动到比扁平小的y轴方向，拇指指向z轴方向。 同样也可以定义左手系。 三个不同面的矢量必然满足左手系和右手系的任一个。 注意，文字游戏，“a、b、c成右手系”和“b、a、c成右手系”是完全相反的命题。 但是，“a、b、c成右手系”和“b、c、a成右手系

14、”是相同的命题。 画画看吧。 三维叉积的性质，在三维空间失去的，极角。 在三维空间中描述向量的方向不仅需要一个角度，实际上还需要两个角度。 左右。 在三维空间中，两个向量之间没有左右概念。 取而代之的是三个向量间的左手系和右手系的概念。 混合积，有向体积，图。 a、b、c混合积的模型是a、b、c所形成的长方体的体积。 考虑到符号，混合积也称为有向体积。 a、b、c构造的三角锥的体积是长方体的1/6 .所有的本质：行列式、3-dimensioncomputealgeometry、三维计算几何、三维直线、三维直线的表现法与二维相似。 计算点到直线的距离的方法与二维相同。 计算分数的方法也和二维相同

15、。 虽然是异面直线，但在三维空间中，直线除了平行和交叉以外都有第三位置关系：异面。 不同面的直线的距离是两条直线上距离最小的两点的距离。 这是两条直线的垂线段的长度。、异面直线的距离、异面直线的距离、两直线的交点，首先求出它们的距离。 如果不是0，很明显树有交点。 在其它情况下，如果它们的方向向量平行，则它们一致。 否则就交叉了。 建议利用后述的投影技术转换为二维问题。 平面、平面是到两点的距离相等的点的轨迹。 具体地说，什么很清楚点法国、与平面垂直、即与平面上的所有向量垂直的除零以外的向量被称为平面的法线向量。 可以证明平面的所有法线向量都是平行的。 当记录平面的法线向量v并且记录平面上的点

16、p时，可以完全表示整个平面。从点到平面的距离、直线与平面的交点、直线与平面的交点、平面与平面的交线、二面角是两个平面的法线矢量所成的角。 平面上的点的二维投影、平面上的点的二维投影、平面上的点的二维投影、多面体、多面体是指由三维空间的平面和直线边组成的几个物体。 以上是科学的定义。 我觉得这样的胡说八道毫无用处。 假设多面体的各面是三角形。凸多面体，如果一个多面体是凸集合就是凸多面体。 就像凸多边形是半平面的交叉一样，凸多面体也可以看作是半空间的交叉。 求半空间的交往非常复杂，这里不怎么介绍。 但是，关于半空间的基本知识还需要说明。 半空间的表示可以用三个非公共线的秩序点表示，使得半平面可以用

17、两个不同的秩序点表示。 为了判断点p是内侧还是外侧，从点p向平面看。 如果半空间的三个秩序点逆时针，点p就在外侧，否则点p就在内侧。 凸多面体的表现表示一个凸多面体需要记录其所有面。 对于所有的面，必须正确地记录这一面上的点的顺序。 根据假设，因为每个面是三角形，即包含三个点，所以每个面表示半空间。 凸多面体必须是这些半空间内侧的交点。 另外，如果p在半空间a之外，则用半空间a或a表示的平面对于p是可见的。 我们观察凸多面体时，看到的面是视点的可视面。 凸多面体各面的点的顺序，必须保证从多面体内部的哪个点看，都看不到所有的面。 如果把右手系置换成行列式的符号，则视觉概念会高维扩展。 多面体有非三角面时，这种面的记录必须保证其上的点从多面体的内部看是顺时针排列的。 此时，这一面还能有效地表示半空间。 根据三维凸包、凸包的定义推测，一坤三维空间中的点凸包是凸多面体。 事情到现在为止我们不得不想办法谋求那个。 但是，由于失去了左右这一概念，Graham扫描法被完全废弃并不容易发现。 我该怎么办？ 为了方便，我们假定没有四点共同的情况。 暴力的方法，O(N3 )列举了所有点的三元组，将其视为半空间。 如果所有其他点都在该半空间内，则该面是凸包的一面。 时间复杂度O(N4 )。 很