rectangle-union-area/README.md
2022-04-16 17:33:27 +02:00

32 lines
1 KiB
Markdown

## Problem statement
This solves the following problem:
```
Given a set of rectilinear rectangles in the plane, each by coordinates of opposing corners,
calculate the area of their union.
```
It was a task to show that this is solvable in `O(n^2)` on one of my exercise sheets.
Because I had some spare time, I decided to implement this.
Actually, this can be done in `O(nlog n)` time using a sweepline algorithm
that makes use of [segment trees][st].
The implementation tries to be reasonably fast and respects `nlog n` running time,
but is certainly not too optimized and more of a showcase.
## Build
A standard `C++` installation along with `CMake` should to the job.
Remove the benchmark targets if you do not need them.
## Benchmark
Just for fun, I played around with the [Google Benchmark Library][gl-benchmark].
You will have to install the library and statically link to it to run the
benchmarks.
See the github page of the benchmark library for details.
[gl-benchmark]: https://github.com/google/benchmark
[st]: https://en.wikipedia.org/wiki/Segment_tree