From:

Date:

October 26, 2004 10:57Subject:

Challenge: Polygon to RectanglesMessage ID:

20041026175131.65953.qmail@web52410.mail.yahoo.comHi 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

**Challenge: Polygon to Rectangles**by Ala Qumsieh

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About