Превращение последовательности точек в геометрическую фигуру
Задача. Имеем таблицу из пяти точек, образующих вершины впуклого пятиугольника:
use tempdb
if OBJECT_ID('tempdb..#points', 'U') is not null drop table #points
create table #points (id int identity primary key, p geometry)
insert #points (p) values (geometry::Point(0, 0, 0)),
(geometry::Point(1, 1, 0)),
(geometry::Point(1, -1, 0)),
(geometry::Point(-1, -1, 0)),
(geometry::Point(-1, 1, 0))
select id, p.ToString() from #points
Скрипт 1
Геопространственные типы geometry и geography, будучи по своей природе CLRными, чувствительны к регистру, поэтому метод называется Point, а не POINT.
Рис.1
Требуется соединить эти точки линиями, получив его границу в виде LINESTRING, а затем закрасить внутренность полученного проволочного контура, получив фигуру в виде POLYGON.
Теория в виде BOL советует использовать для этого метод STGeomFromText и ему подобные (STLineFromText, STPolyFromText, ...). К сожалению, для других разновидностей геопространственных типов (LINESTRING, POLYGON, ...) не существует расширенного метода-конструктора, как Point для точки. В свое время мы использовали метод STGeomFromText здесь, см.функцию OrderedBoundaryToPolygon. Повторим данный подход:
declare @i int = (select min(id) - 1 from #points), @p geometry, @s varchar(max) = ''
while (1 = 1) begin
select top 1 @i = id, @p = p from #points where id > @i order by id
if @@ROWCOUNT = 0 break
set @s += cast(@p.STX as varchar) + ' ' + cast(@p.STY as varchar) + ', '
end
select top 1 @p = p from #points order by id
set @s += cast(@p.STX as varchar) + ' ' + cast(@p.STY as varchar)
select geometry::STGeomFromText('LINESTRING(' + @s + ')', 0)
Скрипт 2
Пробегаемся в цикле вдоль таблицы, из каждой записи вытаскиваем содержащуюся в ней точку и добавляем ее координаты в строку, которая затем используется для конструирования LINESTRING. Поскольку я хочу получить замкнутый контур, начальная точка ломаной добавляется в конец @s. В результате получается:
Рис.2
Аналогично ломаной делается многоугольник (с внутренней площадью), только слово LINESTRING в методе STGeomFromText следует заменить на POLYGON, а скобки - на двойные:
select geometry::STGeomFromText('POLYGON((' + @s + '))', 0)
Скрипт 3
Рис.3
Каждая группа внутренних скобок обозначает замкнутый контур, т.е. он должен заканчиваться той же парой координат, что и начинался. Внутренние контуры очерчивают области, не принадлежащие многоугольнику - см. BOL. В нашем случае все ограничивается внешним контуром.
Чем больше точек будет в таблице #points, тем надольше растянется возня со строками, как при выполнении методов XML или динамического SQL. К тому же существует опасение, что будучи интерпретируемым, код T-SQL может подтормаживать при интенсивных строковых операциях. Имеется замечательный метод STConvexHull, который умеет натягивать на коллекцию точек минимальную выпуклую оболочку. К сожалению, он непригоден в данном случае, т.к. наш многоугольник вогнутый:
declare @i int = (select min(id) - 1 from #points), @g geometry = geometry::STGeomCollFromText('GEOMETRYCOLLECTION EMPTY', 0)
while (1 = 1) begin
select top 1 @i = id, @g = @g.STUnion(p) from #points where id > @i order by id
if @@ROWCOUNT = 0 break
end
select @g.STConvexHull()
Скрипт 4
Рис.4
В качестве альтернативы практика советует использовать не строковое (WKT = well-known text), а бинарное (WKB = well-known binary) представление геопространственных величин. Над геопространственными типами определен метод STAsBinary, который возвращает бинарное представление геометрического объекта в формате WKB. Обратным ему служит статический метод STGeomFromWKB и родственные (STPointFromWKB, STLineFromWKB, …) методы. Чтобы оперировать бинарным представлением, для начала хорошо бы вообще знать, как оно устроено. Например, вот бинарное представление точки:
select geometry::STPointFromText('POINT(1 2)', 0).STAsBinary()
--------------------------------------------------------------------------------
(No column name)
0x0101000000000000000000F03F0000000000000040
Скрипт 5
Что здесь к чему, какой байт за что отвечает? К сожалению, документация на эту тему крайне лаконична, а без этого знания использование вышеприведенных методов теряет смысл. Информацию об устройстве формата WKB можно почерпнуть на сайте компании Environmental Systems Research Institute, более известной, как ESRI, которая тоже поддерживает стандарты Open Geospatial Consortium (OGC).
Первый (левый) байт в этой последовательности обозначает порядок сортировки байт в координатах. 0х00 = Big Endian, 0х01 = Little Endian. Затем идет последовательность из 4-х байт, обозначающая разновидность геопространственного типа. 0x01000000 = Point, 0x02000000 = LineString, 0x03000000 = Polygon, 0x04000000 = MultiPoint, 0x05000000 = MultiLineString, 0x06000000 = MultiPolygon, 0x07000000 = GeometryCollection, 0x08000000 = CircularString, 0x09000000 = CompoundCurve, 0x0a000000 = CurvePolygon.
Для точки WKBPoint {byte byteOrder; uint32 wkbType; Point point; } затем идут два 8-байтовых представления координат Point {double x; double y;} - 000000000000F03F 0000000000000040, или Х = 1, Y = 2 в кодировке Little Endian.
Для ломаной WKBLineString {byte byteOrder; uint32 wkbType; uint32 numPoints; Point points[numPoints]; } между обозначением разновидности геопространственного типа и координатами дополнительно имеется еще 4-байтное целое, обозначающее кол-во точек в ломаной. Например,
select geometry::STLineFromText('LINESTRING(1 2, 2 1)', 0).STAsBinary()
--------------------------------------------------------------------------------
(No column name)
0x01 02000000 02000000 000000000000F03F 0000000000000040, 0000000000000040 000000000000F03F
Скрипт 6
Фиолетовым цветом показан порядок сортировки Big/Liitle Endian (byte byteOrder), зеленым - тип геометрии (uint32 wkbType), жирным цветом - кол-во точек в фигуре (uint32 numPoints), голубым - координаты первой точки, непонятным - координаты второй.
Для многоугольника WKBPolygon {byte byteOrder; uint32 wkbType; uint32 numRings; LinearRing rings[numRings]; } после обозначения разновидности геопространственного типа добавляется еще одно 4-байтное целое - uint32 numRings - кол-во замкнутых контуров границы. Каждый контур LinearRing {uint32 numPoints; Point points[numPoints]; }. Т.е. в случае одного контура дальше идет просто кол-во точек и их координаты. Например,
select geometry::STPolyFromText('POLYGON((1 2, 2 1, 0 0, 1 2))', 0).STAsBinary()
--------------------------------------------------------------------------------
(No column name)
0x01 03000000 01000000 04000000 000000000000F03F 0000000000000040, 0000000000000040 000000000000F03F, 0000000000000000 0000000000000000, 000000000000F03F 0000000000000040
Скрипт 7
Здесь наклонным цветом показано кол-во контуров, жирным - кол-во точек в контуре, далее разноцветным цветом - их координаты. Несмотря на то, что это треугольник, кол-во точек = 4, потому что замкнутый контур должен оканчиваться на ту же точку, с которой начинался. Форматы остальных разновидностей геопространственных типов 4 - 7 можно посмотреть там же, на сайте ESRI. Форматы 8 - 10 соответствуют дугам вместо отрезков и собранным из них "ломаным" и "многоугольникам", которые появились в Денали, поэтому их разбор предоставляется читателям в качестве самостоятельного упражнения.
Теперь совершенно очевидно, как при помощи бинарного представления WKB построить ломаную из точек таблицы #points аналогично Рис.2:
declare @i int = (select min(id) - 1 from #points), @b varbinary(max) = cast('' as varbinary)
while (1 = 1) begin
select top 1 @i = id, @b += substring(p.STAsBinary(), 6, 16) from #points where id > @i order by id
if @@ROWCOUNT = 0 break
end
select top 1 @b += substring(p.STAsBinary(), 6, 16) from #points order by id
declare @numPoints int = (select count(1) + 1 from #points)
select geometry::STGeomFromWKB(0x01 + 0x02000000 + cast(reverse(cast(@numPoints as binary(4))) as binary(4)) + @b, 0)
Скрипт 8
В переменной @b будут накапливаться координаты точек ломаной. Перед началом работы цикла мы инициализируем ее в пустоту. Обратите внимание: не в 0, а в пустоту. Особенность типа binary состоит в том, что ноль не является пустотой. Например,
declare @b varbinary(max) = 0
select @b + 0x01
--------------------------------------------------------------------------------
(No column name)
0x0000000001
Скрипт 9
Инициализация нулем означает, что в @b будет содержаться 4-байтное число = 0, и добавление 0х01 прибавит единичку 5-м байтом. Аналогично,
declare @b varbinary(max) = 0x0
select @b + 0x01
--------------------------------------------------------------------------------
0x0001
Скрипт 10
изменит ситуацию только тем, что 0 будет содержаться не в виде 4-х байтов, а только одного, и 0х01 добавится 2-м байтом. Если же нужно, чтобы перед инкрементом @b в ней вообще ничего не содержалось, ее следует инициализировать пустой строкой с последующей конвертацией к бинарному типу.
Пробегаясь по точкам таблицы, мы из бинарного представления каждой вытаскиваем ее координаты Х и Y, которые, как мы видели в Скрипте 5, начинаются с 6-го байта (1-й байт = byteOrder, затем 4 байта wkbType) и имеют длину по 8 байт, т.е. 16 байт общей длины. Я использую функцию substring, а не, скажем, right, потому что substring от бинарного типа дает снова бинарный тип, а right - varchar, который нужно было бы затем преобразовывать к varbinary.
По окончании работы цикла имеем в переменной @b бинарное представление координат всех точек таблицы #points в порядке id. Как и в Скрипте 2, добавляем в конец первую точку, чтобы ломаная вышла замкнутой.
В соответствии со Скриптом 6 префиксуем будущую LINESTRING признаком кодировки Little Endian (0x01), признаком того, что это будет LINESTRING (0х02000000) и количеством точек в ней = (select count(1) from #points) + 1, потому что начальная точка является и конечной. Это количество надо превратить в 4 байта - cast(… as binary(4)). Конвертация целого при помощи cast/convert дает последовательность байт в формате Little Endian. Но в этом формате кодируются только координаты точек, о чем говорит 1-й байт бинарного представления геопространственного объекта. Остальные атрибуты должны быть закодированы Big Endian. Следовательно, байты в полученной последовательности надо перевернуть (функция reverse), и, поскольку она возвращает строку, результат нужно обратно конвертировать в бинарный тип (внешний cast). В конце добавляются собранные в цикле координаты точек (@b). Результат Скрипта 8 идентичен Рис.2.
Если требуется получить многоугольник (ломаную вместе с очерченной ею замкнутой областью), это опять-таки можно сделать с помощью бинарного представления. Скрипт 8 остается без изменения, только в последнем selectе разновидность геометрического типа следует заменить на 0x03000000 (POLYGON). Далее (см. Скрипт 7) должно идти кол-во контуров границы 0х01000000. Далее - кол-во точек в первом контуре и их координаты. Это было задано для LINESTRING в Скрипте 8. Так как наш многоугольник имеет границу из одного контура, больше ничего добавлять не нужно.
select geometry::STGeomFromWKB(0x01 + 0x03000000 + 0x01000000 + cast(reverse(cast(@numPoints as binary(4))) as binary(4)) + @b, 0)
Скрипт 11
В итоге получаем тот же многоугольник, что и при помощи WKT на Рис.3.
Сравнение производительности WKT- и WKB-способов поточечного рисования многоугольника:
--WKT
dbcc dropcleanbuffers
dbcc freeproccache
declare @i int = (select min(id) - 1 from #points), @p geometry, @s varchar(max) = ''
while (1 = 1) begin
select top 1 @i = id, @p = p from #points where id > @i order by id
if @@ROWCOUNT = 0 break
set @s += cast(@p.STX as varchar) + ' ' + cast(@p.STY as varchar) + ', '
end
select top 1 @p = p from #points order by id
set @s += cast(@p.STX as varchar) + ' ' + cast(@p.STY as varchar)
select geometry::STGeomFromText('POLYGON((' + @s + '))', 0)
go
--WKB
dbcc dropcleanbuffers
dbcc freeproccache
declare @i int = (select min(id) - 1 from #points), @b varbinary(max) = cast('' as varbinary)
while (1 = 1) begin
select top 1 @i = id, @b += substring(p.STAsBinary(), 6, 16) from #points where id > @i order by id
if @@ROWCOUNT = 0 break
end
select top 1 @b += substring(p.STAsBinary(), 6, 16) from #points order by id
declare @numPoints int = (select count(1) + 1 from #points)
select geometry::STGeomFromWKB(0x01 + 0x03000000 + 0x01000000 + cast(reverse(cast(@numPoints as binary(4))) as binary(4)) + @b, 0)
Скрипт 12
говорит, однако, что по количеству операций чтения первый способ оказывается выгоднее, хотя проигрывает по времени выполнения:
Рис.5
Думаю, что 5 точек границы, которые были взяты, чтобы проиллюстрировать подходы, – слишком малая величина, чтобы делать общие выводы. Сравнение производительности на статистически значимых объемах предоставляется читателям в качестве самостоятельного упражнения.
Алексей Шуленин