作者
digoal
日期
2019-04-21
标签
PostgreSQL , 四色猜想 , Four_color_theorem , 泰森多边形 , 网络 , 基站 , ST_GeometryN , postgis , ST_NumGeometries , ST_VoronoiPolygons , ST_VoronoiLines , st_union
背景
最强大脑的题目，四色猜想，在几百个泰森多边形中，给定一个起始多边形和它的颜色，给多边形上色，要求符合四色原理。指定一种目标色，尽可能的使得目标色最少。
四色问题又称四色猜想、四色定理，是世界近代三大数学难题之一。地图四色定理（Four color theorem）最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。
四色问题的内容是“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”也就是说在不引起混淆的情况下一张地图只需四种颜色来标记就行。
用数学语言表示即“将平面任意地细分为不相重叠的区域，每一个区域总可以用1234这四个数字之一来标记而不会使相邻的两个区域得到相同的数字。”这里所指的相邻区域是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。
The Notorious Four-Color Problem
例子
使用以下文章中的tc表。
《在PostgreSQL中生成和查看泰森多边形 - Voronoi diagram》
```
增加一个字段，存储这个泰森多边形的颜色。
alter table tc add column color int;
1,2,3,4 分别代表四种颜色。
```
1、创建插件
create extension postgis;
create extension intarray;
2、创建依赖函数1，两个数组相减。
```
-- 求 array A - array B
create or replace function array_remove(
int[], -- A
int[] -- B
) returns int[] as $$
declare
res int[] := $1;
x int;
begin
foreach x in array $2 loop
res := array_remove(res,x);
end loop;
return res;
end;
$$ language plpgsql strict;
```
3、创建依赖函数2，选择目标色，排除周边多边形已有颜色，并降低目标色的优先级
```
-- 选择有效目标颜色, 并尽量排除目标颜色, 使这种颜色的多边形最少
create or replace function array_remove_sel(
int[], -- 四色
int[], -- 相邻多边形已上色集合
int -- 目标颜色, 尽量使这种颜色的多边形最少
) returns int as $$
declare
tmp int[] := array_remove($1, $2);
tmp1 int[] := array_remove(tmp, array[$3]);
s int;
begin
if tmp = '{}'::int[] then
return null;
elsif tmp = array[$3] then
return $3;
else
s := ceil(random()*array_length(tmp1,1))::int;
return tmp1[s];
end if;
end;
$$ language plpgsql strict;
```
4、给泰森多边形上色(以下DO的逻辑有问题，无法对所有多边形按四色定理上色)，由于没有全局判断，所以实际上有些色上了之后可能影响后面的约束，导致最后有些多边形无法上色（违反约束）
```
do language plpgsql $$
declare
tmpvids int[] := array[80];
allvids int[] := tmpvids;
tmpcolors int[];
x int;
begin
-- 起始多边形为ID=80的多边形，起始多边形颜色为2
update tc set color=2 where id=80;
loop
select uniq(sort(array_agg(tc.id))) into tmpvids from
tc
join
(select id,poy from tc where id = any (tmpvids)) t
on
( st_intersects(tc.poy, t.poy)
and GeometryType(ST_Intersection(tc.poy, t.poy)) <> 'POINT'
)
where tc.id <> all (allvids);
if tmpvids is null then exit; end if;
foreach x in array tmpvids loop
select uniq(sort(array_agg(tc.color))) into tmpcolors from
tc, (select * from tc where id=x) t
where st_intersects(tc.poy, t.poy)
and GeometryType(ST_Intersection(tc.poy, t.poy)) <> 'POINT'
and tc.color is not null;
-- 目标色为1，（即要求1的颜色最少）
update tc set color=array_remove_sel(array[1,2,3,4], tmpcolors, 1) where id=x;
end loop;
raise notice '%', tmpvids;
allvids := uniq(uniq(array_cat(allvids, tmpvids)));
end loop;
raise notice '%', array_length(allvids,1);
end;
$$;
```
或
```
do language plpgsql $$
declare
tmpvids int[] := array[80];
tmpvids_sorted text[] := '{}'::text[];
allvids int[] := tmpvids;
tmpcolors int[];
tmptext text;
x int;
i int;
begin
-- 起始多边形为ID=80的多边形，起始多边形颜色为2
update tc set color=2 where id=80;
loop
-- 找出相邻未上色多边形
select uniq(sort(array_agg(tc.id))) into tmpvids from
tc
join
(select id,poy from tc where id = any (tmpvids)) t
on
( st_intersects(tc.poy, t.poy)
and
GeometryType(ST_Intersection(tc.poy, t.poy)) <> 'POINT'
)
where tc.id <> all (allvids);
-- 如果已经没有未上色的相邻多边形，说明所有多边形都已经上色
if tmpvids is null then exit; end if;
-- 统计相邻多边形的相邻多边形数据
i := 1;
foreach x in array tmpvids loop
select x||'_'||count(*) into tmptext from
tc
join
(select id,poy from tc where id = x) t
on
( st_intersects(tc.poy, t.poy)
and
GeometryType(ST_Intersection(tc.poy, t.poy)) <> 'POINT'
) ;
tmpvids_sorted[i] := tmptext;
i := i+1;
end loop;
raise notice '%', tmpvids_sorted;
-- 相邻多边形的相邻多边形越多的，优先上色
i := 1;
for x in select split_part(unnest, '_', 1) from unnest(tmpvids_sorted) order by split_part(unnest, '_', 2) desc loop
select uniq(sort(array_agg(tc.color))) into tmpcolors from
tc, (select * from tc where id=x) t
where st_intersects(tc.poy, t.poy)
and GeometryType(ST_Intersection(tc.poy, t.poy)) <> 'POINT'
and tc.color is not null;
-- raise notice '%', x;
-- 目标色为1，（要求1的颜色对应的多边形数量最少）
if i=1 and (not arraycontains(tmpcolors,array[1])) then
update tc set color=1 where id=x;
else
update tc set color=array_remove_sel(array[1,2,3,4], tmpcolors, 1) where id=x;
end if;
i := i+1;
end loop;
-- raise notice '%', tmpvids;
allvids := uniq(uniq(array_cat(allvids, tmpvids)));
end loop;
raise notice '%', array_length(allvids,1);
end;
$$;
```
5、验证是否满足四色猜想。
do language plpgsql $$
declare
x int;
tmpcolor int;
tmpcolors int[];
begin
for x in select id from tc where color is not null loop
select color into tmpcolor from tc where id=x;
select uniq(sort(array_agg(tc.color))) into tmpcolors from
tc, (select * from tc where id=x) t
where st_intersects(tc.poy, t.poy)
and GeometryType(ST_Intersection(tc.poy, t.poy)) <> 'POINT'
and tc.id<>x
and tc.color is not null;
if arrayoverlap(array[tmpcolor], tmpcolors) then
raise notice 'ID: %, color: %, sidecolors: %', x, tmpcolor, tmpcolors;
end if;
end loop;
end;
$$;
6、查询每种颜色有多少个多边形。
digoal=# select color,count(*) from tc group by 1 order by 2;
color | count
-------+-------
| 68
1 | 178
3 | 248
4 | 249
2 | 257
(5 rows)
参考
https://baike.baidu.com/item/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86/805159?fromtitle=%E5%9B%9B%E8%89%B2%E7%8C%9C%E6%83%B3&fromid=198855
https://en.wikipedia.org/wiki/Four_color_theorem
http://jlmartin.faculty.ku.edu/~jlmartin/MiniCollege2013/handout.pdf
https://gis.stackexchange.com/questions/132831/calculate-color-of-object-so-no-adjacent-objects-repeat
PostgreSQL 许愿链接
您的愿望将传达给PG kernel hacker、数据库厂商等, 帮助提高数据库产品质量和功能, 说不定下一个PG版本就有您提出的功能点. 针对非常好的提议，奖励限量版PG文化衫、纪念品、贴纸、PG热门书籍等，奖品丰富，快来许愿。开不开森.
9.9元购买3个月阿里云RDS PostgreSQL实例
PostgreSQL 解决方案集合
德哥 / digoal's github - 公益是一辈子的事.
