Кратчайшее расстояние. На кубе

← →
Zhouck (2003-10-03 15:57) [0]

Пусть у нас есть куб. На нем можно указать две любые точки. Кратчайшее расстояние между ними по поверхности ?

← →
vuk (2003-10-03 15:59) [1]

Сделать развертку и провести прямую.

← →
nikkie (2003-10-03 15:59) [2]

только не любая развертка подойдет

← →
Zhouck (2003-10-03 16:04) [3]

А в какую сторону считать? На сколько я знаю, возможно кратчайшее рассояние через 4 грани (хотя єто сложно представить)

← →
pasha_golub (2003-10-03 16:13) [4]

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

2Zhouck
А по-моему нет, конечно если задачу не усложнять, или не считать проход через вершину за проход по все трем граням :-)

← →
Darts (2003-10-03 16:19) [5]

z^2 = x^2 + y^2 + z^2 для трехмерного пространства

← →
Darts (2003-10-03 16:20) [6]

тфьу... очепяитка
a^2 = x^2 + y^2 + z^2, где а есть искомое расстояние

← →
Nikolay M. (2003-10-03 16:24) [7]

Подытожу мысли первых двух постингов: сделать всевозможные развертки куба, исключить равнозначные (неочевидная задача, имхо), провести в каждой из них отрезок, соединяющий точки (учесть, что при развертке отрезок может прерываться на границе одного квадрата и начинаться на другом), из всех отрезков выбрать минимум. Тупо, но верно.

← →
Zhouck (2003-10-03 16:34) [8]

a^2 = x^2 + y^2 + z^2, где а есть искомое расстояние
Да какой трехмерный. Оно то трех мерное, но расстояние считается на плоскости. Потому такая формула не канает.

← →
AlexKniga (2003-10-03 18:13) [9]

Nikolay M.
> исключить равнозначные

Лучше этого не делать, и в следствии, также не нужно будет > учесть, что при развертке отрезок может прерываться на границе одного квадрата и начинаться на другом

← →
pasha_golub (2003-10-03 19:31) [10]

Дяденьки на кубе по-моему однохренственно как пойдешь, а вот на призме, да еще и не на прямой, хотя прямая/косая в принципе для топологии пофиг

← →
Юрий Федоров (2003-10-03 19:37) [11]

Почему никто ничего не сказал по поводу кубинцев, пытающихся попасть во Флориду?

← →
nikkie (2003-10-03 20:11) [12]

>pasha_golub
мальчик, ты не прав, причем два раза (про 3 грани - тоже).

← →
Zhouck (2003-10-06 10:47) [13]

Что-то мало вариантов. Что, любителей алгоритмов здесь нет ?

← →
pasha_golub (2003-10-06 11:12) [14]

2nikkie
У ну-ка, дяденька, научите. Как говорится код, то есть пример с тремя гранями, в студию :-)

← →
pasha_golub (2003-10-06 11:20) [15]

Пардон, пример с четырьмя гранями, конечно :-)

← →
nikkie (2003-10-06 13:10) [16]

bitte scho"n :)
пусть нижняя грань - ABCD, верхняя - A"B"C"D".
берем точку P = середину ребра AB и точку Q = С".
кратчайшая линия, соединяющая их, проходит по 2-м граням ABB"A" и BCC"B".
теперь чуть-чуть сдвигаем эти точки, так чтобы они не нахожились на ребрах.
точку P - по грани ABCD, точку Q - по грани A"B"C"D".
теперь кратчайшая проходит по 4 граням.

← →
Mike Kouzmine (2003-10-06 13:13) [17]

Не знаю какое кратчайшее растояние на Кубе, но самое большое знаю - до Флориды.

← →
Igorek (2003-10-06 13:14) [18]

Еще зависит от того как сдвинуть точку Q. Может или по трем или по четырем пройти.

← →
nikkie (2003-10-06 13:42) [19]

>Igorek
>Еще зависит от того как сдвинуть точку Q
сказано - по грани A"B"C"D" и чуть-чуть.

