半平面:顾名思义,半平面就是平面的一半,那么半平面应该如何表示呢?我们知道一条直线可以将平面分成两半,如果直线的方程为 ax+by+c=0 ,那么半平面就可以表示为 ax+by+c<0或者ax+by+c>0 ,如果我们这样定义半平面,那么半平面交也就很好解释了。半平面交:每一个半平面就是一个不等方程,那么半平面交就是满足这些半平面不等方程组的可行域。应用:现在了解半平面交的应用就是求多边形的核,那么多边形的核又是什么鬼?多边形的核就是在这个区域中的任意一点与多边形边的连线都在多边形的内部。就如同一个摄像头,将摄像头安装在这个区域的任意一点都可以看到多边形的任何地方。求解:那么明白了半平面交是什么鬼了之后,如何求解半平面交呢?- 假设现在我们有一个多边形

讯享网
- 我们以AB为直线,那么属于半平面在下方,可以发现C不在半平面中,所以去掉C,但是AB与CD有一个交点,所以在半平面中多了一个点H,那么半平面交的点集为 A,B,H,D,E,F,G(顺时针)

- 接下来我们以BC为直线,可以判断A不在半平面中了,所以半平面的点集为 B,H,D,E,F,G

- 继续以上步骤,分别以相邻的点为直线来切割区域,去掉不在切割之后区域的点,增加新的交点。

- 最后的到的红色线段围成的区域就是多边形的核(一个凸包)。
- 我们以AB为直线,那么属于半平面在下方,可以发现C不在半平面中,所以去掉C,但是AB与CD有一个交点,所以在半平面中多了一个点H,那么半平面交的点集为 A,B,H,D,E,F,G(顺时针)
例题
【POJ3130】How I Mathematician Wonder What You Are!
After counting so many stars in the sky in his childhood, Isaac, now an astronomer and a mathematician uses a big astronomical telescope and lets his image processing program count stars. The hardest part of the program is to judge if shining object in the sky is really a star. As a mathematician, the only way he knows is to apply a mathematical definition of stars.
The mathematical definition of a star shape is as follows: A planar shape F is star-shaped if and only if there is a point C ∈ F such that, for any point P ∈ F, the line segment CP is contained in F. Such a point C is called a center of F. To get accustomed to the definition let’s see some examples below.

The first two are what you would normally call stars. According to the above definition, however, all shapes in the first row are star-shaped. The two in the second row are not. For each star shape, a center is indicated with a dot. Note that a star shape in general has infinitely many centers. Fore Example, for the third quadrangular shape, all points in it are centers.
Your job is to write a program that tells whether a given polygonal shape is star-shaped or not.
Input
The input is a sequence of datasets followed by a line containing a single zero. Each dataset specifies a polygon, and is formatted as follows.
n
x1 y1
x2 y2
…

You may assume that the polygon is simple, that is, its border never crosses or touches itself. You may assume assume that no three edges of the polygon meet at a single point even when they are infinitely extended.
Output
For each dataset, output “1” if the polygon is star-shaped and “0” otherwise. Each number must be in a separate line and the line should not contain any other characters.
Sample Input
6
66 13
96 61
76 98
13 94
4 0
45 68
8
27 21
55 14
93 12
56 95
15 48
38 46
51 65
64 31
0
Sample Output
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <string> #include <queue> #include <algorithm> #include <iostream> using namespace std; const double eps = 1e-6; const int Max = 55; typedef struct Point { double x,y; Point(){} Point(double _x,double _y):x(_x),y(_y){} Point operator + (const Point &a)const { return Point(x+a.x,y+a.y); } Point operator - (const Point &a)const { return Point(x-a.x,y-a.y); } double operator * (const Point &a)const { return x*a.x+y*a.y; } Point operator * (const double &a)const { return Point(x*a,y*a); } double operator ^ (const Point &a)const { return x*a.y-y*a.x; } }Vector; Point P[Max]; Point S[Max*10],T[Max*10]; int dbcmp(double a) { return fabs(a)<eps?0:(a>0?1:-1); } int n; Point GetLineIntersection(Point p,Vector v,Point q,Vector w)//计算两条直线的交点。 { Vector u = p-q; double t = (w^u)/(v^w); return p+v*t; } bool JudgePolygonNucleus() { int num1 = n; int num2; for(int i = 0;i<n;i++)//初始的多边形的核为他自己本身 { S[i] = P[i]; } for(int i = 0;i<n;i++) { num2= 0 ; for(int j = 0;j<num1;j++) { int ans1 = dbcmp((P[(i+1)%n]-P[i])^(S[j]-P[i])); int ans2 = dbcmp((P[(i+1)%n]-P[i])^(S[(j+1)%num1]-P[i])); if(ans1>=0)//通过叉积判断是不是在直线的某一侧,>0 在直线的左侧,<0在直线的右侧,=0 在直线上 { T[num2++] = S[j]; } if(ans1*ans2<0) { T[num2++] = GetLineIntersection(P[i],P[(i+1)%n]-P[i],S[j],S[(j+1)%num1]-S[j]); } } num1 = num2; for(int j = 0;j<num2;j++) { S[j] = T[j]; } } return num1!=0; } int main() { while(scanf("%d",&n) && n) { for(int i = 0;i<n;i++) { scanf("%lf %lf",&P[i].x,&P[i].y); } if(JudgePolygonNucleus()) { printf("1\n"); } else { printf("0\n"); } } return 0; }
讯享网
【POJ3335】Rotating Scoreboard和上一道题意一样只是输出不同。
【POJ1474】Video Surveillance同上
【POJ1279】Art Gallery求核的面积




版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/78486.html