|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 08 Apr 2002 10:40:10
To : ZAB\
Subject : Re: Задача "Шнурки"
--------------------------------------------------------------------------------
> VK>>> 1) pазбиваем одну кpивую на тpеугольники, считаем число точек
> ZAZ>> ^^^^^^^^^^^^
> ZAZ>> А как быть если она или они сами по себе являются узлами???
> VK> Тpеугольник, согнутый в кукиш? Кpуто... Я то думал, что
> VK> тpеугольник по опpеделению плоский :) А если сеpьезно, то для этой
> VK> задачи, имхо, узел не может pассматpиваться как мат.точка, т.е.
> VK> имеет ненулевые pазмеpы и pазбивается на отpезки конечной длины.
> VK> Hо стягивать тpеугольники сpазу, как Владимиp Лужков пpедлагает,
> VK> конечно, лучше. По очеpеди, то одну кpивую, то дpугую...
>
> Как ты кривую-узел на треугольники разобьёшь??? А что касается стягивания,
> то я ему уже ответил и даже попытался объяснить словами свой пример, вот
> толко ничего не вышло (любому желающему могу выслать max или проеции в
> gif)... Повторяю: алгоритм хорош только как некий препроцессинг (только в
> случае если верный алгоритм будет очень сложен)
> отбрасывающий простые ситуации в которых шнурки не сцеплены.
Стягивание спасёт отца русской демократии. Стягивание не только три подряд
идущие точки вдоль шнурка (назовём его стягивание 3 в 2), но стягивание любых
трёх точек одного шнурка, сквозь треугольник из которых не проходит второй
шнурок (это уже стягивание 5 в 4).
Однако острой нужды в громоздком алгоритме стягивания нет.
Если проекция (одна штука) на плоскость содержит чётное количество точек, где
шнурок 1 выше шнурка 2 и чётное количество - где ниже - то они разделяются.
Если на проекции есть совпадающие отрезки разных шнурков - либо ищем другую
проекцию, либо двигае точки шнурков.
Andrew Doroshev
Hо здесь работы поболе. Hадо контролировать и отсутствие пересечений справа и
слева от нового отрезка.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
