Найти точку внутри треугольника

[TOTAL]

Профессор Снэйп писал(а):

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

Будет, конечно. Но как это может помочь?

[Алексей К.]

Задача на плоскости легко формализуется в нужном Вам направлении, и, полагаю, Вам это проблем не составляет.

TOTAL в сообщении #152457 писал(а):

Так как сначала надо решить, по какую сторону от граней вписывать шар.

А это тот же тупик --- надо правильно ориентировать грани.

(1) Найти координаты одной вершины --- и по ней ориентировать все те грани, к которым она не принадлежит. Найти другую вершину...

(2) Или --- найти точку в $\varepsilon$-окрестности любой вершины, так, чтобы она была "внутри" стерео-угла (по терминологии треугольника --- на луче-биссектрисе внутреннего угла).

Понятно, для чего Вам была нужна хоть какая-то точка внутри... Пока по-прежнему непонятно, как это сделать "быстро".

[ewert]

TOTAL писал(а):

Профессор Снэйп писал(а):

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

Будет, конечно. Но как это может помочь?

если вписанные шары вообще строить уже умеем, то -- тупым перебором пожет. Неэффективно, но работать будет

--------------------------------------------------------------------------
Ну ладно, будем считать это шуткой, а вот такая мысля. Выстраиваем все $(n+1)$ уравнение граней в одну переопределённую систему и приводим её к почти треугольному виду (так, чтобы первая ненулевая диагональ выходила из правого нижнего угла). Это требует порядка $n^3$ операций. Теперь каждая вершина находится выкидыванием одной из строк, а на решение остающейся почти треугольной системы требуется порядка $n^2$ операций. Итого $n^3$ операций на всё про всё, а чего ещё желать?.

[TOTAL]

ewert писал(а):

TOTAL писал(а):

Профессор Снэйп писал(а):

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

Будет, конечно. Но как это может помочь?

если вписанные шары вообще строить уже умеем, то -- тупым перебором пожет. Неэффективно, но работать будет.

Очень неэффективно.
Например на плоскости заданы прямые
$4x-3y+9=0$
$12x+5y-43=0$
$7x+24y+19=0$
Для построения всех касающихся этих прямых окружностей надо решить систему уравнений
$|4x-3y+9|/5=|12x+5y-43|/13=|7x+24y+19|/25=R$,
раскрывая разными способами скобки.
Если же известно, что первая и третья прямая ориентированы положительно, а вторая прямая - отрицательно, то решаем всего одну систему уравнений
$(4x-3y+9)/5=-(12x+5y-43)/13=(7x+24y+19)/25=R$
и находим радиус $R=2$ и координаты центра $x=1, \;\; y=1$ именно вписанной в треугольник окружности.

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

ewert писал(а):

Выстраиваем все $(n+1)$ уравнение граней в одну переопределённую систему и приводим её к почти треугольному виду (так, чтобы первая ненулевая диагональ выходила из правого нижнего угла). Это требует порядка $n^3$ операций. Теперь каждая вершина находится выкидыванием одной из строк, а на решение остающейся почти треугольной системы требуется порядка $n^2$ операций. Итого $n^3$ операций на всё про всё, а чего ещё желать?.

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

Как же так получается, что для нахождения хотя бы какой-то точки внутри симплекса требуется столько же оперций как и для нахождения всех вершин? Ведь когда хочешь получить меньше, обычно рассчитываешь, что и платить надо будет меньше.

[Алексей К.]

Мы бы вправе рассчитывать, что центр тяжести стоит меньше.
А насчёт любой точки --- не уверен... Эдак Вы подешёвке всю внутренность скупите!

[ewert]

Я, кстати, сжульничал, за что и приношу извинения. Вычеркивать строки из полученной почти треугольной матрицы нельзя -- это уже будут не вершины. Но выкрутиться, кажется, всё-таки можно. Если сохранять левотреугольную матрицу, реализующую прямой ход иетода Гаусса. И вычёркивать строки [i]исходной[\i] матрицы. Тогда матрица, полученная умножением левотреугольной на оставшуяся после вычёркивания, не будет, конечно совпадать с соответствующей частью правой почти треугольной, но отличия не очень велики, и порядок $n^2$ для системы вроде бы остаётся.

А что до того, что "птичек жалко" (пардон, точек) -- то тут, мне кажется, ничего не поделаешь. По отношению к каждой проверяемой точке каждая следующая вершина даёт принципиально новую информацию, так что вряд ли удастся обойтись лишь частью вершин.

[вздымщик Цыпа]

Не, со сферами плохо. Их вроде бы $2^n$, из которых реализуется $n+2$, причем сразу не скажешь, которые именно. И из них уже правильная только одна.

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