Определение простых циклов-2

Продолжение поста "Определение простых циклов плоского связного графа".

Короче, как я и думал, все тривиально. Какой я молодец, что оставил отладочную выдачу.

По задумке в результате последнего вызова перед восхищенными зрителями должен был нарисоваться внешний контур нашей необъятной Родины. Поначалу она так и пошла его очерчивать от фрагмента границы №1 на Чукотке по часовой стрелке (потому что внутренней областью этого региона является вся окружающая плоскость, то есть для нее это, как и для всех, против часов) и благополучно добралась до юга Камчатки. На юге Камчатки имеется фрагмент границы очень маленькой длины.

Рис.1

select g.STLength() from dbo.RegionsBoundaryFragments where id = 419 --6534.55890860261

Когда процедура BuildRegionBoundary до него доходит, у нее по причине его малости съезжает крыша:

Рис.2

Видите, когда она ищет продолжение куска границы №418, в кач-ве кандидатов рассматриваются не только начало следующего куска №419 (как должно было бы быть по уму), но и его конец и начало послеследующего куска №420. Почему граница попилена на такие неравномерные LINESTRINGи - вопрос не ко мне. В таком виде карта лежала в .e00 (см. пост "Как я затаскивал в таблицу карту"). Лично меня бы больше устроило, если каждый LINESTRING был бы изначально равен границе своего региона, чтобы не упражняться в курсе "Начальные алгоритмы теории графов средствами SQL". Но в дареном конспекте на почерк не смотрят. Изо всех кандидатов, как мы помним, отбирается с наибольшим синусом между вектором окончания и вектором продолжения. Конец предыдущего и начало следующего - это одна жирная точка, просто в нашем случае она имеет толщину эпсилон. Наибольший синус оказывается у вектора продолжения, который идет от конца куска 419 к его началу (-419 на первом месте в третьем резалтсете), поэтому она разворачивается и преспокойно идет назад. Дура. Кто ж такой криворукий тебя писал? Первым поворотом налево теперь оказывается граница между Корякским АО и Камчатской обл., поэтому она съезжает туда и довершает обход Камчатской области, как если бы ей сказали exec BuildRegionBoundary @fragment = -419, @eps = 10000. 

Проблема, как и ожидалось, в правильном подборе эпсилон. Сбой происходит из-за того, что 10000 - это много. С горя я его уменьшил до 1000 и все прекрасно заработало. Вот и чудно, я уж было опасался, что придется его делать адаптивным.

update dbo.RegionsBoundaryFragments set region = null

exec BuildRegionBoundary @fragment = 1, @eps = 1000

--00:01:34

--select * from RegionsBoundaryFragments where region = 1

select dbo.OrderedBoundaryToPolygon(1)

Рис.3

Хотя SSMS опять отсебятничает. Корректно ей следовало бы закрасить всю плоскость, кроме России, потому что внутренней областью данного региона является дополнение.

Определяем остальные регионы:

update dbo.RegionsBoundaryFragments set region = null where region > 1

set nocount on

declare @fragment int

while 1 = 1 begin

 select top 1 @fragment = id from RegionsBoundaryFragments where region is null

 if @@rowcount = 0 break

 exec BuildRegionBoundary @fragment = @fragment, @eps = 1000

end

set nocount off

--00:05:19 (отладочная выдача в процедуре выключена)

select * from RegionsBoundaryFragments  

Скрипт 1

Рис.4

По мере того, как скрипт работает, с другого соединения можно наблюдать за прогрессом определения регионов:

Рис.5

По окончании нахождения регионов превращаем их в многоугольники:

if object_id('RegionPolygons', 'U') is not null drop table RegionPolygons

go

select region, dbo.OrderedBoundaryToPolygon(region) g into RegionPolygons from RegionsBoundaryFragments group by region

--00:00:12

select * from RegionPolygons

Скрипт 2

Рис.6

QED. Аплодисменты.

Алексей Шуленин