Проверка нахождения точки внутри многоугольника.

Январь 15, 2008

Недавно опять столкнулся с задачей. Необходимо проверить, находиться ли точка внутри произвольно ориентированного четырехугольника на плоскости. Задача решается одинакого для любого выпуклого многоугольника.

Приведу решение для 4х угольника, так как мне было нужно именного для него, но его очень легко переделать под треугольник или любой другой многоугольник.

Проверка нахождения точки внутри многоугольника

Для всех случаев задача сводиться к нахождению суммы углов между векторами, проведенными от точки P к каждой вершине многоугольника. Если их сумма равна 360 градусов, тогда точка лежит внутри многоугольника.

Пример реализации

/// определяем, находится ли точка внутри произвольно повернутого 4хугольника на плоскости
inline bool isPointInsideRect2D(const Vector4& pos, const Vector4& p1, const Vector4& p2, const Vector4& p3, const Vector4& p4) {
	float angle = 0;
	Vector4 dir[4];
	dir[0] = (p1 - pos).getNormalized();
	dir[1] = (p2 - pos).getNormalized();
	dir[2] = (p3 - pos).getNormalized();
	dir[3] = (p4 - pos).getNormalized();
	angle += acosf(dir[0] * dir[1]);
	angle += acosf(dir[1] * dir[2]);
	angle += acosf(dir[2] * dir[3]);
	angle += acosf(dir[3] * dir[0]);
	/// 0.000001f - это точность для float
	if(NShared::PI * 2 - angle < 0.000001f)
		return true;
	return false;
}
			

Реализацию класса Vector4 смотрите тут.

Обсудить в форуме.


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

All content copyright (c) 2012 Vladislav Litunovskiy. All Rights Reserved.