标签归档:c

【算法】求两个凸多边形的交集的面积

问题编程计算两个凸多边形的交集多边形的面积

解法分析:显然凸多边形的交集仍然是凸多边形,本解法的关键是首先求出交集凸多边的全部顶点,然后利用凸多边的面积算法求解。首先明确交集多边形的顶点组成。在本问题中,容易证明交集的顶点应该出自下面的两类点 :〔一〕已知的两个多边形 的顶点〔二〕两个多边形的边的交点第一类点的求法:显然如果一个多边形的某个顶点在另一个多边形内〔包括在边上〕则该顶点是交集的一个顶点,因此我们只需依次对两个多边形的顶点进行判断,检验其是否包含在另一个多边形中,即可求出第一类点。本程序中的子函数 inarea( )利用待判断点与另一个多边形的全部边按顺序组成的三角形的面积总和与此多边形的面积进行大小比较,来判断该点的归属,若大则在凸多边形的外部,不属于第一类点;否则,是交集的顶点。第二类点的求法:两个多边形相交可能有两条边重合〔包括部分重合〕的情况,显然重合的部分必是交集的一条边,这条边的顶点是已知两个多边形的顶点,即应属于第一类点,在第一类点的求法中显然已包括了这种顶点,因此我们在求两个多边形的边的交点时,可以不计算两条边重合时的交点,而只计算两条边相交〔不平行〕时的交点。在本程序的算法中为了求两条边的交点,我们采用线段的参数方程表示法,即x=a*t+by=c*t+d        其中0<=t<=1 ;设线段的两个端点坐标分别是〔x0,y0〕和〔x1,y1〕,则线段的参数方程可写成:x=〔x1–x0〕*t+x0y=〔y1–y0〕*t+y0   其中 0<=t<=1;据此可以求两条边的交点,详细的计算公式请见后面的源程序。如果某个多边形的顶点在另一个多边形的边上,由上面的算法可知它将被分别计入两类点当中,因此我们最后求得的交集多边形的顶点可能有部分是重复的,但由多边形的面积算法可知这不会影响面积的大小,因此在确定两类点时,不需要做精细的划分。在求三角形的面积时,用到了下面的公式:┃ 1  x0  y0  ┃S3 = (1/2)* ┃ 1  x1  y1  ┃┃ 1  x2  y2  ┃其中〔x0,y0〕〔x1,y1〕〔x2,y2〕为三角形的三个顶点坐标;并且 S3为三角形的有向面积,之所以用有向面积是因为在确定交集多边形顶点的顺序时,要利用三角形的有向面积进行方向判断。源程序://VC调试通过,
#include<stdio.h>
#include <stdlib.h>
#define ABS(x)  ((x)<0?-(x):(x))
struct point{float x;float y;};bool crosspt(pointp,point p1,point p2,point q1,point q2) //求线段(p1,p2)和(q1,q2)的交点float tmp,tp,tq;...
阅读全文
发表在 程序开发 | 标签为 , , | 留下评论

【程序】八皇后动态图形的实现

八皇后问题(Eight Chess Queens )是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出

在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,...

阅读全文
发表在 人工智能, 服务器, 游戏, 程序开发 | 标签为 , , , , , , , , | 留下评论

【数学】圆周率π里面的《红楼梦》

圆周率3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 ......有许多有趣且引人...

阅读全文
发表在 数学, 杂篇, 雅致小品 | 标签为 , , , , , , , , | 留下评论

【文摘】阿尔法狗的上帝

2017-05-2郭暮云OC海外校园
redline
京时间5月25日,阿尔法狗(Alphago)与柯洁大赛第二局将在浙江乌镇继续进行。弈至155手,柯洁认负,AlphaGo执黑中盘胜,目前比分2比0,AlphaGo赢下与...
阅读全文
发表在 人工智能, 圣经, 格物 | 标签为 , , , , , , , | 留下评论

【源码】快速组合排列算法

作者GoodKi--如何从一个整数数列中,快速的查找出一个子集合,使得这个子集的整数和等于一个...阅读全文
发表在 博客, 数学, 服务器, 程序开发 | 标签为 , , , | 留下评论

【译文】C# 集合之:字符串数组输出到文本文件

字符串数组输出到文本文件原文C# Tutorial and source code全部的 C# 对象、变量和常数都必须有指定的类型。数组是包含相同类型的...阅读全文
发表在 程序开发 | 标签为 , , | 留下评论