[计算几何.ppt

所以，我们需要控制误差。 const double eps = 1e-8; //无穷小量 int sgn(double x) { //判断正、负和零 return x-eps ? -1 : xeps; } 此时一个二维凸包的程序应该能够完美地写出来。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 原来如此~ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 思路： 逆时针遍历凸包的边，判断该点是否在该边左侧 （叉乘判别法） 其他： 面积判别法 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 方法一： 射线法 从判定点出发，任意引一条射线，若和边界相交奇数次，说明点在多边形内；否则在多边形外。 方法二： 转角法 把多边形每条边的转角加起来，如果是360度，说明在多边形内；如果是0度，说明在多边形外；如果是180度，说明在多边形边界上。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 射线法流程图 图是用来观赏的 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 计科1110 王鑫磊 2013年11月3日 QQ：331829605 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 在现代工程和数学领域，计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。 ACM竞赛中，计算几何问题的输入一般是关于一组几何物体（如点、线）的描述；输出常常是有关这些物体的问题的回答，如直线是否相交，点围成的面积等问题 我们的ppt也以ACM竞赛为背景 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 给定二维平面上的两条线段，每条线段给定两个端点。 问题： 判断是否存在交点。 若存在，求两线段的交点。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 先利用端点求出线段对应直线 列方程组联立求解 判断交点是否在两条线段上 常用的解析几何的做法！ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 向量、点都可以用一个二元组表示，即矢量 Pt line_cross_line (Pt a, Pt b, Pt c, Pt d) { double x, y, Sd=(b-a)^(d-a), Sc=(c-a)^(b-a); x = (d.x*Sc + c.x*Sd)/(Sc+Sd); y = (d.y*Sc + c.y*Sd)/(Sc+Sd); return Pt (x,y); } Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 还有其他解决计算几