Simple C++ implementation to find area of union of rectilinear rectangles.
Go to file
Maximilian Keßler 279ca3bd14 update gitignore 2022-04-17 13:14:19 +02:00
.gitignore update gitignore 2022-04-17 13:14:19 +02:00
CMakeLists.txt restructure cmakelists.txt 2022-04-17 13:04:47 +02:00
LICENSE Add LICENSE 2022-04-16 15:34:09 +00:00
README.md add README 2022-04-16 17:33:27 +02:00
areas.cpp fix bug: multipliy area with distance up to next y point 2022-04-16 12:36:25 +02:00
areas.h refactor into multiple files 2022-04-16 11:41:48 +02:00
benchmark.cpp add single instance for benchmark 2022-04-16 21:18:34 +02:00
geometry.h implement segment tree 2022-04-16 11:34:29 +02:00
main.cpp add some more checks in main file for correctness 2022-04-16 13:21:31 +02:00
segment_tree.cpp add bottom case when updating covered lengths 2022-04-16 13:18:16 +02:00
segment_tree.h add bottom case when updating covered lengths 2022-04-16 13:18:16 +02:00

README.md

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.

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. 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.