Многоугольник (не обязательно выпуклый) задан на плоскости перечислением координат вершин в порядке обхода его границ. Определить лежит ли заданная точка внутри данного многоугольника. Входные данные: Решение. 1. Будем перебирать все соседние пары вершин А[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; }
Ключевые слова:
многоугольник, полигон, луч, точка внутри, точка снаружи, принадлежность точки
|
|||||||