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);
}
}
}