Programming Assignment 1 - Neat Diagrams

Computer Algorithms II, Fall 2007

Due Date

This assignment is due by 5:30 p.m. on Tuesday, 25 September,

. See the assignment turn-in page (last modified on 14 January 2006) for instructions on turning in your assignment.

Some free-hand sketching programs have the ability to neaten-up diagrams. For example, if a user of such a program produced the diagram on the left, the program might actually output the neat diagram on the right:

The Problem

Write a program that accepts from std-in a free-hand circle-and-stick diagram and writes to std-out a neat version of the input tree.

Assuming a coordinate system in which x increases to the right and y increases going down, a diagram is neat if all the following properties hold:

All circles have the same diameter. The diameter doesn't have be related to the diameter of the sketched circles.
A stick between two circles should be either horizontal, vertical, or at a ± 45° diagonal:
All sticks can be the same length, or you can relate the length of the neat stick to the length of the sketched stick.

Input

Input consists of a sequence of zero or more strokes. Each stroke represents a circle or a stick between two circles.

A stroke is a sequence of four or more integers interpreted as a sequence of two or more (x, y) point coordinates. Each integer is separated from adjacent integers by at least one non-newline space character. Every integer on the same line is part of the stroke defined by the line.

Any number of space characters may appear between adjacent strokes.

A stroke that doesn't appear to be a circle or a stick should be flagged as illegal input.

Output

Output from your program is a sequence of zero or more text lines; successive lines can be separated by zero or more blank lines. A blank line is a sequence of zero or more non-newline space characters ending with a newline; a space character is any character that makes isspace() true. Also, the first line of output may be preceded by zero or more blank lines; the last line of output may be followed by zero or more blank lines.

The word circles followed by a positive integer interpreted as the circle radius followed by a sequence of integers interpreted as a sequence of (x, y) points describing the circle centers:
circles r x₁ y₁ ...
Circle centers may be listed in any order. A valid circles line must have an odd number of integers.
The word sticks followed by a sequence of integers interpreted as a sequence of a sequence of (x, y) points describing stick endpoints:
sticks x_1,1 y_1,1 x_1,2 y_1,2 ...
The first four integers describe the endpoints of the first stick, the second four integers describe the endpoints of the next stick, and so on. Sticks may be listed in any order. A valid sticks line must have an even number of integers.

Adjacent elements in a non-blank output line must be separated by at least one non-newline space character. circles and sticks lines may appear in any order.

If the input is invalid, your program should output to std-err a single error message describing the problem; only the first problem discovered need be reported.

Testing

There are two programs available to test your code. cas-sketch produces input in the format required by your program; cas-show accepts output in the format produced by your program and displays it. Both of these programs can be found in the assignment directory /export/home/class/cs-306/pa1.

Both cas-sketch and cas-show use the X Window System. You must be sitting in front of a system that's running the X window system to to use either program; if you are sitting in front of a system that's not running the X window system, you can't use either program.

If you are sitting in front of a pc running linux and you're running a window manager, then you're sitting in front of a system running the X window system and you can use either program.

If you're sitting in front of a pc running ms software, then you are sitting in front of a system that is not running the X window system and you can't use either program.

However, you may still have problems if you're sitting in from of a system running the X window system. If you have remotely logged into another system (using telnet, rlogin, or rsh) and you're trying to run either program on the remote system, you have to also do the following:

Find the name of your local system using the hostname command:
```
loc: hostname
clayton

loc: 
```
Set and export the DISPLAY environment variable on the remote system to
```
localsystemname:0.0
```
where localsystemname is the name of your local system. For example, type
```
rem: export DISPLAY=clayton:0.0

rem: 
```
if you're using ksh.
On the local host, type
```
xhost + 
```
you should get an message like "access control disabled, clients can connect from any host":
```
loc: xhost +
access control disabled, clients can connect from any host

loc: 
```
If you're paranoid about giving every host access to your screen, you can type instead (on the local host)
```
xhost remotesystemname
```
where remotesystemname is the name of the remote system:
```
loc: xhost cslab18
cslab18 being added to access control list

loc: 
```
You should now be able to run either program on the remote system and have the windows pop up on the local system's screen.

This page last modified on 5 October 2007.