| Covered Area Problem is a classic algorithm
problem used for academic teaching purposes. The basic idea is to
give several pairs of Cartesian coordinates as the input. Each pair
of coordinate represents the upper-left corner and lower-right corner
of a rectangle. The goal of the system is to find out the total
area covered by all those rectangles. Please note that we can not
just add all the covered area of each rectangles since the rectangles
can be overlapped each other in any order.
Common solution usually implements two dimentional flag mapping.
Each rectange will map several flags covered by it into value 1
(covered). If the flag in a location is already 1, then no change
needed. At the end of the process, the program will count how many
flags have value 1 and that would be the answer.
This common solution has several weaknesses :
1. It consumes a huge size of memory, larger Cartesian coordinates
can not be calculated.
2. Two dimentional array is very difficult to be implemented in
logic and functional programming.
The algorithm used in this article will work on the all coordinates
of integer numbers, meaning the top-left coordinate is (-32768,32767)
and the lower-right coordinate is (32767,-32768). This algorithm
will divide the region into 4 equal subsections. Instead of marking
flags in a two dimentional array (65526 x 65536), this algorithm
will compare each subsection with the rectangles. When a subsection
is totally uncovered, the value 0 will be given. When a subsection
is totally covered, the value 1 will be given. When a subsection
is partially covered, the value 2 will be given and that subsection
will be divided into 4 smaller equal subsections, and the same calculation
will be performed recursively.
The code is very simple. It calculates everything in recursion so
the same algorithm can be implemented in imperative programming
language (C++), functional programming language (Haskell) and logic
programming language (Prolog).
This Haskell version is compiled using Hugs98
compliler.
Any comments, questions, or suggestions can be sent to robertsetiadi@gmail.com.
Related links :
Covered Area Problem (C++ version)
Covered Area Problem (Prolog version)
|