← →
Izyum (2003-10-06 13:49) [20]

Есть такой метод "бегущая волна" или его более сложная модификация "встречная волна". Если разобраться в его принципе - можно расчитывать не только на кубе, а на любой форме, и даже с препятствиями:)

← →
Zhouck (2003-10-06 14:18) [21]

>>метод "бегущая волна"
А поподробнее ?

← →
pasha_golub (2003-10-06 14:23) [22]

2nikkie
Дяденька, а вы нарисовать то, что говорите пробовали? Если всю эту хрень сдвинуть, то кратчайший путь все равно будет по трем граням. Не может он быть по четырем, если исключить случай с прохождением через вершины, а не может, потому что куб - фигура центральносимметричная, и между двумя любыми точками можно дойти максимум по трем граням

← →
Izyum (2003-10-06 14:28) [23]

> Zhouck © (06.10.03 14:18) [21]

Учебники по проектированию печатных плат:) Описывать достаточно долго

← →
pasha_golub (2003-10-06 14:29) [24]

2Izyum
Гы, малаца! Тоды все про графы...

← →
Zhouck (2003-10-06 15:06) [25]

>>потому что куб - фигура центральносимметричная, и между двумя любыми точками можно дойти максимум по трем граням
Я тоже когда-то так думал

← →
pasha_golub (2003-10-06 15:08) [26]

2Zhouck
Ну е-мое я готов поверить, приведите пример, желательно с рисунком, а то может я неправильно истолковал условия nikkie

← →
nikkie (2003-10-06 15:36) [27]

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

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

← →
pasha_golub (2003-10-06 16:27) [28]

2nikkie
Да нет, дяденька, как раз врубаюсь. Требую чертеж! :-)

← →
Igorek (2003-10-06 17:10) [29]

> pasha_golub © (06.10.03 16:27) [28]
> 2nikkie
> Да нет, дяденька, как раз врубаюсь. Требую чертеж! :-)

Вот напр. берем ребро куба (пусть ребро Р). Ребро куба равно 100 см. В вершинах ребра ставим две точки. Потом сдвигаем их по непаралельным ребрам (не по ребру Р) на 5 см. Потом сдвигаем их по паралельным граням, перпендикулярным ребру Р на 1 см. Потом соединяем эти две точки по поверхности.

Другими словами получится развертка из 4 квадратов в форме S. На ней можно провести прямую через четыре грани.

← →
Юрий Зотов (2003-10-06 17:29) [30]

Предлагается такое решение (интуитивное, не проверял).

1. Проводим плоскость через 2 исходные точки и центр куба.
2. Пересечение этой плоскости с гранями даст 2 пути. Более короткий из них и есть искомый.

← →
pasha_golub (2003-10-06 17:30) [31]

2Igorek
Понял, спасибо. Так бы сразу, про букву S. Приношу извинения, был не прав

2nikkie
А вы, дяденька, чертежики все-таки рисуйте :-))

← →
Юрий Зотов (2003-10-06 17:33) [32]

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

← →
han_malign (2003-10-06 18:10) [33]

> 1. Проводим плоскость через 2 исходные точки и центр куба.
- блин, а вот откуда третью точку взять я и не догадался, а ведь все просто: сфера - это вырожденный куб (очень сильно вырожденный):)))

← →
pasha_golub (2003-10-06 18:13) [34]

2han_malign
С точки зрения топологии один хрен.

2все
Я отказываюсь от заявления pasha_golub © (06.10.03 17:30) [31]

Требую рисунок в диметрии или аксонометрии

← →
Igorek (2003-10-06 18:14) [35]

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

← →
nikkie (2003-10-06 22:15) [36]

>pasha_golub
http://schachspieler.narod.ru/cube.htm

← →
nikkie (2003-10-06 22:27) [37]

>Юрий Зотов
кратчайший путь так не получится.

Кратчайшее расстояние. На кубе Найти похожие ветки