Определение принадлежности точки многоугольнику.

point.jpg

Многоугольник (не обязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границ. Определить лежит ли заданная точка внутри данного многоугольника.

Входные данные:
- Координаты вершин, заданные в порядке обхода его границы по часовой стрелке
- Число вершин в многоугольнике
- Координаты данной точки
Выходные данные:
- Принадлежность точки многоугольнику

Решение.
В основе данного алгоритма лежит идея подсчёта количества пересечений горизонтального луча, исходящего из данной точки со сторонами многоугольника. Точка не принадлежит многоугольнику, если количество пересечений - четно.

1. Будем перебирать все соседние пары вершин А[n] и A[n+1] многоугольника.
Если точка по у-кординате лежит между текущими вершинами, то мы можем пустить параллельный оси Х луч в одну из сторон.
2. Проверяем пересечение луча с отрезком.

Для этого:
-составим уравнение прямой, проходящей через 2 точки А[n] и A[n+1]:

( X - A[n].X ) / ( А[n+1].X - A[n].X ) = ( Y - A[n].Y ) / ( А[n+1].Y - A[n].Y )

-выразим X из уравнения.

X = ( Y - A[n].Y ) / ( А[n+1].Y - A[n].Y ) * ( А[n+1].X - A[n].X ) + A[n].X

-подставим вместо X, Y координаты нашей точки.
Если

X > ( Y - A[n].Y ) / ( А[n+1].Y - A[n].Y ) * ( А[n+1].X - A[n].X ) + A[n].X,

точка находится правее (левее, если обход многоугольника против часовой стрелки) по X от отрезка А[n] A[n+1], и у нас есть пересечение.

3. Если общее количество пересечений – четное число, точка лежит снаружи многоугольника.
(На рисунке направление обхода многоугольников – по часовой стрелке).

Программа - визуализатор

#include <windows.h>
#include <stdio.h>
#include <math.h>
#define N 200
 
struct Point
{
	int x, y;
};
 
HWND hMainWnd;
long FAR PASCAL MainWndProc (HWND hwnd, UINT iMsg, WPARAM wParam, LPARAM lParam);
bool isIntersect( Point p[], int size, Point s );
 
int PASCAL WinMain(	HINSTANCE hInstance,
			HINSTANCE hPrevInstance, 	
			LPSTR lpszCmdLine, int nCmdShow)					     
{
	WNDCLASS WC;
	MSG msg;  				
	if(!hPrevInstance)
	{
		WC.style = NULL; 		
		WC.lpfnWndProc = MainWndProc;	
		WC.cbClsExtra = 0;		
		WC.cbWndExtra = 0;		
		WC.hInstance = hInstance;
		WC.hIcon = LoadIcon(NULL, IDI_APPLICATION),
		WC.hCursor = LoadCursor(NULL, IDC_ARROW);
		WC.hbrBackground = (HBRUSH)GetStockObject(WHITE_BRUSH);
		WC.lpszMenuName = NULL;			
		WC.lpszClassName = "MainWndClass";
		if(!RegisterClass(&WC))
                        return FALSE;
	}
    hMainWnd = CreateWindow (
        "MainWndClass",          
        "Polygons",       
        WS_OVERLAPPEDWINDOW,     
        CW_USEDEFAULT,          
        CW_USEDEFAULT,        
        CW_USEDEFAULT,       
        CW_USEDEFAULT,       
        NULL,                 
        NULL,               
        hInstance,           
        NULL) ;		
 
	if(!hMainWnd)	return NULL;
    ShowWindow (hMainWnd, nCmdShow) ;
    UpdateWindow (hMainWnd) ;
 
    while (GetMessage (&msg, NULL, 0, 0))
    {
        TranslateMessage (&msg) ;
        DispatchMessage (&msg) ;
    }
    return msg.wParam ;
}
 
long FAR PASCAL MainWndProc (HWND hMainWnd, UINT iMsg, WPARAM wParam, LPARAM lParam)
{
	static bool isDefine;
	int i, r = 3, pt;
	static int size;
	static Point polygon[N], point;
 
    HDC         hdc ;
    PAINTSTRUCT ps ;
    RECT        rect ;
	HBRUSH hbrush, hbrushOld;
 
    switch (iMsg)
    {
    case WM_PAINT :
	    hdc = BeginPaint (hMainWnd, &ps) ;
		hbrush = (HBRUSH)CreateSolidBrush(RGB(255, 0, 0));
		hbrushOld = (HBRUSH)SelectObject(hdc, hbrush);
		GetClientRect (hMainWnd, &rect) ;
		if( size > 0)
		{
			MoveToEx(hdc, polygon[0].x, rect.top - polygon[0].y, 0);
			for(i = 1; i < size; i++)
			{
				LineTo(hdc, polygon[i].x, rect.top - polygon[i].y);
				Ellipse( hdc, polygon[i].x - r, rect.top - polygon[i].y + r, 
					polygon[i].x + r, rect.top - polygon[i].y - r );
			}
			Ellipse( hdc, polygon[0].x - r, rect.top - polygon[0].y + r, 
					polygon[0].x + r, rect.top - polygon[0].y - r );
			LineTo(hdc, polygon[0].x, rect.top - polygon[0].y);
 
			if( isDefine == true )
				Ellipse( hdc, point.x - r - 2, rect.top - point.y + r + 2, 
				point.x + r + 2, rect.top - point.y - r - 2);
		}
		SelectObject(hdc, hbrushOld);
		DeleteObject(hbrush);
	    EndPaint (hMainWnd, &ps) ;
        break;
 
	case WM_LBUTTONDOWN :
		GetClientRect (hMainWnd, &rect);
		if( isDefine == false && size < N )
		{
			polygon[size].x = LOWORD(lParam);
			polygon[size++].y = rect.top - HIWORD(lParam);
			InvalidateRect(hMainWnd, NULL, 1);
			UpdateWindow (hMainWnd) ;
		}
		break;
 
	case WM_RBUTTONDOWN :
		if( isDefine == true )
		{
			isDefine = false;
			size = 0;
 
			InvalidateRect(hMainWnd, NULL, 1);
			UpdateWindow (hMainWnd) ;
		}
		else if( isDefine == false )
		{
			GetClientRect (hMainWnd, &rect) ;
			isDefine = true;
 
			point.x = LOWORD(lParam);
			point.y = rect.top - HIWORD(lParam);
 
			InvalidateRect(hMainWnd, NULL, 0);
			UpdateWindow (hMainWnd);
 
			if( isIntersect(polygon, size, point) == true )
				 MessageBox(hMainWnd, "Point belongs to polygon", "Result", MB_OK);
			else MessageBox(hMainWnd, "Point not belong to polygon", "Result", MB_OK);
		}
		break;
 
    case WM_DESTROY :
        PostQuitMessage (NULL) ;
        break;
 
	case WM_SIZE :
		InvalidateRect(hMainWnd, NULL, 1);
		break;
 
	default:
		return DefWindowProc (hMainWnd, iMsg, wParam, lParam);
	}
 
	return NULL;
}
 
bool isIntersect( Point p[], int size, Point s )
{
	int i, j;
	bool parity = false;
	for(i = 0, j = size - 1; i < size; j = i++)
	{
		if ( ( p[i].y < s.y && s.y <= p[j].y || p[j].y < s.y && s.y <= p[i].y ) 
		&& (s.x > (p[j].x - p[i].x) * (s.y - p[i].y) / (p[j].y - p[i].y) + p[i].x))
			parity = !parity;
	}
	return parity;
}

Ключевые слова: 
многоугольник, полигон, луч, точка внутри, точка снаружи, принадлежность точки
ВложениеРазмер
Программа проверки точки внутри многоугольника26.56 кб