Проверка на внутреность или внешность относительно области

[pimeja]

Есть однозв'язная область с непреривной границей
\Gamma=\{x(t)=(x_1(t), x_2(t)), 0 <= t <= 2\pi \}
и обходом против часовой.

Как проверить лежит ли точка (x_0, y_0) в внутрености или во внешности области.

[worm2]

По-моему, условие "внутренности" для выпуклой области записывается как-то так:

$$\left|\int\limits_{0}^{2\pi}\left((x_1(t)-x_0)x_2'(t)-x_1'(t)(x_2(t)-y_0)\right) dt\right|$$

=

$$\int\limits_{0}^{2\pi}\left|(x_1(t)-x_0)x_2'(t)-x_1'(t)(x_2(t)-y_0)\right| dt$$

.

Добавлено спустя 6 минут 35 секунд:

О, а ещё можно элегантненько так:

$$\int\limits_{\Gamma}\frac{dz}{z-z_0}\ne 0$$

, где $z(t)=x_1(t) + i x_2(t)$, $z_0=x_0+iy_0$.

[Zai]

worm2, с возвращением Вас из отпуска.
Возможно немного проще осуществить алгоритм следующим образом.
Пусть $t_1 - одна из точек $(x_1(t_1),x_2(t_1)) минимального расстояния до определяемой точки $(x_0,y_0)
Для внутренней точки $(x_0-x_1(t_1))*\frac {dx_2(t_1)} {dt}-(y_0-x_2(t_1))*\frac {dx_1(t_1)} {dt})<0

[Sanyok]

По-моему, для произвольной области (выпуклой или нет - не важно) эта задача решается использованием теоремы Остроградского-Гаусса. В точку (x_0, y_0) помещаеся источник потенциального поля и рассчитывается поток через границу области. Если поток не равен 0, то точка внутри области, иначе - вне области.

[AKalinin]

Sanyok писал(а):

По-моему, для произвольной области (выпуклой или нет - не важно) эта задача решается использованием теоремы Остроградского-Гаусса.

Да, так и есть. Еще можно использовать третью интегральную формулу Грина (она выводится с использование теоремы Остроградского-Гаусса).

[MrD]

Может я не в тему, но поскольку выложено в Computer Science то речь, наверное, идет не об аналитических выкладках, а о быстрых алгоритмах. Тогда это класс алгоритмов под общим названием Convex Hull - http://en.wikipedia.org/wiki/Convex_hull.