2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Найти точку внутри треугольника
Сообщение21.10.2008, 11:06 
Аватара пользователя
Грани симплекса в $n$ - мерном пространстве (тетраэдра в $3D$) заданы уравнениями
$$a_{i1}x_1+ a_{i2}x_2+ \cdots + a_{in}x_n+ b_{i}=0, \;\; i=1, \cdots, n+1.$$
Как с наименьшими затратами найти точку (хоть какую-нибудь) внутри симплекса?

 
 
 
 
Сообщение21.10.2008, 11:19 
Аватара пользователя
1) Берём первые $n$ граней, ищём точку их пересечения.
2) Опускаем из неё перпендикуляр на оставшуюся грань.
3) Выбираем точку внутри отрезка-перпендикуляра.

На первом этапе решается система $n$ линейных уравнений с $n$ неизвестными. На втором --- линейное уравнение. На третьем вообще всё элементарно. Самый затратный по времени --- первый этап. Система, естественно, решается методом Гаусса :)

 
 
 
 
Сообщение21.10.2008, 11:56 
Аватара пользователя
Профессор Снэйп писал(а):
3) Выбираем точку внутри отрезка-перпендикуляра.
Но этот перпендикуляр может оказаться весь снаружи.

 
 
 
 
Сообщение21.10.2008, 12:00 
Аватара пользователя
TOTAL писал(а):
Профессор Снэйп писал(а):
3) Выбираем точку внутри отрезка-перпендикуляра.
Но этот перпендикуляр может оказаться весь снаружи.


