Алгоритм проверки принадлежности точки невыпуклому многоугольнику с помощью триангуляции

Результат работы

Проверить принадлежит ли заданная точка невыпуклому многоугольнику без самопересечений.

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

struct point {
	int x, y, color;
	point (int x = 0, int y = 0, int color = 0) : x(x), y(y), color(color) {}
};
struct triangle {
	point a, b, c;
	triangle (point a, point b, point c) : a(a), b(b), c(c) {}
};
vector<point> points; // вершины многоугольника
vector<point> points2; // точки, которые будем проверять
 
// добавление точки в указанный контейнер
void addPoint(LPARAM lParam, int color, vector<point> &points) {
	int x = LOWORD(lParam);
	int y = HIWORD(lParam);
	points.push_back(point(x, y, color));
}
// вычисление удвоенной площади треугольника
int square(const point &a, const point &b, const point &c) {
	return abs((c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x));
}
// проверка принадлежности точки d треугольнику (a,b,c)
bool inTriangle(const point &a, const point &b, const point &c, const point &d) {
	return square(a, b, c) == square(a, b, d) + square(b, c, d) + square(c, a, d);
}
// listPoint -- вершины многоугольника
// triangles -- контейнер, в котором будем хранить все полученные треугольники
void triangulation(list<point> &listPoint, HDC hdc, vector<triangle> &triangles) {
	// берем первые 3 вершины из списка, обозначим их a,b,c
	point a = listPoint.front();
	listPoint.pop_front();
	point b = listPoint.front();
	listPoint.pop_front();
	point c = listPoint.front();
	listPoint.pop_front();
	if (listPoint.empty())
	{
		triangles.push_back(triangle(a, b, c));
		return;
	}
	// проверяем, что вершина b лежит слева от вектора (a,c)
	// и ни одна из вершин многоугольника не лежит внутри треугольника (a,b,c)
	bool ok = (c.x - a.x) * (b.y - a.y) - (c.y - a.y) * (b.x - a.x) <= 0;
	for (list<point> :: iterator it = listPoint.begin(); it != listPoint.end(); ++it) 
	{
		if (inTriangle(a, b, c, *it))
		{
			ok = false;
			break;
		}
	}
	if (ok)
	{
		// если условия выполнены, то удаляем вершину b
		// добавляем треугольник (a,b,c) в контейнер triangles
		//MoveToEx(hdc, a.x, a.y, 0);
		//LineTo(hdc, c.x, c.y);
		listPoint.push_front(c);
		listPoint.push_front(a);
		triangles.push_back(triangle(a, b, c));
	}
	else
	{
		// иначе делаем первую вершину последней
		listPoint.push_front(c);
		listPoint.push_front(b);
		listPoint.push_back(a);
	}
	triangulation(listPoint, hdc, triangles);
}
 
 
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
	int wmId, wmEvent;
	PAINTSTRUCT ps;
	HDC hdc;
 
	switch (message)
	{
	// ...
	case WM_PAINT:
		hdc = BeginPaint(hWnd, &ps);
		{
			const int R = 4;
			HBRUSH oldBrush = (HBRUSH) SelectObject(hdc, CreateSolidBrush(0));
			HPEN oldPen = (HPEN) SelectObject(hdc, CreatePen(0, 1, 0));
			// рисуем на экране вершины и ребра многоугольника
			for (int i = 0; i < (int) points.size(); ++i)
			{
				DeleteObject(SelectObject(hdc, CreateSolidBrush(points[i].color)));
				DeleteObject(SelectObject(hdc, CreatePen(0, 2, points[i].color)));
				Ellipse(hdc, points[i].x - R, points[i].y - R, points[i].x + R, points[i].y + R);
				DeleteObject(SelectObject(hdc, CreatePen(0, 2, RGB(0, 0, 200))));
				MoveToEx(hdc, points[i].x, points[i].y, 0);
				LineTo(hdc, points[(i + 1) % points.size()].x, points[(i + 1) % points.size()].y);
			}
			if (points.size() >= 3) {
				list<point> listPoint;
				for (int i = 0; i < (int) points.size(); ++i)
					listPoint.push_back(points[i]);
				DeleteObject(SelectObject(hdc, CreatePen(1, 2, RGB(200, 0, 0))));
				point downLeft(-1, -1, 0);
				int index;
				for (int i = 0; i < (int) points.size(); ++i)
				{
					if (points[i].x > downLeft.x) {
						downLeft = points[i];
						index = i;
					}
				}
				point a = points[(index + points.size() - 1) % points.size()];
				point b = points[index];
				point c = points[(index + 1) % points.size()];
				// если многоугольник задан в порядке обхода против часовой стрелки
				// то меняем порядок обхода
				if ((c.x - b.x) * (b.y - a.y) - (c.y - b.y) * (b.x - a.x) >= 0)
					listPoint.reverse();
				vector<triangle> triangles;
				triangulation(listPoint, hdc, triangles);
				for (int i = 0; i < (int) points2.size(); ++i)
				{
					bool ok = false;
					for (int j = 0; j < (int) triangles.size(); ++j)
					{
						if (inTriangle(triangles[j].a, triangles[j].b, triangles[j].c, points2[i]))
						{
							ok = true;
							break;
						}
					}
					// если текущая точка лежит в одном из треугольников, то покрасим её RGB(0, 150, 150)
					// иначе RGB(255, 0, 0)
					if (ok)
						points2[i].color = RGB(0, 150, 150);
					else points2[i].color = RGB(255, 0, 0);
					DeleteObject(SelectObject(hdc, CreatePen(0, 2, points2[i].color)));
					DeleteObject(SelectObject(hdc, CreateSolidBrush(points2[i].color)));
					Ellipse(hdc, points2[i].x - R, points2[i].y - R, points2[i].x + R, points2[i].y + R);
				}
			}
			DeleteObject(SelectObject(hdc, oldBrush));
			DeleteObject(SelectObject(hdc, oldPen));
		}
		EndPaint(hWnd, &ps);
		break;
	case WM_LBUTTONUP:
		addPoint(lParam, RGB(0, 200, 0), points);
		InvalidateRect(hWnd, 0, true);
		break;
	case WM_RBUTTONUP:
		addPoint(lParam, RGB(255, 0, 0), points2);
		InvalidateRect(hWnd, 0, true);
		break;
	//...
	}
	return 0;
}

Ключевые слова: 
триангуляция, точка внутри многоугольника
ВложениеРазмер
win32.rar4.02 Мб