Ӧ
COMPUTER APPLICATIONS
1999 19 10 Vol.19 No.10 1999



һͼĶ˹ϵ㷨
¡Ͼƺ
ժҪһͼĶ˹ϵԶ㷨ʵ㷨ֻͼлεϢ˶ڽǵļȽϣ㷨иͼȡЧĲԣӿ˶Զɵٶȡ
ؼʡ˹ϵΣGIS
A GRAPH-BASED ALGORITHM FOR
GENERATING POLYGONS TOPOLOGICAL RELATIONSHIPS
Zhou LixinYan JingPan Yunhe
State Key Laboratory of CAD & CG, Zhejiang University Zhejiang.Hangzhou 310027
AbstractA graph-based algorithm for generating polygons topological relationships in GIS automatically is presented in this paper. The algorithm needs only a graphs topological information, avoids computing and comparing the polygons interior angles. The algorithm speeds up the generation of polygons topological relationships by taking some effective measures according to the graphs topological features. Finally, an actual example is also shown in the paper.
KeywordsTopological relationships, Polygon, GIS, Arc
1
ϢϵͳGISǽչѸٵһűԵѧƣGISоǹҿƼչƻе֮Ŀռ˹ϵ㷨GISеĹؼ㷨֮һ
ϢϢGISҪصĿռλúͿռϵȱٵĻϢռϢ˹ϵGISݿһҪݡ˹ϵȷ㡢ߡĿռϵԣʵصĲѯ
ԭеĽռͼε㡢ߡ˹ϵ㷨УüϢϢϣжڽǵļȽϣλõıȽϵȣʮַʱһҪһЩĴ3ݡ
㷨ֻÿռҪصϢؽжڽǵļȽϣͼϢӶӿٶȣûҪ
2
һϵеĶ߶βɵߣеת۵(XY)ΪĶ㣬˻״Ľս㣬ÿһս㣺ʼĩ˵㣬ǵսǻĴλ
ΣһϵеĻսɵķһлɶΡȻһһ򼸸εбг֣ÿһֻһΡÿһֻһμ˴ұ֤ڶεı߽粻ص
εСԣһΣڲκ֧Ӷεһ߳˳ʱӻʱѭθöλ֣ᷢȷ˻׼Ƕȣ򹹳ɶεڵĻļнǱСģһʳΪεСԡСԵĶǳΪСΡ
ĶȣһĻ
ӴһΪڵĶУֻΪСУһһСΣ˻ӴһɶСΣΪ
ͼֻ򾭹ʸԶʶ󣬾ԤõµԭʼݣÿһĶ꼰ս꣬뻡ӵ㣬ÿһһʶ(Ϊεڵ)ʶšЩݿԷֱû-ڽӱαʶ-ȱʾ
ǿԽ㡢ΡɵͼοΪһͨͼҪ㷨ǴͼϢ뻡ڽӹϵԻ-ڽӱʾԶеСΣӶε˹ϵɶεıʶɻڽӱ㷨ﲻۡ
3㷨
һ ȡһ߽Ϊʼ㣬Ϊǰ㣻
ڶ Եǰչѡȡһڵǰ㴦ûбչĽ㣬
CASE 1㴦ûбչΪǰĴμ㣬뵱ǰĽ㣬
IF㶼չ
THEN ת岽
ELSE תڶ
CASE 2㴦ѱչγһΣת
 СΣӵǰöQ1Ϊգ
LOOP
IF ͬӦӴС2
THEN ǰһPQ1
ELSE IF дμӦӴС2 THEN ǰһPQ1
ELSE һ(ӦӴС2)һPQ1
ENDIF
ENDIF
PQ1еÿһн(ʼ)бȽϣ
IF PQ1еĽP1Ļ
THEN PP1ĽQ1ȥ(֤εС) 
ENDIF
IF PΪʼ
THEN õһΣתĲ
ELSE תLOOP
ENDIF
Ĳ ÿõһΣɵĻ¼һεıţͬʱɶεĻӴһ
뵱ǰĽ㣬
IF 㶼ѱչ
THEN ת岽
ELSE תڶ
ENDIF
岽 ǰչϣ
IF ûбչͬ
THEN ѡȡһͬΪǰ㣬תڶ
ELSE IF ûбչĴμ THEN ѡȡһμΪǰ㣬תڶ
ELSE ת
ENDIF
ENDIF
 лεӴΪ2 
4㷨
4.1е㷨
ͼ1ʾɶ2ĻǰΪ2Ҫһɶ2Ľʱڽ2 лc3c52ȱ㻡c3c5ķλǣٷֱ뻡c2ļнǣȡнСΪһɶεĻc5õһ7ƣõɶ2л㡣ſɵõСΣ˹ϵÿһ㴦ĶΪmһ㷨У¼㣺ùʽ
=arctg(y2-y1)/(x2-x1)
mηУm(m+1)/2νǶȵıȽϡ

ͼ1
4.2㷨ķ
ڱĵ㷨УֻҪͼϢԶɶε˹ϵؽжڽǵļȽϣ㷨Ҫ㹤ڵʱȡͬ㡢μ㡢ϼȴƽÿһ㴦ֻm(m+1)/2λȽϡ
4.3ȽϷ
ϵķ֪㷨ļСԭ㷨֤ڽε˹ϵʱЧһҡ
5ʵ
ͼ1ʾͼУѵõεĶꡢ꣬롢α롢αʶͼʾڽӱ-12ʾ
1ڽӱ
Ļ
11,2,4
22,3,5
34,6,7
43,10,14
51,6,11
67,8,12
......

2-
ʼֹ
115
212
324
413
527
.........
.........

㷨裺
ѡȡ1Ϊʼ㣬Ϊǰչչ532Ȼѡȡ5Ϊǰչ ...... 1Ϊ1㣬532Ϊ2 ...... չΪ15329674108,ͼ2ʾ

ͼ2
õĶ˽ṹ3ʾ
3-

κɶεĻ
11,4,6
22,4,7,8,9,5
33,5,10
46,7,11,12
58, 12,15,13
69,13,14,10


6
㷨ͼϢԶɶε˹ϵ˽жڽǵļȽϣʹֻͬԻӴС2ĻĲԣ˶ͼлεڽӹϵķСȣСΪ֤εСԶбȽϵĴӶʹ˹ϵԶɵٶȴӿ죬㷨֤˶εСԣ֤зĶΣʹ㷨걸ԡ㷨ûҪ
ڶ˹ϵ㷨ǵϢϵͳеһؼ㷨Ӷһ㷨شʵüֵ
ע863ƻֿܼ֧⡣
߼飺¡ʿоҪоΪCAD/CAMͼѧϢϵͳ
ϾʦҪоΪͼѧ·ơ
ƺסڣʿʦҪоΪ˹ܡͼѧռ
ߵλ㽭ѧCAD & CGصʵҡ㽭.ݣ310027)
ο
1ݡη棬. KCPISĿռģû. ѧ199625(1):63-66
2ݡأ. GISжάռĿķԭԺͳ߶. ѧ 199423(3):315-321
3ݡΰ. ռݽṹо. ѧ磬199511
4ݡ. SIS֯봦. 人Ƽѧ磬1993
5ݡ. . ѧ磬1981
6ݡ޽˹DF. ͼѧ㷨. ѧ磬1987
7ݡHanan Samet. Application of Spatial Data Structures. ADDISON-WESLEY PUBLISHING COMPANY, 1990
ո:1999-06-20(޸ĸ)
