Overlap in multiple dimensions is simply the AND of overlap in each dimension.
The 3D case comes up in collision detection.
For collision detection in games, the objects are usually kept in a sorted order, with separate lists for X, Y and Z. Amusingly, a bubble sort is useful, because, as objects move, they tend to move locally, so a bubble sort quickly restores the order. The sorting algorithm should terminate quickly when there are few or no changes. First seen in I-Collide, 1995. When objects are moving slowly, speed is slightly worse than O(N), but degrades if there's too much motion.
2D sorting speeds things up. If you sort the intervals by start X, start Y, you can process the intervals sequentially. Here's something of mine which does that.[1] A MySQL database does the sort, then feeds the data to this algorithm. Overlaps are detected, sets of overlapping objects are merged, and the sets of overlapping 2D rectangles are emitted. Sort is O(N log N) as usual, and overlap detection is O(N).
Have you tried prefix-sum? In my game code I used the Nvidia key/offset sort for a long time, but I've since replaced that for all of my physics and spatial queries.
There are cases where even though the sort executes more instructions that the size of the elements/code still fits into some Ln cache level and makes it faster, but in general the prefix approach comes out ahead.
>>Overlap in multiple dimensions is simply the AND of overlap in each dimension.
Presumably just for boxes aligned with the axes (or some other condition?)? EG two lines can have x’s in common and y’s but not overlap if they are sloped at some angle.
This seemingly no-brainer of a task becomes more intellectually interesting than what you may think on first contact (pun intended).
More so when you have to distinguish between the different types of overlap and non overlap and carry through the reasoning over a chain of overlap/no-overlap relations. I sure underestimated it.
The one dimensional case is covered(there you go again) by Allen algebra. The more richer notion is that of topological relations. I will find the Wikipedia pages and post.
My work involves a lot of time series analysis, as such I'm often dealing with intervals.
While the overlap algorithm (or rather "condition") is cute, there a lot more "cool" stuff to do with intervals, which I would have liked to see in there.
- Checking whether multiple intervals overlap
- Checking whether multiple intervals are contiguous
- Merging contiguous intervals
- Etc..
From experience, something is also crucial when working with intervals: trivially knowing which boundaries are closed and which are opened. I found that defining a strict vocabulary helps a lot here. e.g. "last" is "inclusive", while "end" is exclusive.
[closed; opened[ intervals are also the best when dealing with time intervals (if that makes sense in your use case), because you can trivially join them.
Hmm. I imagine that determining which intervals can be picked to make a continuous span is really a graph-traversal algorithm.
However you aren't just given all the existing edges (pair overlaps) in advance, maybe there's a way to have the graph-exploration side guide the edge-detection to minimize work.
No worries :) Do go through that entire Wiki if you haven't before, somewhat of an gold mine of good (but old) programming tips and tricks. Some information is a bit dated at this point though, but I still think it's one of the best resources out there.
I find it interesting that I don't have a good intuition for the simple condition; instead I have to follow something like the process in the article whenever I want to re-derive that condition.
I wonder how many completely u related applications have that interval check logic coded up somewhere. I'm pretty sure I wrote one for my work codebase. Would I bet my life that the < and <=s are correct? Nope.
I've written code like this to work with overlapping genes. While most genes exist in a genome with spacers between them and their neighboring genes, sometimes you get pairs of genes which overlap, and there seems to be some interesting biology that happens as a consequence.
Even with the visualization, I found the minimal solution hard to visualize. I came up with this instead:
Suppose you start with two separated intervals. The left one starts sliding rightward. At what point do they contact? That's easy, it's just when (end1 > start2).
As it continues sliding, at what point do they lose contact? Again, easy: it's where (start1 >= end2).
So the solution is the first condition and the negation of the second, i.e.: (end1 > start2) && (start1 < end2)
1. Please always make closed and open interval explicit on all code examples. "Detecting overlap" is ambiguous and open intervals have no given solution in the article, if I'm not mistaken.
2. How do you define the empty interval on floating point numbers? How do you define an open interval on floating point numbers? Number representation, input range etc can be very important.
Disclosure: Did some stupidly crazy time series eval for OCPP1.6 and OCPP2.01 charging profiles.
Now write some code to manage collectons of intervals and operations, such as finding if a value is included in a collection of intervals and operations for merging two collections of intervals. What is the best data structure to be used? Explain why?
Overlap in multiple dimensions is simply the AND of overlap in each dimension.
The 3D case comes up in collision detection.
For collision detection in games, the objects are usually kept in a sorted order, with separate lists for X, Y and Z. Amusingly, a bubble sort is useful, because, as objects move, they tend to move locally, so a bubble sort quickly restores the order. The sorting algorithm should terminate quickly when there are few or no changes. First seen in I-Collide, 1995. When objects are moving slowly, speed is slightly worse than O(N), but degrades if there's too much motion.
2D sorting speeds things up. If you sort the intervals by start X, start Y, you can process the intervals sequentially. Here's something of mine which does that.[1] A MySQL database does the sort, then feeds the data to this algorithm. Overlaps are detected, sets of overlapping objects are merged, and the sets of overlapping 2D rectangles are emitted. Sort is O(N log N) as usual, and overlap detection is O(N).
[1] https://github.com/John-Nagle/maptools/blob/main/rust/src/ge...
Have you tried prefix-sum? In my game code I used the Nvidia key/offset sort for a long time, but I've since replaced that for all of my physics and spatial queries.
There are cases where even though the sort executes more instructions that the size of the elements/code still fits into some Ln cache level and makes it faster, but in general the prefix approach comes out ahead.
>>Overlap in multiple dimensions is simply the AND of overlap in each dimension.
Presumably just for boxes aligned with the axes (or some other condition?)? EG two lines can have x’s in common and y’s but not overlap if they are sloped at some angle.
Right, axis-aligned bounding boxes.
Most collision detection systems use axis-aligned bounding boxes as a filter. Then more detailed algorithms are used on possibly-colliding objects.
Interesting, thanks!
This seemingly no-brainer of a task becomes more intellectually interesting than what you may think on first contact (pun intended).
More so when you have to distinguish between the different types of overlap and non overlap and carry through the reasoning over a chain of overlap/no-overlap relations. I sure underestimated it.
The one dimensional case is covered(there you go again) by Allen algebra. The more richer notion is that of topological relations. I will find the Wikipedia pages and post.
https://en.wikipedia.org/wiki/Allen%27s_interval_algebra
https://en.wikipedia.org/wiki/Region_connection_calculus
https://en.wikipedia.org/wiki/Spatial_relation
https://en.wikipedia.org/w/index.php?title=DE-9IM
Interval trees, range trees help if you have a large static set of interval like objects against which you have to relate a query object.
My work involves a lot of time series analysis, as such I'm often dealing with intervals.
While the overlap algorithm (or rather "condition") is cute, there a lot more "cool" stuff to do with intervals, which I would have liked to see in there.
- Checking whether multiple intervals overlap
- Checking whether multiple intervals are contiguous
- Merging contiguous intervals
- Etc..
From experience, something is also crucial when working with intervals: trivially knowing which boundaries are closed and which are opened. I found that defining a strict vocabulary helps a lot here. e.g. "last" is "inclusive", while "end" is exclusive.
[closed; opened[ intervals are also the best when dealing with time intervals (if that makes sense in your use case), because you can trivially join them.
Hmm. I imagine that determining which intervals can be picked to make a continuous span is really a graph-traversal algorithm.
However you aren't just given all the existing edges (pair overlaps) in advance, maybe there's a way to have the graph-exploration side guide the edge-detection to minimize work.
You should write that blog post.
An older, and IMHO slightly more authoritative, source: <https://wiki.c2.com/?TestIfDateRangesOverlap>
See also: <https://martinfowler.com/eaaDev/Range.html>
> older
Hey, _I'm_ a source that's older than that one: <https://stackoverflow.com/a/13513973>
Not so sure about "more authoritative", though.
Bold to claim something you've authored on Stack Overflow is older than C2, the og wiki.
The earliest version I could find on IA is from 2003 (https://web.archive.org/web/20030606033520/http://c2.com/cgi...), last edited in 2002 at that point, but wouldn't surprise me to page was initially created in the 90s.
Hah, damn. I just saw the date at the bottom and ignored the bit that said "last edit".
No worries :) Do go through that entire Wiki if you haven't before, somewhat of an gold mine of good (but old) programming tips and tricks. Some information is a bit dated at this point though, but I still think it's one of the best resources out there.
R-Trees are a good data structure to use in this case, enabling you to query a collection of intervals for overlap with another in O(log(n)) time.
Wikipedia: https://en.wikipedia.org/wiki/R-tree
I find it interesting that I don't have a good intuition for the simple condition; instead I have to follow something like the process in the article whenever I want to re-derive that condition.
I wonder how many completely u related applications have that interval check logic coded up somewhere. I'm pretty sure I wrote one for my work codebase. Would I bet my life that the < and <=s are correct? Nope.
That's what unit tests are for.
or better yet, property tests
I've written code like this to work with overlapping genes. While most genes exist in a genome with spacers between them and their neighboring genes, sometimes you get pairs of genes which overlap, and there seems to be some interesting biology that happens as a consequence.
Here's a package for Python that presumably uses some sort index data structure to be efficient: https://pyranges.readthedocs.io/en/latest/
Even with the visualization, I found the minimal solution hard to visualize. I came up with this instead:
Suppose you start with two separated intervals. The left one starts sliding rightward. At what point do they contact? That's easy, it's just when (end1 > start2).
As it continues sliding, at what point do they lose contact? Again, easy: it's where (start1 >= end2).
So the solution is the first condition and the negation of the second, i.e.: (end1 > start2) && (start1 < end2)
Nice introduction.
1. Please always make closed and open interval explicit on all code examples. "Detecting overlap" is ambiguous and open intervals have no given solution in the article, if I'm not mistaken. 2. How do you define the empty interval on floating point numbers? How do you define an open interval on floating point numbers? Number representation, input range etc can be very important.
Disclosure: Did some stupidly crazy time series eval for OCPP1.6 and OCPP2.01 charging profiles.
I had to do this with 1-day granularity in SQL so we created a Day dimension table and just did a join to detect the overlapping days.
Spacetime overlaps can depend on the velocity of the observer if far enough apart. Not sure if it's worth figuring that into the code.
Now write some code to manage collectons of intervals and operations, such as finding if a value is included in a collection of intervals and operations for merging two collections of intervals. What is the best data structure to be used? Explain why?
I'm saving this for Advent Of Code 2025.
Overlapping intervals were a question back in 2023 so yeah, it's useful