====== بررسی داخل بودن نقطه در چند ضلعی  ======

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






===== پیچیدگی‌ الگوریتم =====

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





===== پیاده‌سازی اولیه =====

<code c 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);
}
</code>

===== پیاده‌سازی دیگر =====

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





<code c ‌‌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);
}

</code>





===== مراجع =====




- [[http://bbs.dartmouth.edu/~fangq/MATH/download/source/Determining%20if%20a%20point%20lies%20on%20the%20interior%20of%20a%20polygon.htm|پیاده سازی اولیه]]

----------------

- [[http://bbs.dartmouth.edu/~fangq/MATH/download/source/Determining%20if%20a%20point%20lies%20on%20the%20interior%20of%20a%20polygon.htm|پیاده سازی دیگر]]  

----------------



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


~~DISCUSSION~~