Full Text:   <1966>

CLC number: TP391.72

On-line Access: 

Received: 2009-04-17

Revision Accepted: 2009-08-17

Crosschecked: 2009-08-31

Cited: 0

Clicked: 3579

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2009 Vol.10 No.10 P.1450~1460


A code-based approach for labeling in complex irregular regions

Author(s):  Zhi-long LI, Jun-jie CAO, Xiu-ping LIU, Zhi-xun SU

Affiliation(s):  School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

Corresponding email(s):   zhilongli@gmail.com, xpliu@comgi.com

Key Words:  Labeling, Freeman codes, Region filling, Optimal direction, Shipbuilding

Zhi-long LI, Jun-jie CAO, Xiu-ping LIU, Zhi-xun SU. A code-based approach for labeling in complex irregular regions[J]. Journal of Zhejiang University Science A, 2009, 10(10): 1450~1460.

@article{title="A code-based approach for labeling in complex irregular regions",
author="Zhi-long LI, Jun-jie CAO, Xiu-ping LIU, Zhi-xun SU",
journal="Journal of Zhejiang University Science A",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T A code-based approach for labeling in complex irregular regions
%A Zhi-long LI
%A Jun-jie CAO
%A Xiu-ping LIU
%A Zhi-xun SU
%J Journal of Zhejiang University SCIENCE A
%V 10
%N 10
%P 1450~1460
%@ 1673-565X
%D 2009
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A0920214

T1 - A code-based approach for labeling in complex irregular regions
A1 - Zhi-long LI
A1 - Jun-jie CAO
A1 - Xiu-ping LIU
A1 - Zhi-xun SU
J0 - Journal of Zhejiang University Science A
VL - 10
IS - 10
SP - 1450
EP - 1460
%@ 1673-565X
Y1 - 2009
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A0920214

labeling information in a complex irregular region is a useful procedure occurring frequently in sheet metal and the furniture industry which will be beneficial in parts management. A fast code-based labeler (FCBL) is proposed to accomplish this objective in this paper. The region is first discretized, and then encoded by the Freeman encoding technique for providing the 2D regional information by 1D codes with redundancies omitted. We enhance the encoding scheme to make it more suitable for our complex problem. Based on the codes, searching algorithms are designed and can be extended with customized constraints. In addition, by introducing a smart optimal direction estimation, the labeling speed and accuracy of FCBL are significantly improved. Experiments with a large range of real data gained from industrial factories demonstrate the stability and millisecond-level speed of FCBL. The proposed method has been integrated into a shipbuilding CAD system, and plays a very important role in ship parts labeling process.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1] Alvim, A.C.F., Taillard, E.D., 2009. POPMUSIC for the point feature label placement problem. Eur. J. Oper. Res., 192(2):396-413.

[2] Al-Assaf, Y., 2003. Human strategies based allocation of two-dimensional irregular shapes. J. Intell. Fuzzy Syst., 14(4):181-190.

[3] Bennell, J.A., Oliveira, J.F., 2008. The geometry of nesting problems: a tutorial. Eur. J. Oper. Res., 184(2):397-415.

[4] Bevington, P.R., Robinson, D.K., 1992. Data Reduction and Error Analysis for the Physical Sciences. WCB/McGraw-Hill, Boston.

[5] Binucci, C., Didimo, W., Liotta, G., Nonato, M., 2005. Orthogonal drawings of graphs with vertex and edge labels. Comput. Geom., 32(2):71-114.

[6] Cravo, G.L., Ribeiro, G.M., Lorena, L.A.N., 2008. A greedy randomized adaptive search procedure for the point-feature cartographic label placement. Comput. & Geosci., 34(4):373-386.

[7] Dogrusoz, U., Kakoulis, K.G., Madden, B., Tollis, I.G., 2007. On labeling in graph visualization. Inf. Sci., 177(12):2459-2472.

[8] Draper, N.R., Smith, H., 1998. Applied Regression Analysis. John Wiley & Sons, New York.

[9] Egeblad, J., Nielsen, B.K., Odgaard, A., 2007. Fast neighborhood search for two- and three-dimensional nesting problems. Eur. J. Oper. Res., 183(3):1249-1266.

[10] Farouki, R.T., Neff, C.A., 1990. Analytic properties of plane offset curves. Comput. Aided Geom. Des., 7(1-4):83-99.

[11] Freeman, H., 1961. On the encoding of arbitrary geometric configurations. IEEE Trans. Electron. Comput., 10(2):260-268.

[12] Hearn, D., Baker, M.P., 1997. Computer Graphics (C Version). Prentice Hall, New Jersey.

[13] Henrich, D., 1994. Space-efficient region filling in raster graphics. The Vis. Comput., 10(4):205-215.

[14] Kakoulis, K.G., Tollis, I.G., 2006. Algorithms for the multiple label placement problem. Comput. Geom., 35(3):143-161.

[15] Lan, X., Jiang, Y., Lü, G., Deng, H., 2005. Automatic placement of GIS vector map annotation in area feature by long-diagonal. Geo-Spat. Inf. Sci., 8(4):276-281.

[16] Lee, W.C., Ma, H., Cheng, B.W., 2008. A heuristic for nesting problems of irregular shapes. Comput.-Aided Des., 40(5):625-633.

[17] Liang, L., Ye, J., 2008. A Solution of Irregular Parts Nesting Problem Based on Immune Genetic Algorithm. Int. Symp. on Computational Intelligence and Design, p.217-220.

[18] Mote, K., 2007. Fast point-feature label placement for dynamic visualizations. Inf. Visual., 6(4):249-260.

[19] Pham, B., 1992. Offset curves and surfaces: a brief survey. Comput.-Aided Des., 24(4):223-229.

[20] Ramesh Babu, A., Ramesh Babu, N., 1999. Effective nesting of rectangular parts in multiple rectangular sheets using genetic and heuristic algorithms. Int. J. Prod. Res., 37(7):1625-1643.

[21] Ramesh Babu, A., Ramesh Babu, N., 2001. A generic approach for nesting of 2-D parts in 2-D sheets using genetic and heuristic algorithms. Comput.-Aided Des., 33(12):879-891.

[22] Tang, G.Y., Lien, B., 1988. Region filling with the use of the discrete green theorem. Comput. Vis. Graph. Image Process., 42(3):297-305.

[23] Wolff, A., 2009. The Map Labeling Bibliography. University of Karlsruhe, Karlsruhe, Germany. Available from http://illwww.iti.uni-karlsruhe.de/map-labeling/bibliography/ [Accessed 19/08/09].

[24] Wu, T.H., Chen, J.F., Low, C., Tang, P.T., 2003. Nesting of two-dimensional parts in multiple plates using hybrid algorithm. Int. J. Prod. Res., 41(16):3883-3900.

[25] Yang, H.H., Lin, C.L., 2009. On genetic algorithms for shoe making nesting: a Taiwan case. Exp. Syst. Appl., 36(2):1134-1141.

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE