'Merge Overlapping Regions
Given a set of intervals, we can efficiently merge the overlapping intervals using this algorihtm: http://www.geeksforgeeks.org/merging-intervals/
However, if we can a set of multi-dimensional intervals, for example, 2D rectangles or areas in higher dimensions, it becomes unclear how to sort them in the first place. To be clear with the definition over overlap in higher dimension, here is an example. In 2D, [1, 6] x [2, 7] overlaps with [3, 4] x [1, 5], but does not overlap with [3, 4] x [9, 10]. That is, two multidimensional intervals overlaps iff the 1D intervals in each dimension overlaps.
Does anyone have an idea of how to do the merge in higher dimensions? I am interested in which regions are overlapping and can be merged together, instead of the boundaries or shape of the merged regions.
Solution 1:[1]
Sort 1st dimension and merge. Then sort 2nd dimension and merge.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | itix |