计算几何——扫描线算法

面对一个几何图形&＃xff0c;计算机通过向某一个方向进行单线扫描&＃xff0c;进行图形处理的方式叫做扫描线算法。

事件和事件处理程序

扫除线算法中最重要的就是对事件&＃xff08;Event&＃xff09;的处理。一个事件定义为当扫除线碰到点、边界、线等产生的进入或退出事件。

例如下图&＃xff1a;

当扫描线碰到某一个矩形的左边界时将会产生一个进入事件&＃xff0c;之后处理程序将对这个进入事件进行处理。

又或者当扫描线碰到某一个矩形的右边界时将会产生一个退出事件&＃xff0c;之后处理程序将对这个退出事件进行处理。

一般的&＃xff0c;我们将整个事件列表中的事件进行按照扫除线的扫描顺序进行排序&＃xff0c;之后处理程序将会依次处理所有事件&＃xff0c;而事件处理程序才是扫描线算法的核心。

天际线问题

LeetCode 218

the-skyline-problem

#include #define FR freopen("in.txt", "r", stdin)typedef long long ll;
using namespace std;struct Event
{int x;int height;bool start;bool operator<(const Event &o) const{if (x &＃61;&＃61; o.x){return height < o.height;}else{return x < o.x;}}
};class Solution
{
public:vector<vector<int>> getSkyline(vector<vector<int>> &buildings){// 构建事件列表vector<Event> events;for (vector<int> item : buildings){events.push_back({item[0], item[2], true});events.push_back({item[1], item[2], false});}vector<vector<int>> ans;// 排序事件sort(events.begin(), events.end());multiset<int> heights;heights.insert(0);int maxHeight &＃61; 0;for (Event event : events){if (event.start) // 如果是一个开始事件{heights.insert(event.height);if (event.height > maxHeight){maxHeight &＃61; event.height;if (!ans.empty() && ans.back()[0] &＃61;&＃61; event.x)ans.pop_back();vector<int> point;point.push_back(event.x);point.push_back(event.height);ans.push_back(point);}}else // 否则为结束事件{heights.erase(heights.find(event.height));if (maxHeight &＃61;&＃61; event.height){if (heights.count(event.height)){continue;}if (!ans.empty() && ans.back()[0] &＃61;&＃61; event.x)ans.pop_back();maxHeight &＃61; *heights.rbegin();vector<int> point;point.push_back(event.x);point.push_back(maxHeight);ans.push_back(point);}}}return ans;}
};


相交面积问题

LeetCode 391

求出三个面积&＃xff1a;

1. 极小包围矩形的面积
2. 所有矩形的面积和
3. 所有矩形组成的平面图形的面积

如果这三个面积相等返回True。

1和2是好处理的&＃xff0c;3需要使用扫面线和线段树求解。

using ll &＃61; long long;int LT(int x)
{return x << 1;
}
int RT(int x)
{return (x << 1) | 1;
}struct Node
{ll len;int cnt;ll rlen;
};
struct Event
{ll x;int l;int r;bool enter;
};vector<int> decre;struct SegmentTree
{vector<Node> t;void buildTree(int i, int l, int r){t[i].cnt &＃61; 0;t[i].len &＃61; 0;t[i].rlen &＃61; decre[r] - decre[l];if (l !&＃61; r - 1){int mid &＃61; (l &＃43; r) / 2;buildTree(LT(i), l, mid);buildTree(RT(i), mid, r);}}void cover(int i, int l, int r, int L, int R){if (l >&＃61; R || r <&＃61; L)return;if (l >&＃61; L && r <&＃61; R){t[i].cnt&＃43;&＃43;;t[i].len &＃61; t[i].rlen;return;}int mid &＃61; (l &＃43; r) / 2;cover(LT(i), l, mid, L, R);cover(RT(i), mid, r, L, R);if (!t[i].cnt)t[i].len &＃61; t[LT(i)].len &＃43; t[RT(i)].len;}void uncover(int i, int l, int r, int L, int R){if (l >&＃61; R || r <&＃61; L)return;if (l >&＃61; L && r <&＃61; R){t[i].cnt--;if (!t[i].cnt)t[i].len &＃61; l &＃61;&＃61; r - 1 ? 0 : t[LT(i)].len &＃43; t[RT(i)].len;return;}int mid &＃61; (l &＃43; r) / 2;uncover(LT(i), l, mid, L, R);uncover(RT(i), mid, r, L, R);if (!t[i].cnt)t[i].len &＃61; t[LT(i)].len &＃43; t[RT(i)].len;}ll getLen(){return t[1].len;}
};class Solution
{
public:ll comb_area(vector<vector<int>> &rectangles){for (vector<int> &r : rectangles){decre.push_back(r[1]);decre.push_back(r[3]);}sort(decre.begin(), decre.end());decre.erase(unique(decre.begin(), decre.end()), decre.end());auto find_id &＃61; [&](int y) -> int{return lower_bound(decre.begin(), decre.end(), y) - decre.begin();};vector<Event> vec;for (vector<int> &r : rectangles){vec.push_back((Event){r[0],find_id(r[1]),find_id(r[3]),true});vec.push_back((Event){r[2],find_id(r[1]),find_id(r[3]),false});}sort(vec.begin(), vec.end(), [](Event a, Event b){ return a.x < b.x; });SegmentTree st;st.t.resize(decre.size() * 4);int R &＃61; decre.size() - 1;st.buildTree(1, 0, R);ll lasx &＃61; vec[0].x;ll ans &＃61; 0;for (Event e : vec){int x &＃61; e.x;int l &＃61; e.l;int r &＃61; e.r;bool enter &＃61; e.enter;if (x !&＃61; lasx){ans &＃43;&＃61; st.getLen() * (x - lasx);lasx &＃61; x;}if (enter)st.cover(1, 0, R, l, r);elsest.uncover(1, 0, R, l, r);}return ans;}bool isRectangleCover(vector<vector<int>> &rectangles){vector<ll> bound(4);for (int i &＃61; 0; i < 4; i&＃43;&＃43;){bound[i] &＃61; (*min_element(rectangles.begin(), rectangles.end(), [&](const vector<int> &a, const vector<int> &b){if (i <&＃61; 1)return a[i] < b[i];elsereturn a[i] > b[i];}))[i];}ll area &＃61; abs(bound[0] - bound[2]) * abs(bound[1] - bound[3]);// 统计面积ll rarea &＃61; 0;for (vector<int> &r : rectangles)rarea &＃43;&＃61; abs(0ll &＃43; r[0] - r[2]) * abs(0ll &＃43; r[1] - r[3]);ll carea &＃61; comb_area(rectangles);return area &＃61;&＃61; rarea && area &＃61;&＃61; carea;}
};