А... Да, действительно может :(

 
 
 
 
Сообщение21.10.2008, 12:40 
Можно решить все $n+1$ систем, задающие все вершины. Потом взять среднюю точку. Она точно будет внутри.

Добавлено спустя 33 минуты 46 секунд:

А вот интересно, можно ли все эти системы решить «за один проход»? В смысле, чтоб алгоритмические затраты были не сильно больше, чем на решение одной системы.

 
 
 
 
Сообщение21.10.2008, 12:49 
Аватара пользователя
вздымщик Цыпа писал(а):
Можно решить все $n+1$ систем, задающие все вершины. Потом взять среднюю точку. Она точно будет внутри.
В этом способе надо решать много систем уравнений, чтобы получить координаты вершин, которые не нужны.

 
 
 
 
Сообщение21.10.2008, 12:50 
Вот-вот, потому я и думаю, нельзя ли их решить одновременно.

Наверное, можно. Ведь поиск обратной матрицы означает вычисление $n^2$ определителей $(n-1)$-го порядка. А тут надо найти $n(n+1)$ таких определителей. Конечно, чтоб найти решение системы, не нужно в явном виде искать обратную матрицу, но все равно наверняка можно соптимизировать и получить метод Гаусса для нескольких «очень похожих» систем.

 
 
 
 
Сообщение21.10.2008, 13:26 
Пусть треугольник.
Имеется 6 уравнений для 6 неизвестных ($x_1,y_1$), ($x_2,y_2$), ($x_3,y_3$).
Добавляем 2 уравнения и 2 неизв. $3x_0=x_1+x_2+x_3$, $3y_0=y_1+y_2+y_3$.
Итого --- 8+8.
Исключаем ненужные 6, оставляем два нужных.

Типа
$$\left(\begin{array}{cccccccc} a_1& b_1 & 0 & 0 & 0 & 0 & 0 & 0\\
a_2 & b_2\\
0&&a_2 & b_2\\
0&&a_3 & b_3\\
0&&&&a_3 & b_3\\
0&&&&a_1 & b_1\\
1& 0&1& 0&1& 0&-3& \hphantom{-}0\\
0&1& 0&1& 0&1&\hphantom{-}0&-3\end{array}\right)
\cdot
\left(\begin{array}{c} x_1\\y_1\\x_2\\y_2\\x_3\\y_3\\x_0\\y_0
\end{array}\right)=
\left(\begin{array}{c} c_1\\c_2\\c_2\\c_3\\c_3\\c_1\\0\\0
\end{array}\right)$$

Добавлено спустя 31 минуту 23 секунды:

Ну да, вряд и это проще... Если только само решение как-то хорошо выглядит и легко кодируется...

 
 
 
 
Сообщение21.10.2008, 13:32 
Аватара пользователя
Хм...

Пусть далее $\bar{x}$ означает набор $x_1, \ldots, x_n$.

У нас есть $n+1$ функций

$$
f_i(\bar{x}) = a_{i,1}x_1 + \cdots + a_{i,n}x_n + b_i; \,\, i = 1, \ldots, n+1
$$

Фактически нам надо найти "сигнатуру" внутренних точек, то есть набор $\varepsilon_1, \ldots, \varepsilon_{n+1} \in \{ +, - \}$, такой что для любой точки $\bar{x}_0$, лежащей внутри симплекса,

$$
f_i(\bar{x}_0) > 0 \Leftrightarrow \varepsilon_i = +
$$

Может, это как-то можно сделать, не находя самих вершин? Ну или находя не все вершины, а только их часть? Ну а затем уже, имея "сигнатуру", внутреннюю точку мы как-нибудь найдём...

 
 
 
 
Сообщение21.10.2008, 14:02 
Аватара пользователя
Алексей К. писал(а):
Исключаем ненужные 6, оставляем два нужных.
...................
Ну да, вряд и это проще... Если только само решение как-то хорошо выглядит и легко кодируется...

Это проще примерно в два раза, т.к. равносильно тому, что каждая из $n+1$ систем решается методом Гаусса наполовину (только приводится к треугольному виду).

Я написал, что проблема частично решена. Имел в виду, что могу (если не ошибаюсь) найти внутреннюю точку, решив всего одну систему для $n$ неизвестных. Однако коэффициентами этой системы являются скалярные произведения векторов из $n+1$ компонент. Т.е. для получения такой системы требуются вычисления. Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

 
 
 
 
Сообщение21.10.2008, 18:36 
TOTAL писал(а):
Я написал, что проблема частично решена. Имел в виду, что могу (если не ошибаюсь) найти внутреннюю точку, решив всего одну систему для $n$ неизвестных. Однако коэффициентами этой системы являются скалярные произведения векторов из $n+1$ компонент. Т.е. для получения такой системы требуются вычисления. Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

А практически никак (если я правильно понял ситуацию). Для составления матрицы типа Грама требуется порядка $n^3$ операций, и для последующей реализации метода Гаусса -- тоже.

 
 
 
 
Сообщение22.10.2008, 07:02 
Аватара пользователя
ewert писал(а):
TOTAL писал(а):
Может быть, кто-нибудь придумает как свести к одной системе, которая получается с меньшими вычислениями?

А практически никак (если я правильно понял ситуацию). Для составления матрицы типа Грама требуется порядка $n^3$ операций, и для последующей реализации метода Гаусса -- тоже.

Если известна точка внутри тетраэдра, то для каждой грани можно указать (путём подстановки координат этой точки в уравнение грани), по какую сторону от этой грани (положительную или отрицательную) расположен тетраэдр. Можно ли сократить требуемые вычисления, если замахнуться на меньшее (может, оно фактически и не меньшее?), т.е. не искать точку внутри симплекса, а всего лишь определить, по какую сторону от каждой грани он расположен?

Конечной "целью" этой "задачи" является нахождение радиуса и центра вписанного в симплекс шара. Шар вписывается путем решения всего одной системы линейных уравнений, если известна ориентация граней.
Как вписать шар с наименьшими затратами?

 
 
 
 
Сообщение22.10.2008, 11:36 
TOTAL в сообщении #152410 писал(а):
Шар вписывается путем решения всего одной системы линейных уравнений.
Как вписать шар с наименьшими затратами?

Означает ли данный вопрос "как с наименьшими затратами решить эту всего одну систему линейных уравнений"?

 
 
 
 
Сообщение22.10.2008, 12:14 
Аватара пользователя
Алексей К. писал(а):
TOTAL в сообщении #152410 писал(а):
Шар вписывается путем решения всего одной системы линейных уравнений.
Как вписать шар с наименьшими затратами?

Означает ли данный вопрос "как с наименьшими затратами решить эту всего одну систему линейных уравнений"?
Нет, не означает. Так как сначала надо решить, по какую сторону от граней вписывать шар. Например, в плоскости можно вписать четыре круга, касающиеся трех прямых линий, но только один круг будет внутри треугольника.

 
 
 
 
Сообщение22.10.2008, 12:21 
Аватара пользователя
Кстати, не будет ли радиус вписанного в симплекс шара наименьшим среди радиусов шаров, касающихся каждой из плоскостей граней симплекса?

 
 
 [ Сообщений: 22 ]  На страницу 1, 2  След.


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