Polyline Simplification (计算几何)
程序员文章站
2022-04-02 17:46:48
...
Polyline Simplification
时间限制: 5 Sec 内存限制: 128 MB提交: 35 解决: 11
[提交][状态][讨论版][命题人:admin]
题目描述
Mapping applications often represent the boundaries of countries, cities, etc. as polylines, which are connected sequences of line segments. Since fine details have to be shown when the user zooms into the map,these polylines often
contain a very large number of segments. When the user zooms out, however, these fine details are not important and it is wasteful to process and draw the polylines with so many segments. In this problem, we consider a particular polyline simplification algorithm
designed to approximate the original polyline with a polyline with fewer segments.
A polyline with n segments is described by n + 1 points p0 = (x0, y0),... , pn = (xn, yn), with the ith line segment being . The polyline can be simplified by removing an interior point pi (1≤i≤n-1),so that the line segments are replaced by the line segment . To select the point to be removed, we examine the area of the triangle formed by pi-1, pi, and pi+1 (the area is 0 if the three points are colinear), and choose the point pi such that the area of the triangle is smallest. Ties are broken by choosing the point with the lowest index. This can be applied again to the resulting polyline, until the desired number m of line segments is reached.
Consider the example below.
The original polyline is shown at the top. The area of the triangle formed by p2, p3, and p4 is considered (middle), and p3 is removed if the area is the smallest among all such triangles. The resulting polyline after p3 is removed is shown at the bottom.
A polyline with n segments is described by n + 1 points p0 = (x0, y0),... , pn = (xn, yn), with the ith line segment being . The polyline can be simplified by removing an interior point pi (1≤i≤n-1),so that the line segments are replaced by the line segment . To select the point to be removed, we examine the area of the triangle formed by pi-1, pi, and pi+1 (the area is 0 if the three points are colinear), and choose the point pi such that the area of the triangle is smallest. Ties are broken by choosing the point with the lowest index. This can be applied again to the resulting polyline, until the desired number m of line segments is reached.
Consider the example below.
The original polyline is shown at the top. The area of the triangle formed by p2, p3, and p4 is considered (middle), and p3 is removed if the area is the smallest among all such triangles. The resulting polyline after p3 is removed is shown at the bottom.
输入
The first line of input contains two integers n (2≤n≤200 000) and m (1≤m < n). The next n+1 lines specify p0,..., pn.
Each point is given by its x and y coordinates which are integers between -5000 and 5000 inclusive. You may assume that the given points are strictly increasing in lexicographical order. That is, xi <
xi+1, or xi = xi+1 and
yi < yi+1 for all 0≤i < n.
输出
Print on the kth line the index of the point removed in the kth step of the algorithm described above (use the index in the original polyline).
样例输入
10 7
0 0
1 10
2 20
25 17
32 19
33 5
40 10
50 13
65 27
75 22
85 17
样例输出
1
9
6
简单的题意,简单的思路,debug一天,就是这么简单。
题意是 有n条边,n+1个点,由点Pi-1,Pi,Pi+1组成的若干个三角形,每次删除面积最小的三角形的中间点,最后剩下m条边,问每次删除的点是哪些。
首先,很容易想到把所有的点压入优先队列,每一次取最小的点,但是去除一个点之后可能会产生两个新的三角形,这样需要两个数组来记录前驱和后继,然后新的问题出现,不只是加入了两个新点,还会影响到另外的两个三角形,而且这两个三角形要直接pop掉,所以再在结构体里面加两个标记位,来记录前驱后继是否相同,不相同就pop掉,最后得到结果。
代码实现:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5+10;
int n,m;
int pre[N],nxt[N];
struct Point{
double x,y;
Point(double x=0, double y =0):x(x),y(y){}
}p[N];
int vis[N];
struct Area{
double area;
int indx,l,r;
Area (int l,int mid,int r,double area):l(l),indx(mid),r(r),area(area){};
friend bool operator < (Area A, Area B){
if(A.area==B.area)
return A.indx>B.indx;
return A.area > B.area;
}
};
priority_queue<Area>pq;
typedef Point Vector;
Vector operator - (Vector A, Vector B){
return Vector(A.x-B.x,A.y-B.y);
}
double Cross(Vector A, Vector B){
return A.x*B.y-A.y*B.x;
}
double Area2(Point A, Point B, Point C){
return Cross(B-A,C-A);
}
vector <int> ans;
int main()
{
int i,j,k;
scanf("%d%d",&n,&m);
for(i = 1; i <= n+1; i ++)
scanf("%lf%lf",&p[i].x,&p[i].y);
for(i=1;i<=n+1;i++)
{
pre[i]=i-1;
nxt[i]=i+1;
}
nxt[0]=1;
for(i = 2; i <= n; i ++)
{
double s=fabs(Area2(p[i-1],p[i],p[i+1]));
Area area1(i-1,i,i+1,s);
pq.push(area1);
}
int t=n-m;
while(t)
{
Area tt=pq.top();
pq.pop();
if(vis[tt.indx]||tt.l!=pre[tt.indx]||tt.r!=nxt[tt.indx])
continue;
t--;
vis[tt.indx]=1;
i=tt.indx;
pre[nxt[i]]=pre[i];
nxt[pre[i]]=nxt[i];
ans.push_back(i);
int temp=pre[tt.indx];
if(temp>1)
pq.push(Area{pre[temp],temp,nxt[temp],fabs(Area2(p[temp],p[pre[temp]],p[nxt[temp]]))});
temp=nxt[tt.indx];
if(temp<=n)
pq.push(Area{pre[temp],temp,nxt[temp],fabs(Area2(p[temp],p[pre[temp]],p[nxt[temp]]))});
}
for(i=0;i<ans.size();i++)
{
printf("%d\n",ans[i]-1);
}
return 0;
}
/*
10 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
*/
推荐阅读
-
几何画板怎么通过度量计算直线或曲线的方程?
-
BZOJ1278: 向量vector(计算几何 随机化乱搞)
-
云计算420亿美元规模 安防应用占据几何?
-
51nod 1298 圆与三角形——计算几何
-
计算几何与计算机图形学方面的一些资源及源代码 MatlabFortranC#C++C
-
计算几何与计算机图形学方面的一些资源及源代码 MatlabFortranC#C++C
-
点到线段的距离 计算几何
-
计算机图形与OpenGL学习七(三维几何变换1.三维平移与三维坐标轴旋转)
-
计算几何(空间几何 + 三分) - Dome of Circus - UVA 1473
-
计算机图形学(四)几何变换_5_三维空间的几何变换_1_三维平移