Page 1 of 1

### 10867 - Cutting a Polygon

Posted: Fri Jul 19, 2013 4:16 pm
help I get WA many times.
what my code does is get all intersections of the line and the polygon. then sort the intersections by x. for every consecutive point, I check whether the midpoint of the line formed by the consecutive points is inside the polygon or in the perimeter of the polygon. if it is, then I just add the answer by the length of the line formed by the consecutive points.
here is my code:

Code: Select all

``````#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include<iostream>

using namespace std;

const double eps = 1e-8;
const double ep = 1e-12;
int n;
struct Point{
double x,y;
bool operator<(const Point &o) const{
double dx = x-o.x;
if(abs(dx)<eps)
return y<o.y;
return x<o.x;
}
bool operator==(const Point &o) const{
return abs(x-o.x)<eps && abs(y-o.y)<eps;
}
};

double slope(Point a, Point b){
double dx = a.x-b.x;
double dy = a.y-b.y;
if(abs(dx)<eps)return 1e20;
else return dy/dx;
}

double dist(Point a,Point b){
double dx = a.x-b.x;
double dy = a.y-b.y;
return sqrt(dx*dx+dy*dy);
}

void checkForIntersections(Point a, Point b, Point c, Point d, vector<Point> &vec){
Point p1 = a;
Point p2 = b;
Point p3 = c;
Point p4 = d;
if(b<a)
{
p1 = b;
p2 = a;
}
/*if(j!=0){
arr[j].x += 10*eps;
arr[j].y +=10*eps;
}*/
if(d<c){
p3 = d;
p4 = c;
}
Point ans;
double minx = min(p3.x,p4.x);
double maxx = max(p3.x,p4.x);
double miny = min(p3.y,p4.y);
double maxy = max(p3.y,p4.y);
double minx2 = min(p1.x,p2.x);
double maxx2 = max(p1.x,p2.x);
double miny2 = min(p1.y,p2.y);
double maxy2 = max(p1.y,p2.y);
if(p1.x-p2.x == 0 && p3.y-p4.y == 0){
ans.x = p1.x; ans.y = p3.y;
}
else if(p3.x-p4.x == 0 && p1.y-p2.y == 0){
ans.x = p3.x; ans.y = p1.y;
}
else {
double D = (p1.x-p2.x) * (p3.y-p4.y)
- (p1.y-p2.y) * (p3.x-p4.x);
if(abs(D)<eps){
if(abs(slope(p3,p2)-slope(p3,p4))<eps){
if(p3<p1)
ans = p1;
else
ans = p3;
Point ans2;
if(p4<p2)
ans2 = p4;
else
ans2 = p2;
//if(j!=0 || !(ans==a))
if(ans<ans2 || ans==ans2){
vec.push_back(ans);

vec.push_back(ans2);
}

//printf("zero %.3f %.3f %.3f %.3f inside %.3f %.3f %.3f %.3f\n",ans.x,ans.y,ans2.x,ans2.y,c.x,c.y,d.x,d.y);
}

return;
}
else{
double A = p1.x * p2.y - p1.y * p2.x;
double B = p3.x * p4.y - p3.y * p4.x;
ans.x = (A*(p3.x-p4.x)
- B*(p1.x-p2.x))/D;
ans.y = (A*(p3.y-p4.y)
- B*(p1.y-p2.y))/D;
}
}
if(ans.x+eps>=minx && ans.x<=maxx+eps && ans.y+eps>=miny && ans.y <=maxy+eps && ans.x+eps>=minx2 && ans.x<=maxx2+eps && ans.y+eps>=miny2 && ans.y <=maxy2+eps){
vec.push_back(ans);
}
//else printf("%.3f %.3f did not intersect\n",ans.x,ans.y);

}

bool inside(Point o, Point poly[]) {
int j=n-1;
bool oddNodes=false;
for (int i=0; i<n; i++) {
if ((poly[i].y< o.y && poly[j].y>=o.y
||   poly[j].y< o.y && poly[i].y>=o.y)
&&  (poly[i].x<=o.x || poly[j].x<=o.x)) {
oddNodes^=(poly[i].x+(o.y-poly[i].y)/(poly[j].y-poly[i].y)*(poly[j].x-poly[i].x)<o.x); }
j=i;
}
return oddNodes;
}

bool inPerimeter(Point o, Point p[]){

for(int i = 0;i<n;i++){
Point a = p[i];
Point b = p[(i+1)%n];
double minx = min(a.x,b.x);
double maxx = max(a.x,b.x);
double miny = min(a.y,b.y);
double maxy = max(a.y,b.y);
if(o.x+eps>=minx && o.x<=maxx+eps && o.y+eps>=miny && o.y<=maxy+eps && abs(slope(a,o)-slope(b,o))<eps)
return true;
}
return false;
}

int main(){
int m;
while(scanf("%d %d\n",&n,&m) &&n){
Point arr[n];
for(int i = 0;i<n;i++)
scanf("%lf %lf\n",&arr[i].x,&arr[i].y);
for(int i = 0;i<m;i++){
vector<Point> vec;
Point a,b;
scanf("%lf %lf %lf %lf\n",&a.x,&a.y,&b.x,&b.y);
vec.push_back(a);
vec.push_back(b);
for(int j = 0;j<n;j++){
Point c = arr[j];
Point d = arr[(j+1)%n];

checkForIntersections(a,b,c,d,vec);
}
int k = vec.size();
double ans = 0.0;
sort(vec.begin(),vec.end());
//printf("\n");
//or(int j = 0;j<k;j++)
//	printf("vec: %.3f %.3f\n",vec.at(j).x,vec.at(j).y);
for(int j = 0;j<k-1;j++){
//printf("vec: %.3f %.3f\nvec: %.3f %.3f\n",vec.at(j).x,vec.at(j).y,vec.at(j+1).x,vec.at(j+1).y);
Point xx = vec.at(j);
Point yy = vec.at(j+1);
Point mid;
mid.x = 0.5*(xx.x+yy.x);
mid.y = 0.5*(xx.y+yy.y);
if(inside(mid,arr) || inPerimeter(mid,arr))
ans+=dist(vec.at(j),vec.at(j+1));
}
printf("%.3f\n",ans+eps);
}
}
}
``````

### Re: 10867 - Cutting a Polygon

Posted: Thu Jul 25, 2013 2:27 am
You could be having precision errors. To see if a floating point value is equal to 0, don't use value == 0, use something like fabs(value) < EPS. Also try this method for finding the intersection point:
http://en.wikipedia.org/wiki/Line-line_intersection