|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 21 Jul 2003 09:26:08
To : Andrey Tarasevich
Subject : Re: оЕПЕРЮЯЙХБЮМХЕ ПЕАЕП Х БЕПЬХМ. лHФЕР ОHОПHЫЕ ЯМЮВЮКЮ ГЮДЮВЙС?
--------------------------------------------------------------------------------
Andrey Tarasevich wrote:
>
> Thu Jul 10 2003 03:47, Serge Nozhenko wrote to Dmitriy Goldobin:
>
> SN> Жють.
>
> SN> Ввести линейную упорядоченность типа less((x1, y1), (x2, y2)) = (x1 <
> SN> x2 || x1 == x2 && y1 < y2), и использовать обычные сортировку/бинарный
> SN> поиск.
>
> Если ты сможешь предложить способ линейного упорядочивания точек плоскости,
> который будет каким-то образом сохранять свойство близости точек, то тебе
> поставят памятник во многих станах мира и твое имя, скорее всего, будет
> упомянуто в эпитафии на могиле современной метематики.
>
> Предложенный тобой способ сравнения и близко не похож на что-то осмысленное в
> контексте данной задачи.
ну зачем так строго - товарищ просто хотел упорядочить точки по их
проекции на ось X, что вполне разумно и работает, если число точек имеет
порядок 100 000. Точно так же сортируются (по левому краю) и проекции
всех отрезков на ось X. Это позволяет при поиске сразу "отсечь" точки и
линии, не попадающие в проекцию, после чего использовать
последовательный поиск - среднее число кандидатов при котором десятки.
Работает все это много лет (больше десяти), и не намного медленнее, чем
всякие квадродеревья и прочие премудрости.
Анатолий Савельев
--- ifmail v.2.15dev5
* Origin: MELT InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
