یکی از مسله‌های مهم در زمینه الگوریتم‌های هندسی و سایر مسایل مربوط به هندسه ترکیبیاتی ، مسله بررسی داخل بودن یک نقطه مانند $P$ در چند ضلعی ساده(چند ضلعی که اضلاعش هم‌دیگر را قطع نمی‌کنند) $Q$ می باشد.یکی از روش های ساده برای حل این مسله رسم نیم‌خط دلخواهی مانند $\overrightarrow{Px}$ و بررسی تعداد نقاط تقاطع آن با اضلاع $Q$ است. در صورتی که این تعداد زوج باشد $P$ درون $Q$ قرار دارد و در صورتی که این تعداد فرد باشد $P$ بیرون $Q$ قرار دارد.اثبات این مطلب به عهده خواننده! .

مرتبه زمانی الگوریتم از$O(n)$ و حافظه مصرف شده از $O(1)$ می‌باشد.

semiLine_soul.c

#include <iostream>
#define MIN(x,y) (x < y ? x : y)
#define MAX(x,y) (x > y ? x : y)
#define INSIDE 0
#define OUTSIDE 1
 
typedef struct {
   double x,y;
} Point;
 
int InsidePolygon(Point *polygon,int N,Point p)
{
  int counter = 0;
  int i;
  double xinters;
  Point p1,p2;
 
  p1 = polygon[0];
  for (i=1;i<=N;i++) {
    p2 = polygon[i % N];
    if (p.y > MIN(p1.y,p2.y)) {
      if (p.y <= MAX(p1.y,p2.y)) {
        if (p.x <= MAX(p1.x,p2.x)) {
          if (p1.y != p2.y) {
            xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
            if (p1.x == p2.x || p.x <= xinters)
              counter++;
          }
        }
      }
    }
    p1 = p2;
  }
 
  if (counter % 2 == 0)
    return(OUTSIDE);
  else
    return(INSIDE);
}

در این روش حول نقطه $P$ تمام اضلاع را مشاهده کرده و همه زوایای به‌دست آمده را به صورت جهت دار با هم جمع می‌زنیم.در صورتی مجموع $2\pi$ شود نقطه داخل چند ضلعی قرار دارد و در صورتی که مجموع $0$ شود نقطه خارج چندضلعی قرار دارد.

‌‌Angle_Soul.c

#include <iostream>
 
typedef struct {
   int h,v;
} Point;
 
int InsidePolygon(Point *polygon,int n,Point p)
{
   int i;
   double angle=0;
   Point p1,p2;
 
   for (i=0;i<n;i++) {
      p1.h = polygon[i].h - p.h;
      p1.v = polygon[i].v - p.v;
      p2.h = polygon[(i+1)%n].h - p.h;
      p2.v = polygon[(i+1)%n].v - p.v;
      angle += Angle2D(p1.h,p1.v,p2.h,p2.v);
   }
 
   if (ABS(angle) < PI)
      return(FALSE);
   else
      return(TRUE);
}
 
/*
   Return the angle between two vectors on a plane
   The angle is from vector 1 to vector 2, positive anticlockwise
   The result is between -pi -> pi
*/
double Angle2D(double x1, double y1, double x2, double y2)
{
   double dtheta,theta1,theta2;
 
   theta1 = atan2(y1,x1);
   theta2 = atan2(y2,x2);
   dtheta = theta2 - theta1;
   while (dtheta > PI)
      dtheta -= TWOPI;
   while (dtheta < -PI)
      dtheta += TWOPI;
 
   return(dtheta);
}

- پیاده سازی اولیه

- پیاده سازی دیگر

خواننده‌ی گرامی، لطفا در صورت داشتن پیشنهاد یا مشاهده‌ی مشکل (علمی، تایپی و …) در این صفحه، به ما اطلاع دهید: