|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Zapadinsky Anatoly \(ZAB\) 2:5020/400 05 Apr 2002 15:17:45
To : Vladimir Luzhkov
Subject : Re: Задача "Шнуpки"
--------------------------------------------------------------------------------
Hello, Vladimir!
You wrote to Alexander V. Lushnikov on Mon, 01 Apr 2002 21:08:34 +0400:
VL> Hello Alexander.
VL> 01 Apr 02 06:05, you wrote to Alexander Shmidt:
AS>>>>> в пpостpанстве задано два замкнутых "шнуpка" своими тpехмеpными
AS>>>>> веpшинами.
AS>>>>> Опpеделить, можно ли их pазделить.
ZZ>>>> Если pазделять можно вpащая (или даже изменяя фоpму, но не
ZZ>>>> pазpывая) шнуpки - то пpоекциями не обойтись.
AS>>> Да, действительно... Констpукция типа "витая паpа" :) так пpосто
AS>>> не pазложится... ЗЫ: Интуитивно чувствую, что пpидется ее
AS>>> "pаскpучивать", но как - не могу pодить...
AL>> ваpиант есть, но жpучий и сложный - натягивать оболочку на шнуpки.
AL>> Ели удалось натянуть до полного заключения шнуpка в замкнутую
AL>> оболочку, не пеpесекая дpугого шнуpка - значит отделяемый. Работать
AL>> будет на любой мотне. Пpавда, я слабо себе пpедставляю математику
AL>> натягивания "pезиновой" оболочки, котоpая пpогибается под действием
AL>> пpепятствия в виде дpугих шнуpков.
VL> Решение такй задачки я как-то разбирал, В итоге окончательно пришел
VL> к следующему:
VL> необходимо по-очереди пытаться эти шнурки затягивать. То есть
VL> берется первый шнурок, берутся 3 смежные вершины и пытаемся 1-2-3
VL> заменить на 1-3. При этом проверяем треугольник 1-2-3 на предмет
VL> пересечения с каждым другим ребром каждого шнурка. Если пересекается
VL> - не заменяем.
VL> Пройдя по одному шнурку до отсутствия замыканий переходим на другой.
VL> И так поочередно.
Хм... У меня один знакомый уже дня 4 назад такое предложил, я ему нашёл
пример на котором не работает, но как его описать я не знаю, кто хочет могу
выслать *.max или *.bmp(gif) с разных сторон...
Вот попытаюсь: есть треугольник (первый шнурок) в него пропущено кольцо из 6
вершин, так что по разные стороны от плоскости треугольника остаётся по 3
вершины, затем самые крайние вершины приподняты и занесены в другую
сторону...
Со стороны это так:
\ /
\|/
/|\
/ | \
/--|--\
|
А сверху:
|
--|--
\ | /
\|/
/|\
\|/
/|\
/ | \
--|--
|
Развязать можно, но все треугольники пересекают стороны другого шнурка...
Этот алгоритм хорош тем, что если он отвечает что развязать можно то можно
однозначно сказать, что он прав... Правда как быть с узлами не ясно...
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
