Re: Снова маpшpyты

From

Mike Bolshakoff ()

To

Sergey Bychkov

Date

2002-10-21T16:05:13Z

Area

RU.ALGORITHMS

From: Mike Bolshakoff <ttw@eurocom.od.ua>

Hi, Sergey Bychkov!

> 
>  MB> Как тебе такая идея: а что если пpивести вpеменнyю шкалy
>  MB> контpолиpyемого маpшpyта к вpеменной шкале контpольного?
> 
> По-моемy, это лишнее.

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

Alexander Hritonenkov, сам чувствует, что описаный им подход
нерационален, и он абсолютно прав. Главный недостаток его подхода
такой: неясно какие пары точек/отрезков проверять на близость :)
Ведь чтобы утверждать "точка не на маршруте", потребуется проверить
факт ее непопадания во _все_ "круглоугольники". Это 999000 проверок
при 1000 точек в каждом маршруте. Причем каждая проверка - это
проверка факта непопадания точки в две полосы и обе окружности
(см. его выкладки - довольно сложно, не так ли?).
Допустим даже, какими-нибудь ухищрениями (и, разумеется,
дополнительными вычислительными затратами) удастся сократить
количество проверок в десять раз, даже в сто раз, но одной проверкой
установить факт попадания точки на маршут не удастся в принципе. 

При моем подходе (в случае линейной интерполяция скорости)
потребуется 2000 раз вычислить длину отрезка и 4000 раз решить
простую пропорцию для нахождения промежуточной точки. После чего
произвести сравнение i-й точки с одного маршрута с i-й же другого -
2000 раз.

Что тормознее?


С уважением,
Mike W. Bolshakoff
<mailto:ttw@eurocom.od.ua>


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)