基于Weiler-Atherton算法的Polygon_Clip
用一个多边形去裁剪另一个多边形，分为两种情况
- 内裁剪：内裁剪即通常意义上的裁剪，取图元位于窗口之内的部分，结果为A∩B。
- 外裁剪：外裁剪取图元位于窗口之外的部分，结果为A－B。
Sutherland－Hodgeman算法解决了裁剪窗口为凸多边形窗口的问题，但一些应用需要涉及任意多边形窗口（含凹多边形窗口）的裁剪。
例：如下图形，但正确的裁剪结果应该为最右边的图。
在算法中，裁剪窗口、被裁剪多边形可以是任意多边形：凸的、凹的（内角大于180o）、甚至是带有内环的（子区），见下图。
P为主多边形，Q为裁剪多边形。
由于多边形构成一个封闭的区域，所以，如果被裁剪多边形和裁剪窗口有交点，则交点成对出现。这些交点分成两类：
一类称 “进” 点，即被裁剪多边形由此点进入裁剪窗口，如图中 J1,J3,J5,J7,J9 ,J11这几个点； 一类称 “出” 点，即被裁剪多边形由此点离开裁剪窗口，如图中 J0,J2,J4,J6,J8 ,J10这几个点 。
比如选择J7为起始点，随后进行遍历。
默认技能：求两条线段的交点
namespace GetLineCross {
bool IsRectCross(const Point &p1, const Point &p2, const Point &q1, const Point &q2) {
bool ret = min(p1.x, p2.x) <= max(q1.x, q2.x) &&
min(q1.x, q2.x) <= max(p1.x, p2.x) &&
min(p1.y, p2.y) <= max(q1.y, q2.y) &&
min(q1.y, q2.y) <= max(p1.y, p2.y);
return ret;
}
bool IsLineSegmentCross(const Point &pFirst1, const Point &pFirst2, const Point &pSecond1, const Point &pSecond2) {
long line1, line2;
line1 = pFirst1.x * (pSecond1.y - pFirst2.y) +
pFirst2.x * (pFirst1.y - pSecond1.y) +
pSecond1.x * (pFirst2.y - pFirst1.y);
line2 = pFirst1.x * (pSecond2.y - pFirst2.y) +
pFirst2.x * (pFirst1.y - pSecond2.y) +
pSecond2.x * (pFirst2.y - pFirst1.y);
if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
return false;
line1 = pSecond1.x * (pFirst1.y - pSecond2.y) +
pSecond2.x * (pSecond1.y - pFirst1.y) +
pFirst1.x * (pSecond2.y - pSecond1.y);
line2 = pSecond1.x * (pFirst2.y - pSecond2.y) +
pSecond2.x * (pSecond1.y - pFirst2.y) +
pFirst2.x * (pSecond2.y - pSecond1.y);
if (((line1 ^ line2) >= 0) && !(line1 == 0 && line2 == 0))
return false;
return true;
}
bool GetCrossPoint(const Point &p1, const Point &p2, const Point &q1, const Point &q2, int &x, int &y) {
if (IsRectCross(p1, p2, q1, q2)) {
if (IsLineSegmentCross(p1, p2, q1, q2)) {
//求交点
long tmpLeft, tmpRight;
tmpLeft = (q2.x - q1.x) * (p1.y - p2.y) - (p2.x - p1.x) * (q1.y - q2.y);
tmpRight = (p1.y - q1.y) * (p2.x - p1.x) * (q2.x - q1.x) + q1.x * (q2.y - q1.y) * (p2.x - p1.x) -
p1.x * (p2.y - p1.y) * (q2.x - q1.x);
x = (int) ((double) tmpRight / (double) tmpLeft);
tmpLeft = (p1.x - p2.x) * (q2.y - q1.y) - (p2.y - p1.y) * (q1.x - q2.x);
tmpRight = p2.y * (p1.x - p2.x) * (q2.y - q1.y) + (q2.x - p2.x) * (q2.y - q1.y) * (p1.y - p2.y) -
q2.y * (q1.x - q2.x) * (p2.y - p1.y);
y = (int) ((double) tmpRight / (double) tmpLeft);
return true;
}
}
return false;
}
}错误案例：认为相对应的入点和出点都在同一条边（都在主多边形或者都在裁剪多边形？）
如下图：
由于入点和出点一定在某一个多边形的一条边上，那在哪一条我们不清楚，所以：
- 先固定主多边形的一条边，扫描裁剪多边形
- 得到交点之后，这些交点一定在固定主多边形的那条边上，所以可以用链表存储顺序后插入
- 反之，先固定裁剪多边形的一条边，扫描主多边形即可
注意：先判断起始点是在另一个多边形外部还是内部（待修改）。
上述处理之后
==坐标都是int，所以会有点误差。==
-
给交点打上标记后顶点排序
-
遍历主多边形顶点表，遇到交点按照入、出标记交点
-
把第一个遇到的交点设为入点，这样它之后的遍历会正确的。
==但是，凸多边形可以排序，思考了很久，凹多边形貌似目前我没有办法==
- 随机在主多边形内找一个没有被遍历到的入点
- 如果当前点是入点，遍历主多边形，否则遍历裁剪多边形
- 当遇到相对应的入/出点时，通过“双向指针”改变遍历方向
- 遍历过程中遇到的点存储到ans里
vector<polygon> ans(1); // 裁剪结果多边形顶点表
map<pair<int, int>, int> vis;
int num = 0;
// 遍历
while(true) {
if(mapPoint.empty()) break ;
// 随机一个入点为起点
int start;
for(int i = 0;i < qv.size(); i++) {
if(vis[pair<int, int>{qv[i].x, qv[i].y}] == 1) continue ;
if(mapPoint[pair<int, int>{qv[i].x, qv[i].y}] == 1) {
start = i;
break ;
}
else mapPoint.erase(pair<int, int>{qv[i].x, qv[i].y});
}
// 从入点start开始走
opt = 0;
while(true) {
if((opt == 0 && vis[{qv[start].x, qv[start].y}] == 1) || (opt == 1 && vis[{pv[start].x, pv[start].y}] == 1)) {
ans.resize(ans.size() + 1);
num++;
break ;
}
if(opt == 0) {
ans[num].push_back(Point{qv[start].x, qv[start].y});
mapPoint.erase({qv[start].x, qv[start].y});
vis[{qv[start].x, qv[start].y}] = 1;
}
else {
ans[num].push_back(Point{pv[start].x, pv[start].y});
mapPoint.erase({pv[start].x, pv[start].y});
vis[{pv[start].x, pv[start].y}] = 1;
}
int nxt = (start + 1);
if(opt == 0) nxt %= (int)qv.size();
else nxt %= (int)pv.size();
if(opt == 0) { // 入点走主多边形
if(qv[nxt].flag == 2) {
opt ^= 1;
start = mapNextQ[nxt];
}
else start = nxt;
}
else { // 出点走裁剪多边形
if(pv[nxt].flag == 1) {
opt ^= 1;
start = mapNextP[nxt];
}
else start = nxt;
}
}
}
参考链接：