Кодирование сети дорог на карте

[Andrew771]

Подскажите какие-нибудь идеи экономичного кодирования и хранения сетей дорог на карте местности максимум 256х256 клеток. Не связанных друг с другом сетей может быть несколько. Быстродействие не важно.

Вот способы, которые на ум пришли:

1. Самое простое - две координаты каждой клетки дороги. Очень затратно по памяти. Итого 2n байт.

2. Базовая клетка - две координаты. Соседние клетки одной сети кодируются смещениями от базовой клетки, от 1 до 16 по вертикали и горизонтали - 1 байт на клетку. Если сеть больше 16х16, то заводим новую базовую клетку. Итого примерно 1.1n байт.

3. Базовая клетка - две координаты. Соседние клетки одной сети кодируются направлениями от базовой клетки - вверх, вниз, влево, вправо - 2 бита на клетку. Плюс какая-то часть памяти на указание соседства. Очень геморный кодировщик и раскодировщик. Итого примерно 0.4n байт.

Может есть еще что-то из теории графов?

[Advertiser]