Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //2D polygon filling (arbitrary poly; full and partial pixels are counted. handles slivers. x incremened ++)
- //nasarouf@cs.ubc.ca
- // old, untested code
- #include <iostream>
- #include <algorithm>
- #include <cmath>
- #include <map>
- using namespace std;
- #define MAX 100
- #define X first
- #define YY second
- #define A first
- #define B second
- typedef pair<int,int> PII;
- typedef pair<PII,PII> Seg;
- pair<double,double> y[MAX];
- int Y[MAX];
- PII p[MAX];
- Seg seg[MAX],li[MAX];
- map<int,int> m;
- int main() {
- int x, i, it, n, a, lin, lit, j, segn;
- Seg s, tmp;
- while ((cin >> n) && n) {
- for (i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
- segn = 0;
- m.clear();
- for (i = j = 0; i < n; i++) {
- if (p[i].first == p[(i + 1) % n].first) continue;
- else if (p[i] < p[(i + 1) % n]) seg[j++] = (make_pair(p[i], p[(i + 1) % n]));
- else seg[j++] = (make_pair(p[(i + 1) % n], p[i]));
- }
- segn = j;
- sort(seg, seg + segn);
- a = 0;
- x = seg[0].first.first;
- it = 0;
- lin = 0;
- while (it < segn || lin) {
- for (i = 0, lit = 0; lit < lin; lit++, i++)
- y[i] = make_pair(li[lit].A.YY + (double)(li[lit].B.YY - li[lit].A.B)*(x - 1 - li[lit].A.X) / (double)(li[lit].B.X - li[lit].A.X),
- li[lit].A.YY + (double)(li[lit].B.YY - li[lit].A.YY)*(x - li[lit].A.X) / (double)(li[lit].B.X - li[lit].A.X));
- n = i;
- sort(y, y + n);
- for (i = 0; i < n; i += 2) {
- Y[i + 1] = (int)(ceil(max(y[i + 1].first, y[i + 1].second)));
- Y[i] = floor(min(y[i].first, y[i].second));
- }
- for (i = 0; i < n; i += 2) {
- if (i && Y[i] < Y[i - 1]) Y[i] = Y[i - 1];
- if (Y[i + 1] < Y[i]) Y[i + 1] = Y[i];
- a += Y[i + 1] - Y[i];
- }
- if (m[x])
- for (i = 0; i < lin; )
- if (li[i].second.first == x) swap(li[i], li[--lin], tmp);
- else i++;
- while (it < segn && seg[it].first.first == x) {
- li[lin++] = seg[it];
- m[seg[it].second.first] = 1;
- it++;
- }
- x++;
- }
- cout << a << endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement