|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Denis Ponomarev 2:5030/800.111 08 Apr 2002 01:30:22
To : Alexander Shmidt
Subject : Задача "Шнурки"
--------------------------------------------------------------------------------
29 Mar 02 17:59, Alexander Shmidt wrote to All:
AS> Hа сайте Андрея Зайчикова есть сабжевая задачка, смысл которой в том,
AS> что в пространстве задано два замкнутых "шнурка" своими трехмерными
AS> вершинами. Определить, можно ли их разделить.
AS> Как я понимаю, решение определяется фактом пересечения их проекций?
AS> Скольких проекций достаточно?(шоп лишние разы не считать)
Появилась такая мысль. Если бред, прошу громко не смеяться.
В двух словах: мы будем спрямлять изгибы.
Подробнее: берем три соседних узла. Строим плоскость и проверяем, не пересекает
ли её шнурки (ОБА!). Если нет, то выкидываем средний узел, то есть как бы
спрямляем. Если уловие не выполняется, берем следующую тройку узлов. Пройдясь
так по все узлам обоих узлов, хотя бы один спрямим, если я не ошибся, проверяя
разные модели. Потом уже можно проверять на проекциях, когда получится, что
спрямлять некуда, хотя можно и после каждой иттерации.
Good Luck, Denis.
--- GoldED+/386 1.1.4.7
* Origin: Хорошо живут кайманы на Каймановых Островах (2:5030/800.111)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
