简单多边形

《简单多边形》由会员分享，可在线阅读，更多相关《简单多边形（5页珍藏版）》请在装配图网上搜索。

1、1.简单多边形p被称做星形多边形(star-shaped),如果其中存在某个点q,使得对于该多边形 内的任何点P,线段pq完全落在p内.给出一个算法，判断任何给定的简单多边形是否为一个 星形多边形. 该算法的期望运行时间必须是线性的.判定方法是先将所有边两两求出交点，然后依次判断这些交点是不是中点，只要 有一个是，多边形就是星形多边形，否则就不是。因为可以证明，只要是星形多 边形，这些交点中至少有一个一定是其中点。判断P点是否是中点的方法是：所有顶点与P点之间连一条线，若有连线不全在 多变形内，则不是中点。这个问题又可以转化为按一定的顺序(顺时针或逆时针) 遍历每条边，看P点是否在所有边的同一

2、侧(右侧或左侧)，是的话，P就是中 点。源程序如下( POJ3130)：#include #include #define SIZE 110const double Z = 1e-6;struct Linedouble A,B;bool y;lineSIZE;struct Pointdouble x,y;inSIZE,testSIZE*SIZE;int pnum,n;void makepoint(Line &a, Line &b)if(!a.y & !b.y)return ;if(!a.y)testpnum.x = a.A;testpnum+.y = b.A*a.A+b.B;else if(!

3、b.y)testpnum.x = b.A;testpnum+.y = a.A*b.A+a.B;elseif(a.A != b.A)testpnum.x = (b.B-a.B)/(a.A-b.A);testpnum.y = testpnum.x*b.A + b.B; pnum+;double crossMul(Point a, Point b,Point c)b.y -= a.y; b.x -= a.x;c.y -= a.y; c.x -= a.x;return b.x*c.y-b.y*c.x;bool check(Point p)int i;double temp,flg = 0;for(i

4、= 0; i n; i+)temp = crossMul(ini,in(i+1)%n,p); if(fabs(temp) Z) temp = 0.0;if(flg = 0)flg = temp;else if(flg*temp 0)return false;return true;int main()int i,j;while(scanf(%d,&n) & n)for(i = 0; i n; i+)scanf(%lf%lf,&ini.x,&ini.y);linei.y = true;for(i = 1;i n; i+)if(ini.x = ini-1.x)linei.y = false;lin

5、ei.A = ini.x;elselinei.A = (ini.y-ini-1.y)*1.0/(ini.x-ini-1.x);linei.B = ini-1.y - linei.A*ini-1.x;if(inn-1.x = in0.x)line0.y = false;line0.A = in0.x;elseline0.A = (in0.y-inn-1.y)*1.0/(in0.x-inn-1.x);line0.B = inn-1.y - line0.A*inn-1.x;pnum = 0;for(i = 0; i n; i+)for(j = i+1; j n; j+)makepoint(linei

6、,linej);for(i = 0; i pnum; i+)if(check(testi)break;if(i pnum)printf(1n);elseprintf(0n);return 0;2.给出两个x-单调的多边形链P和Q.证明P和Q能够相交O(n), (n是P和Q的顶点 的总数).遍历两个多边形链，直至某一个链中的顶点落入另一个链两个相邻顶点之间。假设P的顶点X坐标在Q的相邻两个顶点(q1,q2) (q1q2) X坐标之间。取点集pl, p2,p3,.为所有坐标 在q1,q2之间的点加上P上q2的第一个点。判定是否相交。如果不相交，继续遍历。3.将某凸多边形各边所对应的n条(未排序的)

7、线段组成一个集合E.试给出一个算法，在 O(nlogn)时间内，根据E计算出该多边形所有顶点按顺时针方向的一个序列.(1) 找一个内点(2) 计算这个内点到各顶点的角度0-360度(3) 按角度排序找一个内点：任选 3 点 x1,y1,x2,y2,x3,y3计算：x0=(x1 + x2 + x3)/3y0=(y1 + y2 + y3)/3.计算这个内点到各顶点的角度：dy=yi_y0dx=xi-x0ds=sqrt(dx*dx+dy*dy)sin( Ai) = dy/ds判断象限。排序不用说了吧。4.在一个所谓的矩形多边形” (rectilinear polygon)中，所有边的方向不是水平的就是垂直的. 考察包含n个顶点的矩形多边形p.试举例说明：为了看守这种多边形，有时至少需要n/4 台摄像机.如下图，有8个顶点，但是至少需要2 台摄像机。