(lecture_06)计算几何基础_easy.ppt

1、2020/8/5，1，ACM编程，信息学院计算机应用系侑腊生，2020/8/5，2，今天你在吗？ AC，2020/8/5，3，每周一颗星星(5) :=HW-木阳，2020/8/5，4，第六次，修正几何备用(commer )的2020/8/5，9，2020/8/5，10，2020/8/5，11，21 、2020/8/5、15，特别注意：上述线段的三个属性是修正几何学的基础，在求凸包等许多方面都有应用，请务必把握2020/8/5、16、第二单元格、多边形的面积和重心、2020/8/5、2020/8/5 输入：多边形(顶点为逆时针顺序)输出：面积s，2020/8/5，18，考虑以下图形：2020/8

2、/5，19，Any good idea？ 在2020/8/5，20，第一个最简单的多边形三角形，2020/8/5，21，三角形的面积：解析几何中，ABC的面积可以用点坐标=边长=求出，2020/8/5，23，修正几何的方法：在修正几何中，修正ABC的面积正负表示三角形的顶点是右手系还是左手系。 ABC是左手系统，负面积，ABC是右手系统，正面积，2020/8/5，24，大功完成：Area(A，b，c)=1/2*(ab )，Xb X a Yb Y a，Xc X a Yc Y a，2020/8/5，25，凸多边形的三角形分割当然以P1为扇面中心连接P1Pi得到N-2个三角形，由于凸性，可以保证这些

3、三角形全部在多边形内，2020/8/5，27，还成立！ 不要！ 不要！ 多边形面积公式： A=sigma(Ai) (i=1N-2 )，结论：“有向面积”a比“面积”s更为本质。 2020/8/5，28，任意点为扇心的三角形分割：可将多边形分成N-2个三角形。 为什么不能分成n个三角形呢？例如，如果把多边形内部的一点作为扇心，就可以把多边形切成n个三角形。P0、P1、P2、P6、P5、P4、p3、2020/8/5、29，前面的三角分割显然适用于多边形内部的任意点。 可以获得A=sigma(Ai) (i=1N )，即，A=sigma /2 (i=1N )、Xi X0 Yi Y0和x(i1)x0y

4、()。 2020/8/5，31，内外都好，为什么不把P0作为坐标原点呢，现在的公式？ 2020/8/5，32，简化公式：A=sigma /2 (i=1N )，Xi Yi，X(i 1) Y(i 1)，面积问题解决。 2020/8/5，33，基本问题(2) :给出简单的多边形，求其重心。 输入：多边形(顶点反时针排列)输出：重心点c，2020/8/5，34，从三角形的重心开始：三角形的重心是： (x1 x2 x3)/3，(y1 y2 y3)/3，Sigma(xi)/N，sigma(yi)/N (i=1N )？ 什么？ 什么？ 2020/8/5，35，请看例外： 2020/8/5，36，原因：错误的

5、推广公式是“质点系重心公式”，即多边形的质量仅在其顶点分布且均匀分布，但是，当前的多边形的质量在其内部区域均匀分布，即与面积相关37、Solution:分割成n个三角形，求出各自的重心和面积，此时，原来的质量均匀分布在内部区域，但当前的质量仅分布在这n个重心点(等假变换)，此时，能够利用前面的质量但是，必须稍微变更，变更为加权平均。 由于质量分布不均匀，所以各质点表示其三角形，其质量是该三角形的面积(有向面积)，这就是权力！ 2020/8/5、38、公式：c=sigma (ai * ci )/a (I=1n ) ci=中心(o pipi1)=。 2020/8/5、40、第三单元、凸包、2020

6、/8/5、41、2020/8/5、42、2020/8/5、49、2020/8/5、50、2020/8/5、51、2020/0 点； 点结果102； /保存凸点的点POINT a102； 在顶部； 双距离(点p 1、点p2)/点之间的距离return sqrt (p1. x-p2. x ) * (p1. x-p2. x )。 双倍(点p 1、点p 2、点p3)/外积return(p2.x-p1.x)*(p3.y-p1)。 比较(const void * p 1、const void * p2)点*p4、*p4。 双精灵m； p3=(点* ) p 1； p4=(点* ) p 2； m=多重(a 0、*p3、*p4)； if (m0)返回1； else if (m=0，2020/8/5，69，Any Question )？ 2020/8/5，