о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



ڶɼԵİο͹ֽ㷨
Ļ١塡Ȩ
ժҪε͹ֽǼ㼸εĻ֮һӦ.㷨Ϊȫʷ㷨ֲʷ㷨оĺ.ȫַںʱ̫࣬йӦõҪ.Ŀǰֲʷ㷨Rogers㷨ȱݶʵӦܵ.ڶζɼԻϣµľֲʷַ.ðľֲԣͨȨӰĿɼ㴮ѡȡʵĵʷߣðнƽĳɼڱߵĽʷ߽жηֽ.㷨ӦڹPDSOFT PipingУʵ֤Чܺ.
ؼʡ򵥶Σɼԣηֽ⣬㼸
ͼšTP302.4TP391.72
A FAST POLYGON CONVEX DECOMPOSITION ALGORITHM
BASED ON POINT VISIBILITY
JIN Wen-Hua, RAO Shang-Rong, TANG Wei-Qing, and LIU Shen-Quan
(CAD Laboratory, Institute of Computing Technology,
Chinese Academy of Sciences, Beijing 100080)
AbstractPolygon convex decomposition is one of the fundamental problems in computational geometry. It is used in many fields. Most of the algorithms now available are global searching ones. Local searching algorithms are rarely studied. The global searching algorithms waste so much time that they cannot meet the need of all the engineering problems. Presently the most classical local searching method is Rogers algorithm. But as it has many limitations, it is restricted in some actual use. In this paper, a new local searching algorithm is proposed based on the polygon point visibility. The local geometrical property is fully used in the algorithm. The cutting-line is obtained from the concave point to the visible point which is carefully searched from the visible point list of this concave point by using weight function. Alternatively, the cutting-line is found from concave point to the intersection point which is located on the visible point line and the bisector of the concave angle associated with the concave point. The presented algorithm has been applied in the plant design system of PDSOFT Piping, and the results obtained are remarkable.
Key wordssimple polygon, point visibility, polygon decomposition, computational geometry
1
һ򵥶ΣνֽΪͬԵӶεǼ㼸εһ⣬ЩӶͰΣ1ݡΣ1ݡΣ1ݡ͹Σ26ݡΣ6,7ݡζΣ6,8ݡΣ9ݵ.ڶεִʽһǲϣǵǰеĶʷϷʽ35ݣһǲͲϵϣҵף4͹㷨򵥰ηֽΪ͹εĲ.ֻ۽򵥶ηֽΪ͹βϵ.
ε͹ֽ֮أͼѧ10ݡģʽʶ3ݡͼ3ݡԪʷ֣11ݵ.һ򵥶ΣνֽΪٸ͹Ǽ㼸еһ⣬ΪOCD(optimal convex decomposition).ΪһNP-hard⣬B.ChazelleD.P.Dobkin1979귢ָⲢNP-hard⣬Ӧ㷨12.ȻOCDѾпе㷨⣬ʱ޴󣬶ʵʹ.⣬ʵʹУʱҪʷֺ͹ε٣Ҫ͹ε̬Ϻ.ף5ݽ͹̬Ϊʷø͹ڽӴڽǴСӦӽ˵Ǹ͹ڽС.ʵõİʷ㷨ڽֽõ͹̬֮Ѱ.
SchachterDelaunay˼Լ򵥰ν͹ֽ2.ChazelleͨXk(Xk-pattern)㴮ʵ˾Ŀ͹ֽ13.Keilû͹(base convex polygon)ϲ˼͹ֽ14.Ҳвѧ߶Դ˽о35.Ф͵ף3иݰǰڵλùϵб࣬ȻݰԵıѡʷֲ.ף5ͨڿӵ֮佨һȨʷ֣Ȩȿξܼ͹Ŀֿ˷ֽ͹ε̬㷨Ƕף3㷨ĸĽ.
ڶ͹ֽ㷨УǷʹø(Steiner points)ֱӰֽ͹Ŀ.˴ĸָηֽõ͹ζЩԭζĵ.һ£øڼ͹ѡȡʵ͹ε̬.
͹ֽı㣬ˣʷ߾ǴӰ.һ㣬ʷֺ󣬽ֱӦ¶еӦ㣬¶ڸԵĶڿ͹㣬Ҳǰ㣬¶㲻ܶǰ.͹㾭ʷֺ͹.ף3Уʷ֡׼ʷֺ͵ʷֵĸȷʷĿSӦΪ
N/2+1SN+1
УNΪN/2ȡN/2.
2ȫʷֲʷ
򵥶ʷ㷨ϷΪ࣬һÿʷֻһ㣬ֻʷǰ㣬㷨Ϊֲʷ㷨һǴпӰԺпӰ͹ѡȡǰõһʷ(ӵп԰)㷨Ϊȫʷ㷨.ȫʷһ˵Ⱦֲʷֵõ͹̬ãʷᳬֲʷ֣ĴҲСҪķѵʱͿռԶԶֲʷַҲйӦõҪʯPDSOFT Pipingеƽͼֽ(һֹͼֽ)ԶΪ˵.
ڹPDSOFT PipingƽϵͳУԹܵԪ(ӡšͨ)豸Ƚʱ͹㷨15,16ݻ߷1719λԪ豸ȵȻѴλԪ豸λڵͼβü.򵥶αʾ.߷Ķλ϶ǰ.͹㷨õ͹Զø߷İбҪİηֽΪ͹Σͳһõײ͹βü㷨20ݽ.
ƽϵͳУ򵥵ضνȫʷִήϵͳܣΪεȫʷִҪܴʱͿռ俪.ƽУֻҪѰηֽΪ͹ΣҾʹ÷ֽ͹нϺõ̬ͿɽкĲüһҪѰηֽΪٸ͹.
㷨ȫʷ㷨Զԣֲʷ㷨о׽٣ĿǰRogers㷨ǵ͵ľֲʷ㷨.ȻRogers㷨ֽܹⰼΣеȱʹӦܵ.Ϊ˱ڼ򵥶οɼ㷨21ݵĻϣµİξֲʷ㷨.
3Rogers㷨
ڰε͹ֽ㷨У䷽Rogers.F.Davidף10㷨(ĳΪRogers㷨).Rogers㷨ʹøľֲʷ㷨.ͼ1(a)еĶΪҪܸ㷨Ļ˼·.
򵥶Ϊʱ뷽Եʾ.ж͹ԵĶ弰жϷɲμף22.ͼ1(a)ʾ㷨ɴӶεһ(ӵa)صһcӰcbc(Ϊ)ߣ󽻣ȡcĽ㣬ͼ1(b)ʾĵj߶cjһΪõΣabjhiacdefgic.ٷֱͬĴ.һݹ.²ĶξΪ͹ʱݹֹ.ͼ1(c)ʾݹԭİαֽΪ4͹Σabjkahikhcdljcedgle.

