extracting.ps

c programming pearls answer

%!PS-Adobe-2.0
%%Copyright: Copyright (c) 1993 AT&T, All Rights Reserved
%%Version: 3.4
%%DocumentFonts: (atend)
%%Pages: (atend)
%%BoundingBox: (atend)
%%EndComments
/DpostDict 200 dict def
DpostDict begin
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 prologue for troff files.
%

/#copies 1 store
/Prologue (dpost.ps) def
/aspectratio 1 def
/formsperpage 1 def
/landscape false def
/linewidth .3 def
/magnification 1 def
/margin 0 def
/orientation 0 def
/resolution 720 def
/rotation 1 def
/xoffset 0 def
/yoffset 0 def

/roundpage true def
/useclippath true def
/pagebbox [0 0 612 792] def

/R  /Times-Roman def
/I  /Times-Italic def
/B  /Times-Bold def
/BI /Times-BoldItalic def
/H  /Helvetica def
/HI /Helvetica-Oblique def
/HB /Helvetica-Bold def
/HX /Helvetica-BoldOblique def
/CW /Courier def
/CO /Courier def
/CI /Courier-Oblique def
/CB /Courier-Bold def
/CX /Courier-BoldOblique def
/PA /Palatino-Roman def
/PI /Palatino-Italic def
/PB /Palatino-Bold def
/PX /Palatino-BoldItalic def
/Hr /Helvetica-Narrow def
/Hi /Helvetica-Narrow-Oblique def
/Hb /Helvetica-Narrow-Bold def
/Hx /Helvetica-Narrow-BoldOblique def
/KR /Bookman-Light def
/KI /Bookman-LightItalic def
/KB /Bookman-Demi def
/KX /Bookman-DemiItalic def
/AR /AvantGarde-Book def
/AI /AvantGarde-BookOblique def
/AB /AvantGarde-Demi def
/AX /AvantGarde-DemiOblique def
/NR /NewCenturySchlbk-Roman def
/NI /NewCenturySchlbk-Italic def
/NB /NewCenturySchlbk-Bold def
/NX /NewCenturySchlbk-BoldItalic def
/ZD /ZapfDingbats def
/ZI /ZapfChancery-MediumItalic def
/S  /S def
/S1 /S1 def
/GR /Symbol def

/inch {72 mul} bind def
/min {2 copy gt {exch} if pop} bind def

/setup {
	counttomark 2 idiv {def} repeat pop

	landscape {/orientation 90 orientation add def} if
	/scaling 72 resolution div def
	linewidth setlinewidth
	1 setlinecap

	pagedimensions
	xcenter ycenter translate
	orientation rotation mul rotate
	width 2 div neg height 2 div translate
	xoffset inch yoffset inch neg translate
	margin 2 div dup neg translate
	magnification dup aspectratio mul scale
	scaling scaling scale

	addmetrics
	0 0 moveto
} def

/pagedimensions {
	useclippath userdict /gotpagebbox known not and {
		/pagebbox [clippath pathbbox newpath] def
		roundpage currentdict /roundpagebbox known and {roundpagebbox} if
	} if
	pagebbox aload pop
	4 -1 roll exch 4 1 roll 4 copy
	landscape {4 2 roll} if
	sub /width exch def
	sub /height exch def
	add 2 div /xcenter exch def
	add 2 div /ycenter exch def
	userdict /gotpagebbox true put
} def

/landscapepage {
	landscape not {
		0 height scaling div neg translate	% not quite
		90 rotate
	} if
} bind def

/portraitpage {
	landscape {
		width scaling div 0 translate	% not quite
		-90 rotate
	} if
} bind def

/addmetrics {
	/Symbol /S null Sdefs cf
	/Times-Roman /S1 StandardEncoding dup length array copy S1defs cf
} def

/pagesetup {
	/page exch def
	currentdict /pagedict known currentdict page known and {
		page load pagedict exch get cvx exec
	} if
} def

/decodingdefs [
	{counttomark 2 idiv {y moveto show} repeat}
	{neg /y exch def counttomark 2 idiv {y moveto show} repeat}
	{neg moveto {2 index stringwidth pop sub exch div 0 32 4 -1 roll widthshow} repeat}
	{neg moveto {spacewidth sub 0.0 32 4 -1 roll widthshow} repeat}
	{counttomark 2 idiv {y moveto show} repeat}
	{neg setfunnytext}
] def

/setdecoding {/t decodingdefs 3 -1 roll get bind def} bind def

/w {neg moveto show} bind def
/m {neg dup /y exch def moveto} bind def
/done {/lastpage where {pop lastpage} if} def

/f {
	dup /font exch def findfont exch
	dup /ptsize exch def scaling div dup /size exch def scalefont setfont
	linewidth ptsize mul scaling 10 mul div setlinewidth
	/spacewidth ( ) stringwidth pop def
} bind def

/changefont {
	/fontheight exch def
	/fontslant exch def
	currentfont [
		1 0
		fontheight ptsize div fontslant sin mul fontslant cos div
		fontheight ptsize div
		0 0
	] makefont setfont
} bind def

/sf {f} bind def

/cf {
	dup length 2 idiv
	/entries exch def
	/chtab exch def
	/newencoding exch def
	/newfont exch def

	findfont dup length 1 add dict
	/newdict exch def
	{1 index /FID ne {newdict 3 1 roll put}{pop pop} ifelse} forall

	newencoding type /arraytype eq {newdict /Encoding newencoding put} if

	newdict /Metrics entries dict put
	newdict /Metrics get
	begin
		chtab aload pop
		1 1 entries {pop def} for
		newfont newdict definefont pop
	end
} bind def

%
% A few arrays used to adjust reference points and character widths in some
% of the printer resident fonts. If square roots are too high try changing
% the lines describing /radical and /radicalex to,
%
%	/radical	[0 -75 550 0]
%	/radicalex	[-50 -75 500 0]
%
% Move braceleftbt a bit - default PostScript character is off a bit.
%

/Sdefs [
	/bracketlefttp		[201 500]
	/bracketleftbt		[201 500]
	/bracketrighttp		[-81 380]
	/bracketrightbt		[-83 380]
	/braceleftbt		[203 490]
	/bracketrightex		[220 -125 500 0]
	/radical		[0 0 550 0]
	/radicalex		[-50 0 500 0]
	/parenleftex		[-20 -170 0 0]
	/integral		[100 -50 500 0]
	/infinity		[10 -75 730 0]
] def

/S1defs [
	/underscore		[0 80 500 0]
	/endash			[7 90 650 0]
] def
end
%%EndProlog
%%BeginSetup
DpostDict begin
mark
/rotation 1 def
/gotpagebbox true def
/linewidth 0.5 def
/xoffset 0 def
/yoffset 0 def
/#copies 1 store
/magnification 1 def
%%FormsPerPage: 1
/formsperpage 1 def
%%Patch from lp
%%EndPatch from lp
/landscape false def
/resolution 720 def
setup
2 setdecoding
%
% Copyright (c) 1993 AT&T, All Rights Reserved
%
% Version 3.4 drawing procedures for dpost. Automatically pulled in when
% needed.
%

/inpath false def
/savematrix matrix def

/Dl {
	inpath
		{pop pop neg lineto}
		{newpath neg moveto neg lineto stroke}
	ifelse
} bind def

/De {
	/y1 exch 2 div def
	/x1 exch 2 div def
	/savematrix savematrix currentmatrix def
	neg exch x1 add exch translate
	x1 y1 scale
	0 0 1 0 360
	inpath
		{1 0 moveto arc savematrix setmatrix}
		{newpath arc savematrix setmatrix stroke}
	ifelse
} bind def

/Da {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arc}
		{newpath arc stroke}
	ifelse
} bind def

/DA {
	/dy2 exch def
	/dx2 exch def
	/dy1 exch def
	/dx1 exch def
	dy1 add neg exch dx1 add exch
	dx1 dx1 mul dy1 dy1 mul add sqrt
	dy1 dx1 neg atan
	dy2 neg dx2 atan
	inpath
		{arcn}
		{newpath arcn stroke}
	ifelse
} bind def

/Ds {
	/y2 exch def
	/x2 exch def
	/y1 exch def
	/x1 exch def
	/y0 exch def
	/x0 exch def
	x0 5 x1 mul add 6 div
	y0 5 y1 mul add -6 div
	x2 5 x1 mul add 6 div
	y2 5 y1 mul add -6 div
	x1 x2 add 2 div
	y1 y2 add -2 div
	inpath
		{curveto}
		{newpath x0 x1 add 2 div y0 y1 add -2 div moveto curveto stroke}
	ifelse
} bind def
/build_12 {
    pop
    /optsize ptsize def
    /osize size def
    /ofont font def

    optsize 2 div dup R exch R f
    0 size 2 mul 3 div dup neg exch 0 exch rmoveto

    (1) show
    rmoveto
    optsize R f
    (\244) show
    f
    (2) show

    optsize ofont f
} def
end
%%EndSetup
%%Page: 1 1
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
1 pagesetup
14 B f
(Extracting Geometric Information)2 2065 1 2027 1725 t
(from Architectural Drawings)2 1747 1 2186 1865 t
10 R f
(Brian W. Kernighan)2 812 1 2023 2283 t
7 R f
(1)2840 2243 w
10 R f
(and Christopher J. Van Wyk)4 1140 1 2908 2283 t
7 R f
(2)4053 2243 w
6 R f
(1)2157 2622 w
9 R f
(Bell Laboratories, Murray Hill, NJ 07974, USA,)6 1750 1 2217 2658 t
9 CW f
([e-mail])2358 2778 w
6 R f
(2)1771 2862 w
9 R f
(Department of Mathematics and Computer Science, Drew University,)7 2522 1 1831 2898 t
(Madison, NJ 07940, USA,)3 958 1 2137 3018 t
9 CW f
([e-mail])3118 3018 w
9 B f
(Abstract.)1614 3393 w
9 R f
( encountered)1 466(We describe some experiments on a geometric problem)7 2020 2 2020 3393 t
( predicting the behavior of indoor wireless commu-)7 1891(while developing a tool for)4 1001 2 1614 3513 t
( is to extract information about the walls of a)9 1703( problem)1 331( The)1 194(nications systems.)1 664 4 1614 3633 t
( descriptions contain)2 806( These)1 292(building from a machine-readable description.)4 1794 3 1614 3753 t
( the former)2 427(much irrelevant or redundant information; the task is to eliminate)9 2465 2 1614 3873 t
( is to use plane)4 577( key geometric idea)3 742( A)1 122(and to reduce the amount of the latter.)7 1451 4 1614 3993 t
( A)1 124( segments in the drawing that belong to the same wall.)10 2093(sweep to \256nd line)3 675 3 1614 4113 t
( this simple idea and its realization, however, and any)9 2037(great gulf lies between)3 855 2 1614 4233 t
(solution must involve a tradeoff among factors like accuracy, speed, and the)11 2892 1 1614 4353 t
(degree and nature of human intervention.)5 1488 1 1614 4473 t
12 B f
(1 Introduction)1 865 1 1331 4848 t
10 R f
( the authors has been part of a group developing the)10 2078(For the past two years one of)6 1159 2 1331 5096 t
8 R f
(WISE)4594 5096 w
10 R f
( design and optimization of indoor wireless)6 1750(\(Wireless System Engineering\) system for)4 1708 2 1331 5216 t
( cordless phones, wireless networks, active)5 1826( and)1 190( Cellular)1 393(communications systems.)1 1049 4 1331 5336 t
( supermarkets are among the many applica-)6 1776(badges, and radio-controlled shelf tags in)5 1682 2 1331 5456 t
( kind of system.)3 669(tions of this)2 491 2 1331 5576 t
8 R f
(WISE)2551 5576 w
10 R f
(requires as input a description of the coordinates)7 2008 1 2781 5576 t
( of a building, and myriad parameters, including power,)8 2275(and composition of the walls)4 1183 2 1331 5696 t
( family of programs computes)4 1228( A)1 128( signal to noise ratios.)4 899(frequency, antenna types, and)3 1203 4 1331 5816 t
( to predict the behavior of the system, to mini-)9 1926(radio energy throughout the building,)4 1532 2 1331 5936 t
( cost by varying the locations of transceivers, and to analyze coverage,)11 2950(mize system)1 508 2 1331 6056 t
( overall system is described in [FGK+95].)6 1679( The)1 205(sensitivity, and other properties.)3 1285 3 1331 6176 t
10 R f
(Developing)1581 6334 w
8 R f
(WISE)2093 6334 w
10 R f
(required solutions to a variety of computational geometry)7 2454 1 2335 6334 t
( to practical are)3 626( that reduce computational time from infeasible)6 1921(problems. Techniques)1 911 3 1331 6454 t
( is about a smaller, subsidiary problem that illustrates)8 2199( paper)1 253( This)1 235(described in [F96].)2 771 4 1331 6574 t
( between the important ideas of computational geometry)7 2255(some pragmatic issues that lie)4 1203 2 1331 6694 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 122 107 489 644
%%EndPage: 1 1
%%Page: 2 2
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
2 pagesetup
10 R f
( community and the dif\256cult real-world problems)6 2030(as viewed by the computer science)5 1428 2 1331 1345 t
(posed by potential users of those ideas.)6 1562 1 1331 1465 t
10 R f
( the coordinates and composition of the walls of the)9 2076(The problem is to determine)4 1132 2 1581 1628 t
( easy to state and to under-)6 1100( Although)1 433( is given.)2 374(building from whatever representation)3 1551 4 1331 1748 t
( most dif\256cult problem faced by users of)7 1735(stand, this seems to be the)5 1119 2 1331 1868 t
8 R f
(WISE)4226 1868 w
10 R f
(. Recent)1 368 1 4421 1868 t
(buildings, say those built within the past decade or two, are often described in some)14 3458 1 1331 1988 t
( ``)1 135(computer-aided design system, usually AutoCAD)4 2162 2 1331 2108 t
8 R f
(DXF)3628 2108 w
10 R f
( We)1 232('' \256les [MvR94].)2 768 2 3789 2108 t
( make them)2 486(attacked the problem of processing AutoCAD drawings mechanically to)8 2972 2 1331 2228 t
(more suitable as building representations for)5 1778 1 1331 2348 t
8 R f
(WISE)3134 2348 w
10 R f
(.)3329 2348 w
12 B f
( AutoCAD DXF Files)3 1087(2 Decoding)1 690 2 1331 2754 t
10 R f
(A)1331 3017 w
8 R f
(DXF)1444 3017 w
10 R f
( de\256nes parameters, a blocks section that)6 1735(\256le contains a header section that)5 1408 2 1646 3017 t
( entities sec-)2 499(de\256nes drafting symbols and common constructs like door frames, and an)10 2959 2 1331 3137 t
( entity has a type, coordinates,)5 1272( Each)1 261( contains all the items in the drawing.)7 1583(tion that)1 342 4 1331 3257 t
( with a ``layer'' of the diagram; the color)8 1640(color, and other parameters, and is associated)6 1818 2 1331 3377 t
(and layer may indicate its role in the diagram or building.)10 2300 1 1331 3497 t
10 R f
(Since)1581 3660 w
8 R f
(DXF)1828 3660 w
10 R f
(\256les are in)2 416 1 2014 3660 t
8 R f
(ASCII)2455 3660 w
10 R f
( can use standard Unix tools to manipulate them.)8 1959(, we)1 166 2 2664 3660 t
(Thus, a 150-line)2 660 1 1331 3780 t
8 R f
(AWK)2020 3780 w
10 R f
([AKW88] program parses)2 1047 1 2239 3780 t
8 R f
(DXF)3314 3780 w
10 R f
(\256les and outputs an)3 784 1 3503 3780 t
8 R f
(ASCII)4315 3780 w
10 R f
(repre-)4552 3780 w
(sentation of line segments: each segment is represented by the \()10 2560 1 1331 3900 t
10 I f
(x)3899 3900 w
10 R f
(,)3951 3900 w
10 I f
(y)3984 3900 w
10 R f
( its)1 123(\) coordinates of)2 630 2 4036 3900 t
(endpoints, an assumed)2 932 1 1331 4020 t
10 I f
(z)2303 4020 w
10 R f
( information about composition that can be)6 1805(-value, and any)2 642 2 2342 4020 t
( program also does any necessary coordi-)6 1657( This)1 229(guessed from the layer and color \256elds.)6 1572 3 1331 4140 t
( inverting)1 394(nate transformations, like clipping,)3 1423 2 1331 4260 t
10 I f
(y)3181 4260 w
10 R f
( Other)1 285(, and converting feet to meters.)5 1279 2 3225 4260 t
8 R f
(AWK)1331 4380 w
10 R f
( line segments; the Unix)4 992(programs process these)2 939 2 1551 4380 t
10 CW f
(sort)3512 4380 w
10 R f
(command puts them into)3 1007 1 3782 4380 t
( [O94] lets us quickly write programs to view the)9 2075(various useful orders; and Tcl/Tk)4 1383 2 1331 4500 t
(data interactively before, during, and after processing.)6 2158 1 1331 4620 t
12 B f
( Extraneous Features)2 1093(3 Removing)1 730 2 1331 5026 t
10 R f
( AT&T's Learning Center, a 3-story conference)6 1992(Figure 1 shows the ground \257oor of)6 1466 2 1331 5289 t
( some information \(like wiring and)5 1431( Although)1 436(center and hotel in Basking Ridge, NJ.)6 1591 3 1331 5409 t
( apparent from what)3 836(pipes\) had already been \256ltered out before we got the data, it is)12 2622 2 1331 5529 t
(remains that)1 501 1 1331 5649 t
8 R f
(DXF)1867 5649 w
10 R f
( contain fea-)2 516( They)1 264( drawings for people.)3 875(\256les are meant to produce)4 1071 4 2063 5649 t
( line segments that represent stairs; arcs or lines that)9 2191(tures like closely spaced, short)4 1267 2 1331 5769 t
(indicate the sweep of doors; cross-hatched elevator shafts and building columns; dot-)11 3458 1 1331 5889 t
(ted and dashed grid lines; line drawings of plumbing \256xtures; and textual annotations.)12 3458 1 1331 6009 t
( lines at the top of Figure 1 underline text that titles the drawing, and)14 2787(For instance, the)2 671 2 1331 6129 t
(the ``arrowhead'' marks the nominal North.)5 1751 1 1331 6249 t
10 R f
( After)1 279( to weed out such extraneous features.)6 1635(Thus, part of the processing is)5 1294 3 1581 6412 t