半平面交的一個題，也是求多邊形的核心。求出這個好像也可以用于解決一些線性規(guī)劃問題。我用的是N*N的基本算法，每加入一條直線，
就對原來求出的半平面交進行處理，產(chǎn)生新的核心。
代碼參照臺灣的一個網(wǎng)站演算法筆記上的內(nèi)容和代碼。表示這個網(wǎng)站巨不錯，求凸包的算法也參照了這個網(wǎng)站上的內(nèi)容和代碼。
半平面交的地址：
http://www.csie.ntnu.edu.tw/~u91029/Half-planeIntersection.html#a4 代碼思路主要是：先讀入所有的多邊形頂點，放入一個vector（vp）里面，然后對多邊形的每條邊求一個半平面。剛開始的時候，用一個
vector（Polygon）保存代表上下左右四個無限遠(yuǎn)角的四個點，表示原始的半平面。然后，用讀入的多邊形的每條邊去切割原來的半平面。
切割的過程是，如果原來（Polygon）中的點在當(dāng)前直線的指定一側(cè)，那么原來的點還是有效的。如果原來的點和它相鄰的下一個點與當(dāng)前
直線相交，那么還需要把交點加入Polygon集合。
還有求交點的方法比較奇葩，類似于黑書上面的那種根據(jù)面積等分的方法。
代碼如下：
#include <stdio.h>
#include <
string.h>
#include <math.h>
#include <vector>
#include <algorithm>
using namespace std;
double fPre = 1e-8;
struct Point
{
double x;
double y;
Point(){}
Point(
double fX,
double fY)
{
x = fX, y = fY;
}
};
typedef vector<Point> Polygon;
typedef pair<Point, Point> Line;
Point
operator+(
const Point& a,
const Point& b)
{
Point t;
t.x = a.x + b.x;
t.y = a.y + b.y;
return t;
}
Point
operator-(
const Point& a,
const Point& b)
{
Point t;
t.x = a.x - b.x;
t.y = a.y - b.y;
return t;
}
Point
operator*(Point a,
double fD)
{
Point t;
t.x = a.x * fD;
t.y = a.y * fD;
return t;
}
int DblCmp(
double fD)
{
return fabs(fD) < fPre ? 0 : (fD > 0 ? 1 : -1);
}
double Det(
double fX1,
double fY1,
double fX2,
double fY2)
{
return fX1 * fY2 - fX2 * fY1;
}
//3點叉積
double Cross(Point a, Point b, Point c)
{
return Det(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
}
//向量叉積
double Cross(Point a, Point b)
{
return a.x * b.y - a.y * b.x;
}
//求直線交點的一種簡便方法
//平行四邊形面積的比例等于高的比例
Point Intersection(Point a1, Point a2, Point b1, Point b2)
{
Point a = a2 - a1;
Point b = b2 - b1;
Point s = b1 - a1;
return a1 + a * (Cross(b, s) / Cross(b, a));
}
Polygon HalfPlane(Polygon& pg, Point a, Point b)
{
Polygon pgTmp;
int nN = pg.size();
for (
int i = 0; i < nN; ++i)
{
double fC = Cross(a, b, pg[i]);
double fD = Cross(a, b, pg[(i + 1) % nN]);
if (DblCmp(fC) >= 0)
{
pgTmp.push_back(pg[i]);
}
if (fC * fD < 0)
{
pgTmp.push_back(Intersection(a, b, pg[i], pg[(i + 1) % nN]));
}
}
return pgTmp;
}
int main()
{
int nN;
Point p;
vector<Point> vp;
Polygon pg;
while (scanf("%d", &nN), nN)
{
vp.clear();
for (
int i = 0; i < nN; ++i)
{
scanf("%lf%lf", &p.x, &p.y);
vp.push_back(p);
}
pg.clear();
pg.push_back(Point(-1e9, 1e9));
pg.push_back(Point(-1e9, -1e9));
pg.push_back(Point(1e9, -1e9));
pg.push_back(Point(1e9, 1e9));
for (
int i = 0; i < nN; ++i)
{
pg = HalfPlane(pg, vp[i], vp[(i + 1) % nN]);
if (pg.size() == 0)
{
printf("0\n");
break;
}
}
if (pg.size())
{
printf("1\n");
}
}
return 0;
}