ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sasha Mokrov                         2:461/77       23 Jun 2003  11:36:37
 To : Victor Anikeev
 Subject : координаты
 -------------------------------------------------------------------------------- 
 

 
  VA>  Есть матрица размером 256x256 и список координат в ней.
  VA>  Очень важным является порядок координат.
  VA>  Более 90% соседних пар координат расположены в соседних ячейках
  VA>  (то есть abs(X1-X2) <= 1 AND abs(Y1-Y2) <= 1 ).
  VA>  Сам список на много меньше чем 65536, то есть процент заполнения
  VA>  матрицы точками не очень большой. В любом случае не превышает 40-50%.
 
  VA>  Как наиболее эффективно хранить список в плане занимаемого места?
 
  VA>  У меня есть только одна идея.
  VA>  1. Разбить все координаты на непрерывные группы и в начале каждой
  VA> группы записать ее размер. Следующие два байта - точные координаты
  VA> первой точки. Далее только смещения. Так как соседних ячеек восемь, то
  VA> достаточно трех бит на запись. Может быть далее сжать все это с
  VA> помощью RLE или другого простого алгоритма.
 
  VA>  Какие есть еще предложения? Мне нужен как можно меньший размер списка
  VA>  в памяти.
 
 Представить это все в виде графа, найти кратчайший путь, проходящий через все
 точки, а далее идти по обозначенному маршруту и записывать смещение по x и y от 
 предыдущей до следующей. Смещение записывать с помощью чисел переменной длины
 (тут реализаций много, например, старший бит - класс - количество значащих
 битов: если 0, то один значащий, если 10, то два, 110 - четыре (соответствие
 подбирается оптимальным для конкретной области задач), и т.д. За ним идут сами
 значащие биты, и это только одна из реализаций).
 
 Итого получится, что у тебя путь через плотные группы будет в основном проходить
 без разрыва (в смысле перехода в другие группы и возврата назад).
 
                                             ю CU, Sasha. 02:01CD/4D.00
 
                            ъ ДД [icq 161790265] [email mokrov{на}ua.fm] ДъъДДДД
 --- [ю] WinAMP is closed
  * Origin: system.ini::[boot] shell=calc.exe (2:461/77)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    координаты   Victor Anikeev   25 May 2003 01:55:06   координаты   Rodion Gorkovenko   25 May 2003 02:15:00   координаты   Sasha Mokrov   23 Jun 2003 11:36:37