Hi all,
At work, I had to write a little subroutine that took
the vertices of a rectilinear polygon, decomposed it
into rectangles and returned their vertices. My
solution is pretty long. I thought you guys can do
better!
Here's the problem:
You are given a list of numbers as arguments to your
script. All numbers are integers and denote (x y)
coordinates of each vertex of the polygon. The first
vertex is chosen arbitrarily, but the other vertices
are ordered in a counter-clockwise direction. All
vertices are unique. The polygon is rectilinear, which
means that all angles are 90 degrees.
The program should print to STDOUT the vertices of the
decomposed rectangles: one rectangle per line, each
line containing 4 integers (separated by a single
space and terminated by a newline) which indicate the
top-left and the bottom-right corners of the
rectangle, respectively.
There can be more than one correct solution.
Example:
0,10 4,10
+-----+ 6,9 12,9
| | +---------+
| | | |
| +---+ |
| 4,6 6,6 |
+-------+5,4 |
0,4 | |
| |
+-----------+
5,0 12,0
Input:
5 0 12 0 12 9 6 9 6 6 4 6 4 10 0 10 0 4 5 4
One possible solution:
5 4 12 0
0 6 12 4
0 10 4 6
6 9 12 6
Good luck,
--Ala
__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
