3 ms·

One detail of interval arithmetic not mentioned in TFA but of much consequence in the context in which we have to contend with in Ardour is ... When you ask if

One detail of interval arithmetic not mentioned in TFA but of much consequence in the context in which we have to contend with in Ardour is ... When you ask if a single non-interval lies within a given interval, the answer is yes or no (with a given resolution). When you ask what the relationship between 2 intervals is, there are multiple answers (*). In a given problem domain, each one may have different semantic implications. (*) interval 1 is larger than interval 2 and fully includes it interval 2 is larger than interval 1 and fully includes it interval 1 begins before interval 2 interval 1 ends after interval 2 interval 2 begins before interval 1 interval 2 ends after interval 1 interval 1 and interval 2 are disjoint interval 1 and interval 2 are equivalent at a given resolution

simpaticoder 2y ago
This problem came up for me when writing a tool to help an author index his work. He wanted to be able to enter reference ranges for a term and then combine, including disjoint ones, into a single entry. (There was also a roman numeral problem irrelevant here). This has also come up for me in two dimensions when dealing with overlapping rectangles. For some reason the complexity of it surprised me both times. Sadly computing these cases is a straight-forward slog in 1-D; you can however reuse the solution for higher dimensions in a nice way.
- mikhailfranco 2y ago
  Most spatial databases use the R-Tree or one of its variants: https://en.wikipedia.org/wiki/R-tree https://en.wikipedia.org/wiki/R-tree e.g. PostGIS has GiST-RTree: https://postgis.net/docs/manual-3.2/using_postgis_dbmanagement.html#build-indexes https://postgis.net/docs/manual-3.2/using_postgis_dbmanageme...
mikhailfranco 2y ago
Allen's interval algebra describes the 2*6+1 = 13 relations: https://en.wikipedia.org/wiki/Allen's_interval_algebra https://en.wikipedia.org/wiki/Allen's_interval_algebra It's possible to build a graph where the relations are nodes, and the edges are possible smooth operations on the intervals (e.g. translation). Then you have a state machine for smooth system evolution.
- PaulDavisThe1st 2y ago
  Right, I should have linked to that (or something like it) rather than trying to write out my own list.

simpaticoder 2y ago

This problem came up for me when writing a tool to help an author index his work. He wanted to be able to enter reference ranges for a term and then combine, including disjoint ones, into a single entry. (There was also a roman numeral problem irrelevant here). This has also come up for me in two dimensions when dealing with overlapping rectangles. For some reason the complexity of it surprised me both times. Sadly computing these cases is a straight-forward slog in 1-D; you can however reuse the solution for higher dimensions in a nice way.

mikhailfranco 2y ago
Most spatial databases use the R-Tree or one of its variants: https://en.wikipedia.org/wiki/R-tree https://en.wikipedia.org/wiki/R-tree e.g. PostGIS has GiST-RTree: https://postgis.net/docs/manual-3.2/using_postgis_dbmanagement.html#build-indexes https://postgis.net/docs/manual-3.2/using_postgis_dbmanageme...

mikhailfranco 2y ago

Allen's interval algebra describes the 2*6+1 = 13 relations: https://en.wikipedia.org/wiki/Allen's_interval_algebra https://en.wikipedia.org/wiki/Allen's_interval_algebra It's possible to build a graph where the relations are nodes, and the edges are possible smooth operations on the intervals (e.g. translation). Then you have a state machine for smooth system evolution.

PaulDavisThe1st 2y ago
Right, I should have linked to that (or something like it) rather than trying to write out my own list.