2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 
Сообщение01.09.2008, 15:44 
Аватара пользователя
По-моему, условие "внутренности" для выпуклой области записывается как-то так:
$$\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$.

 
 
 
 
Сообщение01.09.2008, 19:33 
Аватара пользователя
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

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

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


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

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

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group