點在多邊形內外的判斷有兩種處理方法：射線法和轉角法

一、射線法：

• 從這一點出發，引向無窮遠點的一條射線，根據交點情況確定點的位置
• 特點：特殊情況不易處理

以要判斷的點為起點，任做一條射線，計算該射線與多邊形的交點的數目

若有偶數個交點，則點在多邊形外；否則，點在多邊形內

若與線段所在的端點處重合或相交，則要進行復雜的判斷；此時可另取一條射線

二、轉角法：

• 計算多邊形每條邊的轉角，最后相消為0，則點在多邊形內部，否則點在多邊形外部
• 特點：三角形運算時間開銷大

把多邊形每條邊的轉角加起來：如果是360度，則點在多邊形內；如果是0度，點在多邊形外；如果是180度，則點在多邊形邊上；

直接求角度要用反三角函數，精度差且費時

如果是凸多邊形，就用叉積

例題：POJ 1410 Intersection 判斷線段交和點在矩形內?

#include <iostream> #include <stdio.h> #include <string.h> #include <algorithm> #include <queue> #include <map> #include <vector> #include <set> #include <string> #include <math.h>using namespace std; const double eps = 1e-8; int sgn(double x) {if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1; } struct Point {double x,y;Point(){}Point(double _x,double _y){x = _x;y = _y;}Point operator -(const Point &b)const{return Point(x - b.x,y - b.y);}//叉積double operator ^(const Point &b)const{return x*b.y - y*b.x;}//點積double operator *(const Point &b)const{return x*b.x + y*b.y;}//繞原點旋轉角度B（弧度值），后x,y的變化void transXY(double B){double tx = x,ty = y;x = tx*cos(B) - ty*sin(B);y = tx*sin(B) + ty*cos(B);} }; struct Line {Point s,e;double k;Line(){}Line(Point _s,Point _e){s = _s;e = _e;k = atan2(e.y - s.y,e.x - s.x);}//兩條直線求交點，//第一個值為0表示直線重合，為1表示平行，為2是相交//只有第一個值為2時，交點才有意義pair<int,Point> operator &(const Line &b)const{Point res = s;if(sgn((s-e)^(b.s-b.e)) == 0){if(sgn((s-b.e)^(b.s-b.e)) == 0)return make_pair(0,res);//重合else return make_pair(1,res);//平行}double t = ((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e));res.x += (e.x-s.x)*t;res.y += (e.y-s.y)*t;return make_pair(2,res);} }; //兩點間距離 double dist(Point a,Point b) {return sqrt((a-b)*(a-b)); } //判斷線段相交 bool inter(Line l1,Line l2) {returnmax(l1.s.x,l1.e.x) >= min(l2.s.x,l2.e.x) &&max(l2.s.x,l2.e.x) >= min(l1.s.x,l1.e.x) &&max(l1.s.y,l1.e.y) >= min(l2.s.y,l2.e.y) &&max(l2.s.y,l2.e.y) >= min(l1.s.y,l1.e.y) &&sgn((l2.s-l1.s)^(l1.e-l1.s))*sgn((l2.e-l1.s)^(l1.e-l1.s)) <= 0 &&sgn((l1.s-l2.s)^(l2.e-l1.s))*sgn((l1.e-l2.s)^(l2.e-l2.s)) <= 0; } //判斷點在線段上 bool OnSeg(Point p,Line L) {returnsgn((L.s-p)^(L.e-p))==0&&sgn((p.x-L.s.x)*(p.x-L.e.x))<=0&&sgn((p.y-L.s.y)*(p.y-L.e.y))<=0; }//判斷點在凸多邊形內，點形成一個凸包，而且按逆時針排序 //如果是順時針，就把<0改成>0 //點的編號：0~n-1 //返回值：-1點在凸多邊形外，0點在凸多邊形邊上，1點在凸多邊形內 int inConvexPoly(Point a,Point p[],int n) {for(int i=0;i<n;i++){if(sgn((p[i]-a)^(p[(i+1)%n]-a))<0)return -1;else if(OnSeg(a,Line(p[i],p[(i+1)%n])))return 0;}return 1; }//判斷點在任意多邊形內 //射線法，poly[]的頂點數要大于等于3，點的編號：0~n-1 //返回值 //-1：點在多邊形外 //0：點在多邊形邊界上 //1：點在多邊形內 int inPoly(Point p,Point poly[],int n) {int cnt=0;Line ray,side;ray.s=p;ray.s.y=p.y;ray.e.x=-100000000000.0;//-INF,注意取值，防止越界for(int i=0;i<n;i++){side.s=poly[i];side.e=poly[(i+1)%n];if(OnSeg(p,side)) return 0;//如果平行軸，則不考慮if(sgn(side.s.y-side.e.y)==0)continue;if(OnSeg(side.s,ray)){if(sgn(side.s.y-side.e.y)>0)cnt++;}else if(OnSeg(side.e,ray)){if(sgn(side.e.y-side.s.y)>0)cnt++;}else if(inter(ray,side))cnt++;}if(cnt%2==1)return 1;elsereturn -1; }

?

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的点在多边形内外的判断【计算几何】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。