Приветствую участников форума.

Вопрос такой.

Имеется двумерная матрица, ячейки которой могут принимать множество значений. Для наглядности можно представить обычную двумерную картинку, где множеству значений ячеек матрицы соответствует цвет точки.
Необходим алгоритм, представляющий описание матрицы не как поле икс на игрек, а как набор треугольников (т.е. набор выпуклых многоугольников), т.к. матрица имеет множество однородных областей.


Потребность вызвана жёстким ограничением на размер таблицы, описывающей матрицу (до дури огромную). 
Понятно, что время поиска точки многократно возрастёт, но в моём случае это меньшее зло.

Буду благодарен за любые идеи, ссылки, чужие алгоритмы, замечания и просто сочувствие  :-)

P.S. Была ещё мысль архивировать матрицу частями (и частями же обрабатывать), но, IMHO, это более времязатратный способ её обработки, хотя, с другой стороны, сравнивать пока не с чем...

как вариант - GIF
как раз специализируется на сжатии двумерных картинок, в которых часто встречаются однородные области

ну или попроще - RLE: простое объединение повторяющихся значений в строке в группы

Спасибо, но GIF- это всё-таки сжатие.

Чтобы определить значение конкретной точки матрицы (вот поэтому я и зациклился на треугольниках- они выпуклые, вхождение точки в выпуклый многоугольник можно легко найти), мне нужно будет распаковывать её всю  (вплоть до искомой точки, конечно).

Предполагаемый размер матрицы- около  50000 х 50000 ячеек, а храниться она будет в интернете. 

Вот такие у меня заморочки... :-)

Хотя, с GIF/RLE можно попробовать вариант сжатия отдельно больших кусков матрицы (напр. 1000 х 1000), и закачивать с сервера лишь те куски, которых коснулись изменения....

Но вариант с многоугольниками мне почему-то видиться более подходящим... Если, конечно, существует искомый мной алгоритм... 

честно говоря, не знаю, как с GIF'ом, но думаю он, как и RLE, позволяет не сохранять результаты декомпрессии - только текущее состояние
так что памяти много понадобиться не должно
а времени, например, в случае RLE - пропорционально количеству областей разного цвета в строке до этой точки

можно ещё попробовать такой алгоритм (просто не помню, как называется):
делим изображение на четыре равных квадрата, для тех, которые состоят из одинаковых цветов, просто записывается какой-то маркер и этот цвет, для тех, у которых цвета разные - процедура повторяется
т.е. получается такое 4-дерево, где каждый уровень соответствует размеру квадратиков (на каждом следующем в 2 раза меньше)
если часто встречаются области одинаковых цветов, то дерево будет часто обрываться, т.к. многие квадратики будут одноцветные
(этот алгорим хорошо подходит для другой задачи - скачивание с сервера большой картинки и постепенное показывание её всё точнее и точнее, чтобы пользователь мог решит, ждать до конца или нет)
однако, есть некоторые опасности:
в случае неудачного расположения цветов (если вдруг получилось немного однородных областей) размер может увеличиться
кроме того, если однородные области расположены близко к границам квадратов, то они будут кодированы не совсем оптимально - для таких случаев можно попробовать делить изображение на неодинаковые квадраты, но это всё усложняет



любая неоднородная область, мне кажется, не очень хорошо аппроксимируется многоугольником
тут такой вопрос: какой природы данные? (может, действительно, многоугольники тамв самый раз)

Матрица представляет собой описание карты для имитационного моделирования.

Если кто-то видел аэрофотоснимки или прыгал с парашюта, помнит, как причудливо выглядит земля с высоты даже 500 метров- большие многоугольные однородные области. Планируемый размер карты 500 х 500 км, в клетках по 10 метров.

Небольшие изменения будут вызваны изменением флоры- то площадь леса увеличилась, то уменьшилась, вследствии пожара, один вид флоры потеснил другой, тут речка заросла и близлежащий луг стал заливным и т. д.  

За описанный выше алгоритм спасибо, тоже вариант.

И всё же, как полагаете, для такой природы данных подходит аппроксимация многоугольниками?

