判断点是否在多边形内的5种方法

发布网友发布时间：2022-05-05 00:58

共2个回答

懂视网时间：2022-05-05 05:20

本篇文章给大家带来的内容是关于如何理解xyz的判断点在凸包内模板，有一定的参考价值，有需要的朋友可以参考一下，希望对你有所帮助。

int n,m,tot;
struct point 
{
 double x,y;
}p[100000],a[100000],ss;
bool cmp(point A,point B)
{
 if(A.x!=B.x)
 return A.x<B.x;
 return A.y<B.y;
}
point operator -(point A,point B)
{
 point c;
 c.x=A.x-B.x;
 c.y=A.y-B.y;
 return c;
}
double cross(point A,point B)
{
 return A.x*B.y-B.x*A.y;
}
void dopack()
{
 tot=0;
 for(int i=1;i<=n;i++)
 {
 while(tot>1&&cross(p[tot-1]-p[tot-2],a[i]-p[tot-2])<=0)tot--;
 p[tot++]=a[i];
 }
 int k=tot;
 for(int i=n-1;i>0;i--)
 {
 while(tot>k&&cross(p[tot-1]-p[tot-2],a[i]-p[tot-2])<=0)tot--;
 p[tot++]=a[i];
 }
 if(n>1)tot--;
}
bool check(point A)
{
 int l=1,r=tot-2,mid;
 while(l<=r)
 {
 mid=(l+r)>>1;
 double a1=cross(p[mid]-p[0],A-p[0]);
 double a2=cross(p[mid+1]-p[0],A-p[0]);
 if(a1>=0&&a2<=0)
 {
  if(cross(p[mid+1]-p[mid],A-p[mid])>=0)return true;
  return false;
 }
 else if(a1<0)
 {
  r=mid-1;
 }
 else 
 {
  l=mid+1;
 }
 }
 return false;
}

热心网友时间：2022-05-05 02:28

0?1:-1;}struct point{double x,y;bool point_is_inside() //叉积判断点在凸包内部！只针对于凸多边形。圆心连接每一条边的端点得到的叉积必须同向。以此可以延伸出面积法判定点是否在凸包内部。这两种方法都局限于在凸多边形{point p1;p1.x=pegx,p1.y=pegy;