develooper Front page | perl.golf | Postings from October 2004

Challenge: Polygon to Rectangles

From:
Ala Qumsieh
Date:
October 26, 2004 10:57
Subject:
Challenge: Polygon to Rectangles
Message ID:
20041026175131.65953.qmail@web52410.mail.yahoo.com
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 



nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About