Ооооо... совсем другое дело
а задача сегментации уже решена? (ведь эти области не будут точно однородными - будут как минимум шумы)

Естественно, в природе эти области не являются абсолютно однородными. Однако эта неоднородность частично не учитывается.

Хотя, смотря что считать шумом. Расположение деревьев в клетке, а также видовой состав (опять же в клетке) в расчёт не берутся, просто есть, например, тип клетки, означающий редкий березовый лес с вкраплениями вяза- 5 деревьев).

Если же примером шума является поляна в лесу, то решение проблемы мне видится следующим образом. 

На этапе построения карты изначально строятся объекты, подразумеваемые полностью однородными. Далее, происходит их "разбавление" по определённому алгоритму. Допустим, в лесу появляется поляна (или на поле- пруд, без разницы). Происходит оценка размеров объекта (ищутся все связанные однородные клетки). Если он достаточно велик, и являет собой не шум, а, скорее, полноценный объект (достаточно большая поляна, или большой пруд), то образование получает сатус объекта и описывается многоугольниками. Объект- родитель (для поляны- лес, для пруда- поле) также описывается многоугольниками заново.

Если объект достаточно мал, например, всего одна клетка (или две, пять, в зависимости от настроек), то он (т.е. его клетки) заносится в специальную таблицу шума.

Дальнейшее мне видится так. Допустим, мы хотим найти какую-то клетку с известными координатами х и у. Для этого мы первоначально просматриваем таблицу шума, и, если искомой клетки там нет, ищем её по таблице треугольников. Для ускорения поисков, можно, опять же, разбить карту на куски (4, 16, 25) , сопоставив каждому из них свои таблицы. Допустим, известно, что искомая точка находится в районе, за описание которого отвечает конкретная пара таблиц (треугольники и шумы) => поиск осуществляется лишь в этих таблицах. 

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

Разумеется, это эффективно при малом уровне шумов. Поэтому их количество придётся искусственно ограничивать...

Расчёты будут выполняться cgi-скриптом на сервере.  

Разумеется, также необходимо время от времени, перестраивать многоугольники (т.е. проверять на возможность обрзования новых бОльших многоугольников).

а, ну если уже используются понятия "редкий лес" и пр., значит то, что я имел в виду уже проделано (т.е. переход фотография -> набор клеток определённых типов)

вообще, мне кажется, с многоугольниками может возникнуть проблема: точность понятия "прямая линия"
ведь границы областей на картах редко бывают прямыми линиями
кроме того, из-за целочисленности координат на сетке будут происходить всякие округления

можно попробовать разбивать области на "криволинейные трапеции" (это понятие использовалось в некоторых доказательствах, связанных с двумерным интегрированием)
под криволинейной трапецией понимается фигура, ограниченная сверху и снизу горизонтальными прямыми, а слева и справа - отрезками каких-то кривых
на такие фигуры, по-моему (по крайней мере, на первый взгляд), несложно разбить исходное изображение и хранить его тоже можно с хорошей экономией: двумя числами запоминаем диапазон по вертикали и по два числа на каждую строку, что, по идее, пропорционально длине боковых сторон (а не площади, как при прямом хранении, например, в bmp)
проверить на вхождение в неё точки - вообще простая задачка

можно ещё попробовать вертикальные криволинейные трапеции, они могут быть полезны, когда обрабатывается фигура, у которой верхняя граница сильно изрезана, что приведёт к появлению большого количества маленьких горизонтальных трапеций
так что можно даже как-то переключаться между использованием этих двух типов

Maxim1000- Вы- гений!

Идея с криволинейными трапециями просто прекрасна. Поиск точки гораздо проще. Таблица "шумов" также существенно сокращается. Алгоритм "разбиения" на трапеции осмысливается- там, по крайней мере, на первый взгляд, нет таких сложностей, как с треугольниками.

Однородную область можно разбить на три таких трапеции- центральная и верхняя и нижняя/левая и правая. Остальные совсем уж мелкие непонятные точки- в "шумы".

Приступаю к реалицации.

Ещё раз спасибо за идею.