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

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

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

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

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

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

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

    思路大致是這樣的：

    第一個(gè)賦值1，

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

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

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

 

    下面是具體代碼：

   

color[0] = 1; int m=1, n=1; //m計(jì)數(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部分我們需要實(shí)現(xiàn)判斷兩個(gè)面是否相鄰，這里用的是IRelationalOperator接口，它的Touch方法可以判斷兩個(gè)面是否相鄰。這里面index是標(biāo)識(shí)面的一個(gè)字段號(hào)。

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); }

最后附一張效果圖

   

 

參考文章：  

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

本文編號(hào)：151352