四色定理怎么理解_四色定理的实现（AO+C++）

发布时间：2016-10-24 09:59

  本文关键词：四色定理，由笔耕文化传播整理发布。

    上个星期实现了唯一值渲染后，一直打算实现四色渲染的效果。关于四色定理我也是最近才听说，感觉真的挺奇妙的，所以也吸引我去实现它。

    正好在网上找到了一篇有关四色渲染的学习资料，大致思路和算法也参考了这篇文章。

    首先，四色定理就是无论多么错杂的地图，只须要用四种色彩就能将它区分隔来，这四种颜色可以使相邻的面颜色都不相同。这是1852年英国人弗朗西斯提出来的。直到1976年，美国数学家阿佩尔和哈肯哄骗高速策画机，历时1200小时，，成功的证了然四色题目的正确性。

    实现的思路是通过一个二维矩阵来标识面与面之间的相互关系（相邻为1或不相邻为0），如下A、B、C、D四个面的相互关系：

A B C D A 0 B 1 0 C 1 0 0 D 0 1 1 0

    通过以上矩阵，我们就可以对一维数组color[4]赋值，分别代表A、B、C、D的颜色（用1-4表达）。

    思路大致是这样的：

    第一个赋值1，

    第m个面赋值n（n从1开始），循环判断m与1至m-1个面是否相邻，如果相邻且颜色也相同，那么跳出循环，我们就需要对其赋的颜色n++，并且重新开始循环判断。

    如果m与m-1个面循环判断后没有既相邻又同颜色的，那么m个面可以确定赋值为n。

    但是如果n到4都没有符合条件，那么我们就需要重新对m-1赋值，它的颜色应该+1，并且继续循环判断m-1。

 

    下面是具体代码：

   

color[0] = 1; int m=1, n=1; //m计数，n为颜色 while(m < count) { while(n <= 4 && m < count) { int k = 0; for(k = 0; k < m; k++) { if(rel[m][k] == 1 && color[k] == n) break; } if(k < m) n++; else { color[m] = n; m++; n = 1; } } if(n>4) { m--; n = color[m] + 1; } }

 

AO部分我们需要实现判断两个面是否相邻，这里用的是IRelationalOperator接口，它的Touch方法可以判断两个面是否相邻。这里面index是标识面的一个字段号。

while(ipfeature2) { VARIANT getvar; ipfeature2->get_Value(index, &getvar); i = getvar.intVal; IGeometryPtr ipgeorel; ipfeature2->get_Shape(&ipgeorel); IRelationalOperatorPtr iprelation(ipgeorel); IFeaturePtr ipfeature3; IQueryFilterPtr ipQueryFilter3(__uuidof(QueryFilter)); IFeatureCursorPtr ipcursor3; ipfeacls->Search(ipQueryFilter3, false, &ipcursor3); ipcursor3->NextFeature(&ipfeature3); while(ipfeature3) { ipfeature3->get_Value(index, &getvar); j = getvar.intVal; if(i>= j || rel[i][j] == 1) { ipcursor3->NextFeature(&ipfeature3); continue; } IGeometryPtr ipgeo3; ipfeature3->get_Shape(&ipgeo3); VARIANT_BOOL iftouch, ifequal; iprelation->Touches(ipgeo3, &iftouch); //iprelation->Equals(ipgeo3, &ifequal); if(iftouch == VARIANT_TRUE && i != j) { rel[i][j] = 1; rel[j][i] = 1; } ipcursor3->NextFeature(&ipfeature3); } ipcursor2->NextFeature(&ipfeature2); }

最后附一张效果图

   

 

参考文章：  

  本文关键词：四色定理，由笔耕文化传播整理发布。

本文编号：151352