本文關鍵詞：四色定理，由筆耕文化傳播整理發(fā)布。

    上個星期實現(xiàn)了唯一值渲染后，一直打算實現(xiàn)四色渲染的效果。關于四色定理我也是最近才聽說，感覺真的挺奇妙的，所以也吸引我去實現(xiàn)它。

    正好在網(wǎng)上找到了一篇有關四色渲染的學習資料，大致思路和算法也參考了這篇文章。

    首先，四色定理就是無論多么錯雜的地圖，只須要用四種色彩就能將它區(qū)分隔來，這四種顏色可以使相鄰的面顏色都不相同。這是1852年英國人弗朗西斯提出來的。直到1976年，美國數(shù)學家阿佩爾和哈肯哄騙高速策畫機，歷時1200小時，，成功的證了然四色題目的正確性。

    實現(xiàn)的思路是通過一個二維矩陣來標識面與面之間的相互關系（相鄰為1或不相鄰為0），如下A、B、C、D四個面的相互關系：

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

    通過以上矩陣，我們就可以對一維數(shù)組color[4]賦值，分別代表A、B、C、D的顏色（用1-4表達）。

    思路大致是這樣的：

    第一個賦值1，

    第m個面賦值n（n從1開始），循環(huán)判斷m與1至m-1個面是否相鄰，如果相鄰且顏色也相同，那么跳出循環(huán)，我們就需要對其賦的顏色n++，并且重新開始循環(huán)判斷。

    如果m與m-1個面循環(huán)判斷后沒有既相鄰又同顏色的，那么m個面可以確定賦值為n。

    但是如果n到4都沒有符合條件，那么我們就需要重新對m-1賦值，它的顏色應該+1，并且繼續(xù)循環(huán)判斷m-1。

 

    下面是具體代碼：

   

color[0] = 1; int m=1, n=1; //m計數(shù)，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部分我們需要實現(xiàn)判斷兩個面是否相鄰，這里用的是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); }

最后附一張效果圖

   

 

參考文章：  

  本文關鍵詞：四色定理，由筆耕文化傳播整理發(fā)布。

本文編號：151352