TIN&SQL

Эта страница является черновиком статьи.

Введение

TIN (Triangulated Irregular Network) - Нерегулярная сеть триангуляции, структура данных используемая в ГИС для представления поверхности. Фактически является векторным представлением, её растровым аналогом является DEM (Digital Elevation Model - Цифровая модель высот). TIN основана на Триангуляции Делоне, но не тождественна её, так как последняя является более строгим понятием. TIN состоит из непересекающихся треугольников - это накладывает определённые ограничения (не может быть "пещер" и с вертикальными стенками - тоже беда) и фактически означает, что TIN имеет размерность 2.5D (x, y и z)
Удобство использования TIN заключается в возможности иметь разное "разрешение" для участков с разной сложностью.
В стандарте "Simple feature access" существует возможность хранения TIN, но фактически такая возможность существует только в Oracle Spatial и то - не по стандарту. Также существует потребность обращаться к отдельным элементам TIN. Далее рассмотрим вариант хранения TIN в MySQL.

Структура данных

Структура данных для TIN определяет скорость и удобство работы. В триангуляции можно выделить 3 основных вида объектов: узлы (точки, вершины), рёбра (отрезки) и треугольники.

Рис. 1. Связи между объектами TIN

Возможны следующие структуры данных:

1. «Узлы с соседями»
2. «Двойные рёбра»
3. «Узлы и треугольники»
4. «Узлы, рёбра и треугольники»
5. «Узлы, простые рёбра и треугольники»

СД влияет на два важных момента:

• Поиск нужного объекта
• Внесение изменений и добавления новых объектов

Для поиска лучше п.4 и 5 - так, как существует 3 таблицы и можно искать во всех направлениях. А п. 1 и 2 - лучше для изменений, так нужно минимальное количество действий. Оптимальным для поиска и изменений является п. 3.
Требуется хранить множество поверхностей - по этому будет таблица MySurfaces, а также таблицы MyPoints и MyFaces. Конечно требуются 3D точки, но в MySQL реализованы только 2D точки, по этому, высоту придётся хранить отдельно. В MyFaces будем хранить только указатели на точки.

Рис. 2. Базовая структура БД

В данной структуре нет явного описания рёбер и связей между треугольниками.

Структура таблиц

CREATE TABLE `mysurfaces` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `sname` varchar(45) DEFAULT NULL,
  `Load_Time` datetime DEFAULT CURRENT_TIMESTAMP,
  `boundres` polygon DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE `mypoints` (
  `idMyPoints` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `MyPointscol` point NOT NULL,
  `H` double DEFAULT NULL,
  `SurfID` int(10) unsigned NOT NULL,
  PRIMARY KEY (`idMyPoints`),
  SPATIAL KEY `spi_p` (`MyPointscol`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

CREATE TABLE `myfaces` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `p1` int(10) unsigned NOT NULL,
  `p2` int(10) unsigned NOT NULL,
  `p3` int(10) unsigned NOT NULL,
  `SurfID` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

Рёбра

Нужно получить рёбра. Для этого сделаем три представления:
1. Извлечём рёбра из треугольников (wq_Ribs1) $p1,~p2,~p3\Rightarrow {\begin{matrix}p1,~p2\\p2,~p3\\p3,~p1\end{matrix}}$
Мы получаем двойной набор рёбер – в обе стороны (не считая крайних)

wq_Ribs1

select `myfaces`.`id` AS `id`,`myfaces`.`p1` AS `p1`,`myfaces`.`p2` AS `p2`,`myfaces`.`SurfID` AS `SurfID` from `myfaces` 
union 
select `myfaces`.`id` AS `id`,`myfaces`.`p2` AS `p1`,`myfaces`.`p3` AS `p2`,`myfaces`.`SurfID` AS `SurfID` from `myfaces` 
union 
select `myfaces`.`id` AS `id`,`myfaces`.`p3` AS `p1`,`myfaces`.`p1` AS `p2`,`myfaces`.`SurfID` AS `SurfID` from `myfaces`;

2. Получить ссылки на треугольники (wq_Ribs2)
$p1,~p2\Rightarrow p1,~p2,~t1,~t2$
Объединяем преведущую таблицу с самой собой – по симметричным рёбрам и получаем оба треугольника

wq_Ribs2

select `tbl1`.`SurfID` AS `SurfID`,`tbl1`.`id` AS `t1`,`tbl2`.`id` AS `t2`,`tbl1`.`p1` AS `p1`,`tbl1`.`p2` AS `p2` 
from (`allmyribs` `tbl1` left join `allmyribs` `tbl2` on(((`tbl1`.`p1` = `tbl2`.`p2`) and (`tbl1`.`p2` = `tbl2`.`p1`))));

3. Сортируем ключи слева на право, и удаляем дубликаты (wq_Ribs3) ${\begin{matrix}p1,~p2\\p2,~p1\\p2,~p3\\p3,~p2\\p3,~p1\end{matrix}}\Rightarrow {\begin{matrix}p1,~p2\\p2,~p3\\p1,~p3\end{matrix}}$

wq_Ribs3

select distinct `allmyribs_tri`.`SurfID` AS `SurfID`,
if((`allmyribs_tri`.`p2` < `allmyribs_tri`.`p1`),`allmyribs_tri`.`p2`,`allmyribs_tri`.`p1`) AS `p1`,
if((`allmyribs_tri`.`p2` < `allmyribs_tri`.`p1`),`allmyribs_tri`.`p1`,`allmyribs_tri`.`p2`) AS `p2`,
if((`allmyribs_tri`.`t2` < `allmyribs_tri`.`t1`),`allmyribs_tri`.`t2`,`allmyribs_tri`.`t1`) AS `t1`,
if((`allmyribs_tri`.`t2` < `allmyribs_tri`.`t1`),`allmyribs_tri`.`t1`,`allmyribs_tri`.`t2`) AS `t2` 
from `allmyribs_tri`;

Ссылки

1. http://wiki.gis.com/wiki/index.php/Triangulated_irregular_network
2. http://www.opengeospatial.org/standards/sfa
3. http://www.opengeospatial.org/standards/sfs
4. http://docs.oracle.com/cd/B28359_01/appdev.111/b28400/sdo_tin_pkg_ref.htm#SPATL1207
5. А.В. Скворцов "Триангуляция Делоне и её применение"