See also: <https://martinfowler.com/eaaDev/Range.html>
Hey, _I'm_ a source that's older than that one: <https://stackoverflow.com/a/13513973>
Not so sure about "more authoritative", though.
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.
Wikipedia: https://en.wikipedia.org/wiki/R-tree
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.
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...
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.
Most collision detection systems use axis-aligned bounding boxes as a filter. Then more detailed algorithms are used on possibly-colliding objects.
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)
Galanwe•4h ago
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.
ambicapter•2h ago
Terr_•1h ago
However you aren't just given all the edges (pair overlaps) that exist in advance, which means there may be ways to have the graph-traversal side guide the edge-detection to minimize work.