A rule-based system for dense-map name placement

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A rule-based system for dense-map name placement

Full text

Pdf (4.09 MB)

Source

Communications of the ACM archive
Volume 35 , Issue 1 (January 1992) table of contents

Pages: 68 - 79

Year of Publication: 1992

ISSN:0001-0782

Authors

Jeffrey S. Doerschler	Hamilton Standard, Windsor Locks, CT
Herbert Freeman	Rutgers Univ., New Brunswick, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 45, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129617.129620 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Ahn, and Freeman, H. A program for automatic name placement Proceedings Auto Carto Six (Ottawa, Canada, Oct. 1983) pp. 444-453.
	2	Ahn, J. K. Aummatic name placement system. Tech. Rep. IPI-TR- 0637 Image Processing Laboratory, Electrical Computer, and Systems Engineering Department, Rensselaer Polytecnic Instituie, Troy, N.Y. 12181 May 1984.
	3	Ahn, J.K and Freeman, H. The name-placement problem for maps. Tech Rep. IPL-TR-043. Image Processing Laboratory, Electrical, Computer, and Systems Enginecr.- ing Deparment, Rensselaer Poiytechnic institute, Troy, N.Y, 12181, Mar, 1983.
	4	Balodis, M, Positioning of typogra phy on maps, In ACSM Fall Convention (Salt Lake City, Utah, Sept. 1983), pp. 28-44.
	5	Basoglu, U. A new approach to automated name placement. In Proceedings Auto-Carto V (Crvsi City, Va Aug, 1982), pp,. 103-112.
	6	Basoglu, U. A. new approach to automatcd name placement systems, Ph.D, thiesis, University of Wisconsin, Madison, Wis., 1984.
	7	Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
	8	Jon Louis Bentley , Jerome H. Friedman, Data Structures for Range Searching, ACM Computing Surveys (CSUR), v.11 n.4, p.397-409, Dec. 1979 [doi>10.1145/356789.356797]
	9	Bresenham, J,.E Algorithm for computer control of a digital plotter. IBM Syst, J, 4, I (1965), 25-30.
	10	Cromley, R.G. A spatial allocation analysis of the point annotation problem. In Proceeding Second International Sysmposium on spatial data Handling (Seattle, Wash, July I986, pp. 38-49.
	11	Doerschler, J.S. Data strmtvte, required for overlap detection in an expert map name placement system, Tech. Rep. IPI-FR-477. Image Processding Laboratiny, Eletrica compater, and Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, N.Y. 152181, Aug, 1985.
	12	Doerschler, J.S. Map data production for an expert name placement system. Tech. Rep. IPI-FR-473, Image Processing Laboratory, Electrical, Computer, and Systems. Engineering Department, Rensselaer Polvtechnic Institute. Troy, N.Y. 1281, May 1985.
	13	Jeffrey Scott Doerschler , Herbert Freeman, A rule-based system for dense-map name placement, 1988
	14	Doerschler., J.S. A rule-bascd system for dense-map name placement Tech. Rep. SR-005, Center for Computer Aids fbr lndustriaJ Productvity, Rutgers University, Piscataway, N J. 08855- 1390, Dec 1987.
	15	Easman R. Names placement and positional recall of map information. In Auto-Carto 7 Proceedings, Digital Representation of Spatial knowledge (Wash, DC, Mar. 1985). pp. 4.74 - t872.
	16	Herbert Freeman, Computer Processing of Line-Drawing Images, ACM Computing Surveys (CSUR), v.6 n.1, p.57-97, March 1974 [doi>10.1145/356625.356627]
	17	Freeman, H. Map data processing and the annotation problem. In 3d Skandinarrian Conference on Image Analysis (Copenhagen, July, 1983).
	18	Freeman, H. and Ahn, J.Autonap - An expert system for automatic map name placement. In t'roceeaings International Symposium on Spatial Data Handling (Zurich, Switzerland, Aug. 1984),
	19	Freeman, H. and Ahn, J, A system for automatic name placement. In Proceedings of 4th Jerusalem Conference on Information Technology (Jerusalem, May 1984).
	20	Herbert Freeman , John Ahn, On the problem of placing names in a geographic map, International Journal of Pattern Recognition and Artificial Intelligence, v.1 n.1, p.121-140, April 1987 [doi>10.1142/S0218001487000096]
	21	Freeman, H. and Davis, L, A corner-finding algorithm for chaincoded curves, IEEE Trans. Comput. C-26, 3 (Mar. 1977), 297-303.
	22	Greggains, A. Automated name placement. Cartographica 19, 2 (Summer 1982), 133-135.
	23	Heard, A.M. Automatic correlation of USGS digital line graph geographic features to GNIS names data. Tech. Rep. ETL--0426, Battelle Memorial Institute, Columbus La6oratories, Columbus, Oh. 43201-2693, Aug. 1986. Prepared lbr U.S. Army Corps of Engineers, Engineer Topographic Laboratories, Fort Belvoir, Va. 22060-5546.
	24	Hirsch, S.A. An algorithm for automatic name placement around point data. The American Cartographer 9, I (Apr. 1982), 5-17.
	25	I Love New York Tourism Map. New York State Department of Commerce, Division of Tourism, Albany, N,Y., 1982,
	26	Imhof, E. Tasks and methods ot' theoretical cartography. In International Yearbook of Cartography III, Oretl Fussti Verlag, Zurich, 1963, 13-25.
	27	Imhof, E. Positioning names on maps. The American Cartographer 2, 2 (Oct. 1975), 128-144,
	28	Kelly, P.C. Automated Positioning of Feature Names on Maps. Master's thesis, Department of Geography, State University of New York at Buffalo, Dec. 1980.
	29	Lacroix, V. An improved areafeature name placement. Tech. Rep. IPL-TR-064, Image Processing Laboratory, Electrical, Computer, and Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, N.Y. 12181, Oct. 1984.
	30	Langran, G.E, and Poiker, T.K, Integration of name selection and name placement. In Proceedings Second International Symposium on Spattat Data Handtzng (Seattle, Wash., July tu~o), pp. t~u-o4.
	31	R. D. Merrill, Representation of contours and regions for efficient computer search, Communications of the ACM, v.16 n.2, p.69-82, Feb. 1973 [doi>10.1145/361952.361956]
	32	Metropolitan Albany Schenectady and Troy Fully Indexed Street Map. Marshall Penn-York Co,, Syracuse, N.Y., 1978.
	33	Ugo Montanari, Continuous Skeletons from Digitized Images, Journal of the ACM (JACM), v.16 n.4, p.534-549, Oct. 1969 [doi>10.1145/321541.321543]
	34	Mower, J.E. Name placement of point features through constraint propagation. In Proceedings Second International Symposium on Spatial Data Handling (Seattle, Wash., July 1986), pp. 65-73.
	35	George Nagy , Sharad Wagle, Geographic Data Processing, ACM Computing Surveys (CSUR), v.11 n.2, p.139-181, June 1979 [doi>10.1145/356770.356777]
	36	Nastetin,J, Optimization of baseline determination for area map annotation. Tech. Rep. IPL-TR-078, Image Processing Laboratory, Electrical, Computer, and Systems Engineering Department, Rensselaer Polytechnic Institute, Troy, N.Y. 12181, Aug. 1985.
	37	William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
	38	John L. Pfaltz , Azriel Rosenfeld, Computer representation of planar regions by their skeletons, Communications of the ACM, v.10 n.2, p.119-122, Feb. 1967 [doi>10.1145/363067.363120]
	39	Pfefferkorn, C. et al. Aces: a cartographic expert system. In Auto- Carto 7 Proceedings, Digital Representation of Spatial Knowledge (Wash. DC, Mar. 1985), pp. 399-407.
	40	Phillips, RJ. et al. Searching for names on maps. The Cartographic J. 15, 2 (Dec, 1978), 72-77,
	41	Raisz, E. General Cartography. McGraw-Hilt Book Co., N.Y., t948,
	42	Ramer, U. An iterative procedure for the polygonal approximation of plane curves. Comput. Graph. Image Processing 1, 3 (1972), 244-256.
	43	Robinson, A,H. The Look of Maps: An Examination of Cartographic Design. The University of Wisconsin Press, Madison, Wis., 1952.
	44	Robinson, A.H. and Sale, R.D. Elements of Cartography. John Wiley and Sons, Inc., N.Y., 1969.
	45	Ivan E. Sutherland , Gary W. Hodgman, Reentrant polygon clipping, Communications of the ACM, v.17 n.1, p.32-42, Jan. 1974 [doi>10.1145/360767.360802]
	46	Patrick Henry Winston, Artificial intelligence (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
	47	Yoeli, P. The logic of automated map lettering. The Cartographic J. 9, 2 (Dec. 1972), 99-108.

CITED BY 11

	Konstantinos G. Kakoulis , Ioannis G. Tollis, A unified approach to labeling graphical features, Proceedings of the fourteenth annual symposium on Computational geometry, p.347-356, June 07-10, 1998, Minneapolis, Minnesota, United States
	Chung Keung Poon , Binhai Zhu , Franis Chin, A polynomial time solution for labeling a rectilinear map, Proceedings of the thirteenth annual symposium on Computational geometry, p.451-453, June 04-06, 1997, Nice, France
	Jia Li , Catherine Plaisant , Ben Shneiderman, Data object and label placement for information abundant visualizations, Proceedings of the 1998 workshop on New paradigms in information visualization and manipulation, p.41-48, November 02-07, 1998, Washington, D.C., United States
	Rob Duncan , Jianbo Qian , Antoine Vigneron , Binhai Zhu, Polynomial time algorithms for three-label point labeling, Theoretical Computer Science, v.296 n.1, p.75-87, 4 March 2003
	Srinivas Doddi , Madhav V. Marathe , Andy Mirzaian , Bernard M. E. Moret , Binhai Zhu, Map labeling and its generalizations, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.148-157, January 05-07, 1997, New Orleans, Louisiana, United States
	Marc van Kreveld , Tycho Strijk , Alexander Wolff, Point set labeling with sliding labels, Proceedings of the fourteenth annual symposium on Computational geometry, p.337-346, June 07-10, 1998, Minneapolis, Minnesota, United States
	Jon Christensen , Joe Marks , Stuart Shieber, An empirical study of algorithms for point-feature label placement, ACM Transactions on Graphics (TOG), v.14 n.3, p.203-232, July 1995
	Herbert Freeman, Automated cartographic text placement, Pattern Recognition Letters, v.26 n.3, p.287-297, February 2005
	Konstantinos G. Kakoulis , Ioannis G. Tollis, Algorithms for the multiple label placement problem, Computational Geometry: Theory and Applications, v.35 n.3, p.143-161, October 2006
	Ugur Dogrusoz , Konstantinos G. Kakoulis , Brendan Madden , Ioannis G. Tollis, On labeling in graph visualization, Information Sciences: an International Journal, v.177 n.12, p.2459-2472, June, 2007
	Parinya Chalermsook , Julia Chuzhoy, Maximum independent set of rectangles, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.892-901, January 04-06, 2009, New York, New York