ͼ1Rogers㷨ͼ
Rogers㷨ʱ临ӶΪO(mn)УmΪnΪζ.Rogers㷨򵥡ʵ֣µȱݣ
(1).㷨Уÿذиʱ߾εб߽㣬Ӷ㷨Чʲߣ
(2)ʷֲ͹϶.Rogers㷨ʷֵõ͹θϹ̶.Pn㣬m.㷨ÿذиκ󣬰¶зֱӦƽ̹͹.ˣ㷨ÿһиȻһ.ˣRogers㷨ֻ(m+1)͹.ֻе󽻺õԭεİʱһиŻ.ֵĸʺСԣRogers㷨ھµõ͹θΪ(m+1)㷨()
(3)пܲǳϸСǳ΢С͹.ͼ2ʾεİһڱߵļнaСиõ͹ξͻúϸС.̬õ͹ںĶ߲ü㷨мп򸡵½.

ͼ2Rogers㷨ȱ
4ڶɼԵľֲʷ㷨
ֵ̽㷨Rogers㷨һʹøľֲʷַ.򵥶P=(v0,v1,v2,,vn-1)vi,i=0,1,2,,n-1Ϊζ.v0ĵһΪviviΪӵ㣬ף21Ŀɼ㷨ӵviĿɼ㴮ST(s0,s1,,sj).
MΪvi߶ηһµߣNΪvi߶ηһµ.MNֱ߽ƽΪ4ABCDͼ3ʾУ
AMNγɵ(MN)
BMNķγɵ(Nķ)
CNMķγɵ(Mķ)
DMķNķγɵ.

ͼ34
ȻSTеĵֻABCУ3еĵγɵĵ㴮STֲ.SASBSCʾ3㴮.ͼ3ʾSA(s2,s3,s4,s5)SB(s0,s1)SC(s6,s7,s8,s9).
ӿɼ㴮ļԿɵó½ۣ
1.SAΪգSBSCΪգSBеһskSCеĵһsk+1ڶεͬһ.
÷֤֤˽.ͼ4ʾ.sksk+1ͬһϣsksk+1֮ڶζ㣬sksk+1STڵģsksk+1֮Щǲɼ.ʧһԣsksk+1֮һɼĶv.vviAڣͼ4(a)ʾvؿɼ롰vǲɼġìܣv߶εߣͼ4(b)ʾvҲ϶ɼҲ롰vǲɼġìܣvڵұߣvMұߣͼ4(c)ʾ߶Σv,sk+1ݵĽuɼ롰sksk+1STڵġì.v߶Σsk,sk+1ϣvؿɼҲ롰vǲɼġì.ˣsksk+1֮䲻ܴڶζ㣬sksk+1ڶεͬһϣʽ۳.
֤.

ͼ4sksk+1ͬһ
2.SAΪգSBSCزΪ.
ڽ2Ҳ÷֤֤ڴ˲׸.
ܱĻڶɼԵİξֲʷ㷨
(1).ûа㣬㷨İΪǰ㣻
(2)ǰĿɼ㴮STɴȡ㴮SASBSC
(3)SAΪգ
ٵSAж㣬viҲͬʱλĳAУЩ뼯SPУ
ڷ򣬽SAепɼ뼯SPУ
SPеĶֻһΪѡеĵ㣬зSPжȨֵȡȨֵСΪѡеĵ㣺
sjΪSPеһ㣬viɵʸΪMĵλʸΪNĵλʸΪ


ͼ5SPпɼȨֵ
Aƽʸ.ȨֵgjȡʸZֵ

gj=0ʱɼsjAƽϣʱʷߵõ͹̬.
(4)SAΪգɽ2֪SBSCزΪ.skΪSBеһ㣬sk+1ΪSCеĵһ.ɽ1֪sksk+1ڶεͬһ.߶Σsk,sk+1AƽߵĽΪѡĵ㣻
(5)Ӳ34ѡõĵΪuviuʷߣиΣ
(6)²ΰݹؽа͹ֽ⴦ֱеĶξΪ͹Ϊֹ.
жϹУж٣ʹñ㷨ڶviӦĿɼ㴮һֲΧڣһȥ㣬Ӷܼ͹θ.
5ᡡ
ڱ㷨ÿʷִ֮ٻһ㣬㷨ֻmʷֲ.ף21ݿ֪ȡĿɼ㴮㷨ʱ临ӶΪO(n).˱ĵʱ临ӶҲΪO(mn).
Ȼ㷨Rogers㷨ʱ临Ӷͬ㷨ÿʷֲʱȥĸԶRogers㷨(˸ıǵڵĸԶֱϵĸ.֤ڴ˲׸).⣬㷨ʷֲʱ.˱㷨ʵٶȿRogers㷨.
ʷֲڰAнУȨʹʷֵõ͹ξкܺõ̬Ǳ㷨Rogers㷨Ҫɫ.Ȩף5еȨ֮ͬڱķҪǶ.
㷨ӦڹPDSOFT Piping.PDSOFT PipingһΪɹĹڹģͼƽͼϱģȾȷж֮.㷨ƽͼԶĵײ㷨͹ֽеõӦò˺ܺõЧ.
õȻѧĿ(Ŀ69673001).
߼飺ĻУ197010ʿҪоΪCAD/CG㼸ΡƷϢ
ģĿݿ.
٣У197112ʿоҪоΪCAD/CG硢Ż㡡ݿ.
壬У19657оԱҪоΪCAD/CGѧӻ
桢ƷϢģĿݿ.
ȨУ193012оԱʿʦҪоΪCAD/CAMƷ
ϢģCG㼸Ρѧӻ.
ߵλйѧԺ㼼оCADоʵҡ100080
ο
1Asano Tetsuo, Asano Takao. Minimum partition of polygonal regions into trapezoids. In: Proc 24th Annual FOCS Symp. New York: IEEE Computer Press, 1983. 233241
2Schachter B. Decomposition of polygons into convex sets. IEEE Trans on Computers, 1978, C-27(11): 10781082
3Фͣ¬٣ǫ. 򵥶͹Ԫʷֵı㷨. ѧ, 1996, 19(6): 477481
(Xiao Zhonghui, Lu Zhenrong, Zhang Qian. Coding algorithm for decomposing a simple polygon into convex parts(in Chinese). Chinese Journal of Computers, 1996, 19(6): 477481)
4ҵ. 򵥶ηֽ͹βϵ㷨. ͼѧѧ, 1992, 4(2): 2229
(Wang Jiaye, Wang Wei. Algorithm for finding convex decomposition of simple polygons. Journal of Computer-Aided Design & Computer Graphics(in Chinese), 1992, 4(2): 2229)
5Ļԣƽ. һȨʷּ򵥶Ϊ͹ε㷨. ѧ199821(3): 229233
(Wang Zhengxuan, Li Wenhui, Pang Yunjie. A weighting algorithm for decomposing a simple polygon into convex polygons(in Chinese). Chinese Journal Computers, 1998, 21(3): 229233)
6Rourke O J, Supowit J K. Some NP-hard polygon decomposition problems. IEEE Trans on Information Theory, 1983, IT-29(2): 181190
7Feng Houyuan, Pavlidis T. Decomposition of polygons into simpler components: Feature generation for syntactic pattern recognition. IEEE Trans on Computers, 1975, C-24(6): 636650
8Avis D, Toussaint T G. An efficient algorithm for decomposing a polygon into star-shaped polygons. Pattern Recognition, 1981, 13(6): 395398
9Berg M de, Kreveld M van, Overmars M, Schwarzkopf O. Computational Geometry-Algorithms and Applications. Berlin Heidelbery, Germany: Spring-Verlag, 1997. 4955
10Rogers F D. Procedural Elements for Computer Graphics. New York: McGraw-Hill, 1985
11Bykat A. Automatic generation of triangular grid: Isubdivision of a general polygon into convex subregions, IItriangulation of convex polygons. Int'l Journal for Numer Meth Eng, 1976, (10): 13291342
12Chazelle B, Dobkin P D. Decomposing a polygon into its convex parts. In: Proc 11th Annual SIGACT Symp on Theory of Computing. New York: Association for Computer Machinery Inc, 1979. 3848
13Chazelle B, Dobkin P D. Optimal convex decompositions. In: Toussaint T Godfried ed. Computational Geometry, Amsterdam, Holland: North-Holland, 1985. 63133
14Keil M. Decomposing polygons into simpler componentsPh D dissertation. University of Toronto, 1983
15(Ļ, , ƽ. 򵥶εƽ㼯͹ȡ㷨. ѧ, 1998, 21(6): 533539)
(Jin Wenhua, He Tao, Liu Xiaoping et al. A fast convex hull algorithm of planar point set based on sorted simple polygon. Chinese Journal of Computers(in Chinese), 1998, 21(6): 533539)
16Ļ, , . 򵥿ٵƽɢҵ㼯͹㷨. պѧѧ, 1999, 25(1): 7275
(Jin Wenhua, He Tao, Tang Weiqing et al. A simple fast convex hull algorithm of planar point set(in Chinese). Chinese Journal of Beijing Univ of Aero & Astro, 1999, 25(1): 7275)
17Jin Wenhua, Liu Xiaoping, Yu Tiefeng et al. Automatic feature contour recognition of component in piping design CAD system. In: Proc of CAD & Graphics'97, Beijing: International Academic Publishers, 1997. 752755
18ĻΣ. ܵCADԪʶ. ͼѧѧ. 199810()169173
(Jin Wenhua, He Tao, Tang Weiqing et al. Feature contour recognition of component in piping CAD system(in Chinese). Journal of Computer Aided Design & Computer Graphics, 1998, 10(suppl): 169173)
19ĻΣƽ. ĽĹܵCADԪʶ𷽷. ͼѧѧ. 199911(2)147150
(Jin Wenhua, He Tao, Liu Xiaoping et al. Improved feature contour recognition of component in piping CAD system. Journal of Computer Aided Design & Computer Graphics, 1999, 11(2): 147150)
20ĻΣ. ͹δڵĿ߲ü㷨. йͼѧ·չChinagraph'98ļ.  廪ѧ磬1998. 2530
(Jin Wenhua, He Tao, Tang Wei-Qing et al. A fast algorithm for convex polygon line clipping(in Chinese). In: Chinagraph'98. Beijing: Tsinghua University Press, 1998. 2530)
21(ĻΣ. 򵥶οɼĿ㷨. ѧ1999, 22(3): 275282
(Jin Wenhua, He Tao, Tang Weiqing et al. A fast point visibility algorithm for simple polygon(in Chinese). Chinese Journal Computers, 1999, 22(3): 275282)
22Ļ, , . 򵥶ζ͹ԵĿȷ㷨. ͼѧѧ, 1998 (1): 6670
(Jin Wenhua, Tang Weiqing, Tang Rongxi. A fast algorithm for determining the convexity-concavity of vertices of simple polygon. Chinese Journal of Engineering Graphics(in Chinese), 1998, (1): 6670)
ԭյڣ1998-12-23޸ĸյڣ1999-08-31.
