| Name | box-intersect-lib-py JSON |
| Version |
0.8.3
JSON |
| download |
| home_page | None |
| Summary | Box intersection/overlap/density algorithms in Rust with python bindings. |
| upload_time | 2024-11-17 18:25:22 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | >=3.7 |
| license | None |
| keywords |
box
algorithm
rust
python
pyo3
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# Fast box intersection algorithm
Computes box intersection/overlap/density algorithms using efficient algorithms and data structures. Aspires offer a easy-to-use interface that "just works" on both smaller and larger datasets. Written in Rust with Python bindings.
* [Algorithm list](#Algorithms)
* [Python wrapper examples](#python-wrapper-examples)
* [Benchmark results](#benchmark-results)
* [Algorithmic ideas](#algorithmic-ideas)
## Algorithms
The primary data structure is for rectangle set intersection: a class which structures a static list of rectangles efficiently so that overlapping rectangles can be identified quickly. The interface is:
* `BoxIntersector`
* `new(box_list)`: Creates the immutable box intersector with the following list of boxes.
* `find_intersections(x1, y1, width, height) -> List[int]`: Finds all intersections with rectangle defined by `(x1, y1, width, height)`. Returned list are the indexes in the input box list
The following algorithms are also avaliable:
* `find_intersecting_boxes(box_list)->list[list[int]]`: Returns all-to-all adjacency list of intersecting boxes.
* `find_intersecting_boxes_asym(source_boxes, dest_boxes)->list[list[int]]`: Returns source-to-dest adjacency list of intersecting boxes.
* `find_best_matches(box_list_1, box_list_2, iou_threshold: float)->tuple[list[tuple[int,int]],list[int],list[int]]`: Returns best unique matches between two given lists of boxes. Matches are only returned if they intersect and meet the Intersection over Union threshold (`iou_threshold`) and no other match with any unmatched box in the oposing list is better. A tuple of matches, remaining_list_1, remaining_list_2 is returned.
* `efficient_coverage(box_list, cover_rect_width, cover_rect_height)->list[tuple[tuple[int, int],list[int]]]`: A heuristic algorithm to try to quickly generate a small number of fixed-sized tiles to cover all the boxes in the box list. If any of the boxes are too large to fit in the tile, an error is raised.
* `find_non_max_suppressed(box_list, box_scores:list[float], iou_threshold:float,overlap_threshold:float)->list[bool]`: Identifies similar boxes in set with more overlap than the two thresholds specify, and suppresses the lower confidence one. Standard algorithm to deduplicate boxes in object detection frameworks.
## Python wrapper
Install with `pip install box-intersect-lib-py`
### Build instructions
If pip install fails, due to prebuilt binary wheels not being avaliable on your platform, try:
1. If you don't have rust installed, install with `curl https://sh.rustup.rs -sSf | sh
` [official installation docs](https://doc.rust-lang.org/cargo/getting-started/installation.html)
2. Install python dependencies: `pip install maturin numpy`
3. Build wheel with `(cd box-intersect-lib-py && maturin build --release --strip)`
4. Previous step will put wheel in a local directory. IT should be install able with `pip install box-intersect-lib-py/target/wheels/*`
A dockerfile with all of this set containerized is provided in `Dockerfile.text`
### Usage:
```python
import box_intersect_lib_py
import numpy as np
# input is numpy array of boxes.
# boxes are left-anchored (x,y,width,height)
boxes = np.array([
[1,1,1,2],
[0,0,5,5],
[2,3,2,6],
],dtype="int32")
results = box_intersect_lib_py.find_intersecting_boxes(boxes)
# 2nd box intersects with other 2
assert (results[0] == np.array([1])).all()
assert (results[1] == np.array([0,2])).all()
assert (results[2] == np.array([1])).all()
print(results) # [array([1], dtype=uint32), array([0, 2], dtype=uint32), array([1], dtype=uint32)]
# get area of the relevant intersections
intersection_areas = [box_intersect_lib_py.intersect_area(boxes[i], boxes[results[i]]) for i in range(len(boxes))]
print(intersection_areas) # [array([2], dtype=uint64), array([2, 4], dtype=uint64), array([4], dtype=uint64)]
# we can also build a data structure of boxes for efficient querying with arbirary other boxes
detector = box_intersect_lib_py.BoxIntersector(boxes)
query_box = (0,0,2,2)
intersecting_idxs = detector.find_intersections(*query_box)
print(intersecting_idxs) # [0, 1]
```
## Benchmark results
Running the following commands on my laptop (subject to signifiant noise):
```
python benchmark/run_benchmark.py --num-boxes 10000000 --region-size 100000 --max-box-size 100 --test-iterations 2
python benchmark/run_benchmark.py --num-boxes 1000000 --region-size 40000 --max-box-size 100 --test-iterations 5
python benchmark/run_benchmark.py --num-boxes 5000000 --region-size 40000 --max-box-size 100 --test-iterations 1
python benchmark/run_benchmark.py --num-boxes 10000 --region-size 4000 --max-box-size 100 --test-iterations 200
python benchmark/run_benchmark.py --num-boxes 50000 --region-size 4000 --max-box-size 100 --test-iterations 200
python benchmark/run_benchmark.py --num-boxes 100 --region-size 400 --max-box-size 100 --test-iterations 5000
python benchmark/run_benchmark.py --num-boxes 500 --region-size 400 --max-box-size 100 --test-iterations 5000
```
num boxes|num intersections| find_intersecting_boxes_t|find_non_max_suppressed_t|find_intersecting_boxes_linesearch_t|find_intersecting_boxes_asym_t|find_best_matches_t|find_rect_cover_t|BoxIntersector build|BoxIntersector query sequentially
---|---|---|---|---|---|---|---|---|---
10000000|98078592|12.169555259500157|7.491135403000044|136.2819793919998|16.957570917499652|18.989964099499957|2.2033966144999795|2.07134081949971|78.30415772001288
1000000|6141632|0.9191611845999432|0.6003980014000263|3.5016677132000043|1.086823502000334|1.1519274157999462|0.14588280299976758|0.1738209677998384|3.4725145600168617
5000000|153686102|7.358366684999055|2.962747178000427|87.27572011099983|11.088836232000176|16.82190396599981|0.6261364540005161|0.9347212379998382|23.502293479996297
10000|64484|0.006635849274998691|0.0034072973049933354|0.007089999469999384|0.00699314222000794|0.007134397955005625|0.0005728775550051068|0.001043458304993692|0.024413333800112014
50000|1588676|0.06341231076999974|0.017638188490000175|0.11677449097000135|0.06591738333499961|0.10906894315499813|0.0029347618249994413|0.006063540664999891|0.16421707900008187
100|732|3.0048768800043034e-05|6.568112400054815e-06|2.921996660006698e-05|2.89388543998939e-05|1.8404549999831942e-05|2.4175683996872975e-06|2.605749600115814e-06|0.00013785439200000838
500|20710|0.0005309709685996495|8.529535939997003e-05|0.0004740007478001644|0.0005328194969999459|0.0008529525551999541|9.667402999912156e-06|2.0378057800189707e-05|0.001288445912010502
## Algorithmic ideas
### Recursive Tile Sort (RTS) RTree
The idea is to build an RTree, essentailly a recursive interval tree where the sort axis swaps with each recursion down. Each node in the tree is a bounding box around a set of subnodes. The subnodes may overlap with each-other, so you have to check each child when doing recursive searches, similar to a B-Tree. This implementation uses an interval tree to store the sub-nodes, allowing for large sets of children, allowing for much flatter trees.
Building an efficient R-tree requires the use of recursive tile sort, hard to describe, but easier to visualize. Note that any method to build a valid R-tree will result in correct output, this method is only used to build an efficiently spatially partitioned R-tree.
### Reduction to a single dimension
This library used to do a simple reduction of 2d box overlap problems to a 1d interval overlap problem across the *x* axis, followed by brute force search across the *y* axis.
While asymtotically suboptimal, the resulting methods result in highly parallizable, cache-local, and predictable code flows, resulting in excelent performance on most datasets, and nearly optimal performance on small and sparse datasets.
Since only the *x* dimension is optimized, the time efficiency of this library does depend on the boxes being spread broadly across the *x* axis. However, rest assured that the accuracy and memory efficiency of this library remains regardless of the size and positions of the boxes.
The following details the main interval algorithms used in this library:
### Left-Right line search (for 1-dimensional reduction)
To do full, dense pairwise interval overlap comparisons, this simple left-to-right search is used.
Consider the following intervals, sorted by their left coordinate (we can keep track of where the interval originally was):
```
1. |--------|
2. |------------------------|
3. |--------|
4. |----|
5. |--------|
6. |--------|
```
Each interval has index *i* in the sorted list.
Note that all the intervals to the right of interval *i* are placed immidiately after *i* in the sorted list----once you find one interval to the right of *i* that does not intersect with it, there will never be another one anywhere else in the sorted list that is to the right.
So you can use this fact to easily build a directed graph of intervals pointing to all intervals to the right of them (psedocode)
```
sorted_intervals # list of (left, right) tuples
intervals_to_the_right(i) = [j for j in range(i+1,len(sorted_intervals)) while sorted_intervals[i].right > sorted_intervals[j].left]
```
Note that this step is linear in the number of interval overlaps *m* plus the number of nodes *n*---every overlap is counted once, no work is done for any intervals which are not there. So it is essentially optimal
Once you have that directed graph of left-to-right in an adjacency list, you can simply invert all the edges to get the right-to-left graph, and combine them to get the undirected overlap graph. This also takes linear time.
As for theoretical performance, the complete run-time of this algorithm is dominated by the original sort plus the number of actual interval intersections: *n \* log(n) + m*.
One noteable implementation detail is that since we are actually concerend with boxes, not intervals, the *y* dimension check is within the `intervals_to_the_right` proceedure, so that the adjacency graph does not need to actually be built in memory for boxes that do not overlap. This means that on realistic workflows, this proceedure is actually the vast majority of the computational work, as it is scanning and filtering many possible boxes which do overlap in the *x* dimension, but not overlap in the *y* dimension.
Below is a visualization of this proceedure. The bolded box is the box currently searched. The yellow region is the brute force search space. The blue boxes are the boxes to the right that the search finds, the green boxes are the boxes found by inverting the graph (no search needed, it has already completed).
For more details, see the implementation in [code](box-intersect-lib/src/find_intersecting.rs).
### Interval tree (for 1-dimensional reduction)
An interval tree is a well known algorithm for online comparison of one interval against a static set of intervals. Since this algorithm is well known (its in the famous "Introduction to Algorithms" CLRS textbook), there is no need to rehash the basic ideas of how it works here, but I will note that the worst case efficiency for the search is *k \* log(n)* where *k* is the number of resulting intervals from the query and *n* is the number of intervals in the tree.
Specific implementation details:
1. Since the tree is not added to, then unlike the implementation in CLRS, a ballanced interval tree can be built in *n* time via a simple bottom-up construction.
2. The base of the tree is sorted by left cooridnate before the tree is constructed. This means that nearby intervals are placed close together, reducing search cost from *k\* log(n)* to *k + log(n)* assuming uniform interval length. However, the sorting step does increase one-time cost of building the tree from *n* to *n\*log(n)*.
3. Instead of a binary tree, a b-tree of size 8 is constructed.
Note that the implementation is no longer part of the master branch, as it was superceeded by the recursive tile sort implementation. See the [single_thread](https://github.com/benblack769/box-intersect-lib/blob/single_thread/box-intersect-lib/src/interval_tree.rs) branch for the implementation.
### Efficient coverage heuristic
The efficient coverage heuristic algorithm is similar in concept to the left-to-right search algorithm idea.
The constraint to the solution set is that all boxes must be covered with a tile. This implies that the left-most box also must be covered with a tile. And this tile can be placed at the left-most edge of the box.
If all possible tiles with this constraint are enumerated, we construct a vertically oriented window of possible tiles. Any individual box fully contained within this window can be added, but if so, the constraints on the tile set will increase, and so the window may shrink as it is contrained to include both boxes.
Computing the optimal box to add requires global analysis and is potentially extremely expensive. So we can utilize a simple but suprisingly effective heuristic: find the next left-most box fully contained in the window, and just add it, and shrink the window. A visualization of this heuristic is shown below:
This approximate algorithm has an informal beginnings of a worst case analysis that suggests it is a 2-approximation of the optimal solution:
1. Consider all the locally left-most boxes. That is, every box that cannot be included in the left-inspection region of some other box.
2. Now, consider that the optimal solution has at least one rectangle for each of these locally left-most boxes. Consider each of these boxes.
3. Now, consider the left-preferring greedy solution applied to all these left-most boxes. After all the boxes in all those greedy tiles are removed, there will be a new set of left-most boxes that appeared from within the left-intersection region of the original set. Now apply the greedy solution to that 2nd set.
4. I claim that step 3 has removed all of the boxes that the optimal set in step 2 removed. (Unfortunately, I don't have a great argument here, so you are free to try to come up with counter-examples)
5. The resulting set of boxes from step 3 is strictly a subset of step 2. Since the optimal solution cannot increase by removing boxes, you can apply this analysis recursively on the remaining set of boxes.
6. Since step 3 only required at worst twice as many tiles as step 2, this algorithm is a 2-approximation.
Not a super formal argument. But I can't come up with any worst case solution worst than a 2-approximation, let us know if you find a counter-example. And a synthetic benchmark labeled it as the best solution yet.
The worst case I could construct is this:
This particular case produces 6 tiles, where the optimal solution produces 4. However, in the infinite limit, extended downwards, this produces twice as many tiles as the best case. Suggesting that the 2-approximation is tight.
The implementation of this algorithm is one of the fastest of all the algorithms in the repo, due to it not using the R-Tree structure at all. Since both phases of the algorithm are left-to-right sweeps, the implementation instead does a single left-to-right sweep over boxes, and builds up multiple tiles at once. As the global sweep encounters a new left-most box, it either adds a box to an existing tile window, or if that is not possible, creates a new tile window. These windows are added from left-to-right by construction, and so only the first windows need to be checked if they need to be popped off the stack or not when the global sweep passes their left-most edge. All in-progress windows are checked by brute force when a new box is encountered. This yields a `O(num_boxes * num_windows)` algorithm in the worst case where all boxes are vertically stacked on top of each other with lots of spacing in between them in the Y axis, but if boxes spacings are equally distributed between X and Y fields (no matter their density), then it goes to `O(num_boxes * sqrt(num_boxes))` max runtime, as there will only be `sqrt(num_boxes)` number of windows open at any given point in time that need to be checked. This means that a simple optimization to reduce worst-case analysis could be swapping the X and Y if there is a lot of vertical stacking, which should reduce the worst case analysis to the square case of `O(num_boxes * sqrt(num_boxes))`.
[More writeup on the intuition behind this algorithm here](https://benblack769.github.io/posts/blog/rect_cover/)
Raw data
{
"_id": null,
"home_page": null,
"name": "box-intersect-lib-py",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": null,
"keywords": "box, algorithm, rust, python, pyo3",
"author": null,
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/63/a3/9ae64ecf381ee5ea975394729ebff0dd17352bc10ed7e4551ba0056ff7ad/box_intersect_lib_py-0.8.3.tar.gz",
"platform": null,
"description": "# Fast box intersection algorithm\n\nComputes box intersection/overlap/density algorithms using efficient algorithms and data structures. Aspires offer a easy-to-use interface that \"just works\" on both smaller and larger datasets. Written in Rust with Python bindings.\n\n* [Algorithm list](#Algorithms)\n* [Python wrapper examples](#python-wrapper-examples)\n* [Benchmark results](#benchmark-results)\n* [Algorithmic ideas](#algorithmic-ideas)\n\n## Algorithms\n\nThe primary data structure is for rectangle set intersection: a class which structures a static list of rectangles efficiently so that overlapping rectangles can be identified quickly. The interface is:\n\n* `BoxIntersector`\n * `new(box_list)`: Creates the immutable box intersector with the following list of boxes.\n * `find_intersections(x1, y1, width, height) -> List[int]`: Finds all intersections with rectangle defined by `(x1, y1, width, height)`. Returned list are the indexes in the input box list\n\nThe following algorithms are also avaliable:\n\n* `find_intersecting_boxes(box_list)->list[list[int]]`: Returns all-to-all adjacency list of intersecting boxes.\n* `find_intersecting_boxes_asym(source_boxes, dest_boxes)->list[list[int]]`: Returns source-to-dest adjacency list of intersecting boxes.\n* `find_best_matches(box_list_1, box_list_2, iou_threshold: float)->tuple[list[tuple[int,int]],list[int],list[int]]`: Returns best unique matches between two given lists of boxes. Matches are only returned if they intersect and meet the Intersection over Union threshold (`iou_threshold`) and no other match with any unmatched box in the oposing list is better. A tuple of matches, remaining_list_1, remaining_list_2 is returned.\n* `efficient_coverage(box_list, cover_rect_width, cover_rect_height)->list[tuple[tuple[int, int],list[int]]]`: A heuristic algorithm to try to quickly generate a small number of fixed-sized tiles to cover all the boxes in the box list. If any of the boxes are too large to fit in the tile, an error is raised.\n* `find_non_max_suppressed(box_list, box_scores:list[float], iou_threshold:float,overlap_threshold:float)->list[bool]`: Identifies similar boxes in set with more overlap than the two thresholds specify, and suppresses the lower confidence one. Standard algorithm to deduplicate boxes in object detection frameworks.\n\n## Python wrapper\n\nInstall with `pip install box-intersect-lib-py`\n\n### Build instructions\n\nIf pip install fails, due to prebuilt binary wheels not being avaliable on your platform, try:\n\n1. If you don't have rust installed, install with `curl https://sh.rustup.rs -sSf | sh\n` [official installation docs](https://doc.rust-lang.org/cargo/getting-started/installation.html)\n2. Install python dependencies: `pip install maturin numpy`\n3. Build wheel with `(cd box-intersect-lib-py && maturin build --release --strip)`\n4. Previous step will put wheel in a local directory. IT should be install able with `pip install box-intersect-lib-py/target/wheels/*`\n\nA dockerfile with all of this set containerized is provided in `Dockerfile.text`\n\n### Usage:\n\n```python\nimport box_intersect_lib_py\nimport numpy as np\n\n# input is numpy array of boxes.\n# boxes are left-anchored (x,y,width,height)\nboxes = np.array([\n [1,1,1,2],\n [0,0,5,5],\n [2,3,2,6],\n],dtype=\"int32\")\n\nresults = box_intersect_lib_py.find_intersecting_boxes(boxes)\n\n# 2nd box intersects with other 2\nassert (results[0] == np.array([1])).all()\nassert (results[1] == np.array([0,2])).all()\nassert (results[2] == np.array([1])).all()\n\nprint(results) # [array([1], dtype=uint32), array([0, 2], dtype=uint32), array([1], dtype=uint32)]\n\n# get area of the relevant intersections\nintersection_areas = [box_intersect_lib_py.intersect_area(boxes[i], boxes[results[i]]) for i in range(len(boxes))]\nprint(intersection_areas) # [array([2], dtype=uint64), array([2, 4], dtype=uint64), array([4], dtype=uint64)]\n\n\n# we can also build a data structure of boxes for efficient querying with arbirary other boxes\ndetector = box_intersect_lib_py.BoxIntersector(boxes)\nquery_box = (0,0,2,2)\nintersecting_idxs = detector.find_intersections(*query_box)\nprint(intersecting_idxs) # [0, 1]\n```\n\n## Benchmark results\n\nRunning the following commands on my laptop (subject to signifiant noise):\n\n```\npython benchmark/run_benchmark.py --num-boxes 10000000 --region-size 100000 --max-box-size 100 --test-iterations 2\npython benchmark/run_benchmark.py --num-boxes 1000000 --region-size 40000 --max-box-size 100 --test-iterations 5\npython benchmark/run_benchmark.py --num-boxes 5000000 --region-size 40000 --max-box-size 100 --test-iterations 1\npython benchmark/run_benchmark.py --num-boxes 10000 --region-size 4000 --max-box-size 100 --test-iterations 200\npython benchmark/run_benchmark.py --num-boxes 50000 --region-size 4000 --max-box-size 100 --test-iterations 200\npython benchmark/run_benchmark.py --num-boxes 100 --region-size 400 --max-box-size 100 --test-iterations 5000\npython benchmark/run_benchmark.py --num-boxes 500 --region-size 400 --max-box-size 100 --test-iterations 5000\n```\n\nnum boxes|num intersections| find_intersecting_boxes_t|find_non_max_suppressed_t|find_intersecting_boxes_linesearch_t|find_intersecting_boxes_asym_t|find_best_matches_t|find_rect_cover_t|BoxIntersector build|BoxIntersector query sequentially\n---|---|---|---|---|---|---|---|---|---\n10000000|98078592|12.169555259500157|7.491135403000044|136.2819793919998|16.957570917499652|18.989964099499957|2.2033966144999795|2.07134081949971|78.30415772001288\n1000000|6141632|0.9191611845999432|0.6003980014000263|3.5016677132000043|1.086823502000334|1.1519274157999462|0.14588280299976758|0.1738209677998384|3.4725145600168617\n5000000|153686102|7.358366684999055|2.962747178000427|87.27572011099983|11.088836232000176|16.82190396599981|0.6261364540005161|0.9347212379998382|23.502293479996297\n10000|64484|0.006635849274998691|0.0034072973049933354|0.007089999469999384|0.00699314222000794|0.007134397955005625|0.0005728775550051068|0.001043458304993692|0.024413333800112014\n50000|1588676|0.06341231076999974|0.017638188490000175|0.11677449097000135|0.06591738333499961|0.10906894315499813|0.0029347618249994413|0.006063540664999891|0.16421707900008187\n100|732|3.0048768800043034e-05|6.568112400054815e-06|2.921996660006698e-05|2.89388543998939e-05|1.8404549999831942e-05|2.4175683996872975e-06|2.605749600115814e-06|0.00013785439200000838\n500|20710|0.0005309709685996495|8.529535939997003e-05|0.0004740007478001644|0.0005328194969999459|0.0008529525551999541|9.667402999912156e-06|2.0378057800189707e-05|0.001288445912010502\n\n\n## Algorithmic ideas\n\n### Recursive Tile Sort (RTS) RTree\n\nThe idea is to build an RTree, essentailly a recursive interval tree where the sort axis swaps with each recursion down. Each node in the tree is a bounding box around a set of subnodes. The subnodes may overlap with each-other, so you have to check each child when doing recursive searches, similar to a B-Tree. This implementation uses an interval tree to store the sub-nodes, allowing for large sets of children, allowing for much flatter trees.\n\nBuilding an efficient R-tree requires the use of recursive tile sort, hard to describe, but easier to visualize. Note that any method to build a valid R-tree will result in correct output, this method is only used to build an efficiently spatially partitioned R-tree.\n\n\n\n\n### Reduction to a single dimension\n\nThis library used to do a simple reduction of 2d box overlap problems to a 1d interval overlap problem across the *x* axis, followed by brute force search across the *y* axis.\n\nWhile asymtotically suboptimal, the resulting methods result in highly parallizable, cache-local, and predictable code flows, resulting in excelent performance on most datasets, and nearly optimal performance on small and sparse datasets.\n\nSince only the *x* dimension is optimized, the time efficiency of this library does depend on the boxes being spread broadly across the *x* axis. However, rest assured that the accuracy and memory efficiency of this library remains regardless of the size and positions of the boxes.\n\nThe following details the main interval algorithms used in this library:\n\n### Left-Right line search (for 1-dimensional reduction)\n\nTo do full, dense pairwise interval overlap comparisons, this simple left-to-right search is used.\n\nConsider the following intervals, sorted by their left coordinate (we can keep track of where the interval originally was):\n\n```\n1. |--------|\n2. |------------------------|\n3. |--------|\n4. |----|\n5. |--------|\n6. |--------|\n```\n\nEach interval has index *i* in the sorted list.\n\nNote that all the intervals to the right of interval *i* are placed immidiately after *i* in the sorted list----once you find one interval to the right of *i* that does not intersect with it, there will never be another one anywhere else in the sorted list that is to the right.\n\nSo you can use this fact to easily build a directed graph of intervals pointing to all intervals to the right of them (psedocode)\n\n```\nsorted_intervals # list of (left, right) tuples\nintervals_to_the_right(i) = [j for j in range(i+1,len(sorted_intervals)) while sorted_intervals[i].right > sorted_intervals[j].left]\n```\n\nNote that this step is linear in the number of interval overlaps *m* plus the number of nodes *n*---every overlap is counted once, no work is done for any intervals which are not there. So it is essentially optimal\n\nOnce you have that directed graph of left-to-right in an adjacency list, you can simply invert all the edges to get the right-to-left graph, and combine them to get the undirected overlap graph. This also takes linear time.\n\nAs for theoretical performance, the complete run-time of this algorithm is dominated by the original sort plus the number of actual interval intersections: *n \\* log(n) + m*.\n\nOne noteable implementation detail is that since we are actually concerend with boxes, not intervals, the *y* dimension check is within the `intervals_to_the_right` proceedure, so that the adjacency graph does not need to actually be built in memory for boxes that do not overlap. This means that on realistic workflows, this proceedure is actually the vast majority of the computational work, as it is scanning and filtering many possible boxes which do overlap in the *x* dimension, but not overlap in the *y* dimension.\n\nBelow is a visualization of this proceedure. The bolded box is the box currently searched. The yellow region is the brute force search space. The blue boxes are the boxes to the right that the search finds, the green boxes are the boxes found by inverting the graph (no search needed, it has already completed).\n\n\n\n\n\nFor more details, see the implementation in [code](box-intersect-lib/src/find_intersecting.rs).\n\n### Interval tree (for 1-dimensional reduction)\n\nAn interval tree is a well known algorithm for online comparison of one interval against a static set of intervals. Since this algorithm is well known (its in the famous \"Introduction to Algorithms\" CLRS textbook), there is no need to rehash the basic ideas of how it works here, but I will note that the worst case efficiency for the search is *k \\* log(n)* where *k* is the number of resulting intervals from the query and *n* is the number of intervals in the tree.\n\nSpecific implementation details:\n\n1. Since the tree is not added to, then unlike the implementation in CLRS, a ballanced interval tree can be built in *n* time via a simple bottom-up construction.\n2. The base of the tree is sorted by left cooridnate before the tree is constructed. This means that nearby intervals are placed close together, reducing search cost from *k\\* log(n)* to *k + log(n)* assuming uniform interval length. However, the sorting step does increase one-time cost of building the tree from *n* to *n\\*log(n)*.\n3. Instead of a binary tree, a b-tree of size 8 is constructed.\n\nNote that the implementation is no longer part of the master branch, as it was superceeded by the recursive tile sort implementation. See the [single_thread](https://github.com/benblack769/box-intersect-lib/blob/single_thread/box-intersect-lib/src/interval_tree.rs) branch for the implementation.\n\n### Efficient coverage heuristic\n\nThe efficient coverage heuristic algorithm is similar in concept to the left-to-right search algorithm idea.\n\nThe constraint to the solution set is that all boxes must be covered with a tile. This implies that the left-most box also must be covered with a tile. And this tile can be placed at the left-most edge of the box.\n\n\nIf all possible tiles with this constraint are enumerated, we construct a vertically oriented window of possible tiles. Any individual box fully contained within this window can be added, but if so, the constraints on the tile set will increase, and so the window may shrink as it is contrained to include both boxes.\n\nComputing the optimal box to add requires global analysis and is potentially extremely expensive. So we can utilize a simple but suprisingly effective heuristic: find the next left-most box fully contained in the window, and just add it, and shrink the window. A visualization of this heuristic is shown below:\n\n\n\n\n\nThis approximate algorithm has an informal beginnings of a worst case analysis that suggests it is a 2-approximation of the optimal solution:\n\n1. Consider all the locally left-most boxes. That is, every box that cannot be included in the left-inspection region of some other box.\n2. Now, consider that the optimal solution has at least one rectangle for each of these locally left-most boxes. Consider each of these boxes.\n3. Now, consider the left-preferring greedy solution applied to all these left-most boxes. After all the boxes in all those greedy tiles are removed, there will be a new set of left-most boxes that appeared from within the left-intersection region of the original set. Now apply the greedy solution to that 2nd set.\n4. I claim that step 3 has removed all of the boxes that the optimal set in step 2 removed. (Unfortunately, I don't have a great argument here, so you are free to try to come up with counter-examples)\n5. The resulting set of boxes from step 3 is strictly a subset of step 2. Since the optimal solution cannot increase by removing boxes, you can apply this analysis recursively on the remaining set of boxes.\n6. Since step 3 only required at worst twice as many tiles as step 2, this algorithm is a 2-approximation.\n\nNot a super formal argument. But I can't come up with any worst case solution worst than a 2-approximation, let us know if you find a counter-example. And a synthetic benchmark labeled it as the best solution yet.\n\nThe worst case I could construct is this:\n\n\n\nThis particular case produces 6 tiles, where the optimal solution produces 4. However, in the infinite limit, extended downwards, this produces twice as many tiles as the best case. Suggesting that the 2-approximation is tight.\n\nThe implementation of this algorithm is one of the fastest of all the algorithms in the repo, due to it not using the R-Tree structure at all. Since both phases of the algorithm are left-to-right sweeps, the implementation instead does a single left-to-right sweep over boxes, and builds up multiple tiles at once. As the global sweep encounters a new left-most box, it either adds a box to an existing tile window, or if that is not possible, creates a new tile window. These windows are added from left-to-right by construction, and so only the first windows need to be checked if they need to be popped off the stack or not when the global sweep passes their left-most edge. All in-progress windows are checked by brute force when a new box is encountered. This yields a `O(num_boxes * num_windows)` algorithm in the worst case where all boxes are vertically stacked on top of each other with lots of spacing in between them in the Y axis, but if boxes spacings are equally distributed between X and Y fields (no matter their density), then it goes to `O(num_boxes * sqrt(num_boxes))` max runtime, as there will only be `sqrt(num_boxes)` number of windows open at any given point in time that need to be checked. This means that a simple optimization to reduce worst-case analysis could be swapping the X and Y if there is a lot of vertical stacking, which should reduce the worst case analysis to the square case of `O(num_boxes * sqrt(num_boxes))`.\n\n[More writeup on the intuition behind this algorithm here](https://benblack769.github.io/posts/blog/rect_cover/)\n\n",
"bugtrack_url": null,
"license": null,
"summary": "Box intersection/overlap/density algorithms in Rust with python bindings.",
"version": "0.8.3",
"project_urls": {
"Homepage": "https://github.com/Techcyte/box-intersect-lib",
"Repository": "https://github.com/Techcyte/box-intersect-lib.git"
},
"split_keywords": [
"box",
" algorithm",
" rust",
" python",
" pyo3"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "8c48d4139094897650cdb636c0711cd9398352bccd66c93237673b6072ae704f",
"md5": "751e8c6f30494391bb37e8a5d6775da0",
"sha256": "495f51341965525f60aba8b17f96f4573b271e4fb38951e6052433601400815d"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp310-cp310-macosx_10_12_x86_64.whl",
"has_sig": false,
"md5_digest": "751e8c6f30494391bb37e8a5d6775da0",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.7",
"size": 295847,
"upload_time": "2024-11-17T19:15:08",
"upload_time_iso_8601": "2024-11-17T19:15:08.343746Z",
"url": "https://files.pythonhosted.org/packages/8c/48/d4139094897650cdb636c0711cd9398352bccd66c93237673b6072ae704f/box_intersect_lib_py-0.8.3-cp310-cp310-macosx_10_12_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "0171bf2a61a40b64c1a19b03685163efb3dec9d994f4c73ecceea49ccf450560",
"md5": "1b56ba17214efa515a5ec63e10cc9746",
"sha256": "ade2f162c4bb114a9515919b32a2d347b7c3bb4a812afcb1da6f7eba18f70c3d"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp310-cp310-macosx_11_0_arm64.whl",
"has_sig": false,
"md5_digest": "1b56ba17214efa515a5ec63e10cc9746",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.7",
"size": 286360,
"upload_time": "2024-11-17T18:46:42",
"upload_time_iso_8601": "2024-11-17T18:46:42.686274Z",
"url": "https://files.pythonhosted.org/packages/01/71/bf2a61a40b64c1a19b03685163efb3dec9d994f4c73ecceea49ccf450560/box_intersect_lib_py-0.8.3-cp310-cp310-macosx_11_0_arm64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "69469f78f9d9a669fae2e60d43a48bccfde5fb9e67033c53ec64138033263ca1",
"md5": "eb6b0651e368db77607c8bd3f8a9b083",
"sha256": "030a5d48dfd9b865900df21bb0f4bfe89bc359a2128f616df4d845f3f886b489"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "eb6b0651e368db77607c8bd3f8a9b083",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.7",
"size": 327660,
"upload_time": "2024-11-17T18:25:11",
"upload_time_iso_8601": "2024-11-17T18:25:11.159077Z",
"url": "https://files.pythonhosted.org/packages/69/46/9f78f9d9a669fae2e60d43a48bccfde5fb9e67033c53ec64138033263ca1/box_intersect_lib_py-0.8.3-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "b18c6c77856de746190304f88a2955f0841b9873afbe9d5946ca9ae1fe64be9d",
"md5": "105b96998a229788be250ee84363833a",
"sha256": "60e8277b127faf80722d9c9541454a8842e4ca821f70a454fb97e79765241c44"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp310-none-win_amd64.whl",
"has_sig": false,
"md5_digest": "105b96998a229788be250ee84363833a",
"packagetype": "bdist_wheel",
"python_version": "cp310",
"requires_python": ">=3.7",
"size": 189632,
"upload_time": "2024-11-17T19:09:25",
"upload_time_iso_8601": "2024-11-17T19:09:25.012256Z",
"url": "https://files.pythonhosted.org/packages/b1/8c/6c77856de746190304f88a2955f0841b9873afbe9d5946ca9ae1fe64be9d/box_intersect_lib_py-0.8.3-cp310-none-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "75d78668aa1b091de3a9e4a7b6288b01dcfb710dc8e4d247d4b541d76791005b",
"md5": "815d7a9fa9fe3bd8ac390a6ca6cf0216",
"sha256": "54cb07746d486d81c371e02335e36a3dc6a0859acaf320aab7125e0238144347"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp311-cp311-macosx_10_12_x86_64.whl",
"has_sig": false,
"md5_digest": "815d7a9fa9fe3bd8ac390a6ca6cf0216",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.7",
"size": 295788,
"upload_time": "2024-11-17T19:15:11",
"upload_time_iso_8601": "2024-11-17T19:15:11.550611Z",
"url": "https://files.pythonhosted.org/packages/75/d7/8668aa1b091de3a9e4a7b6288b01dcfb710dc8e4d247d4b541d76791005b/box_intersect_lib_py-0.8.3-cp311-cp311-macosx_10_12_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "6008158445289fc8382437256c0633e6d6af80d9206117475a4334b36ddda7f8",
"md5": "2e7216b20e751bd70afc2d3b2eb79eb3",
"sha256": "38fe3e933128181bbfd4c1c60eb0732144486ce71c366609f4145b0abdc1c9d1"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp311-cp311-macosx_11_0_arm64.whl",
"has_sig": false,
"md5_digest": "2e7216b20e751bd70afc2d3b2eb79eb3",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.7",
"size": 286210,
"upload_time": "2024-11-17T19:15:13",
"upload_time_iso_8601": "2024-11-17T19:15:13.742485Z",
"url": "https://files.pythonhosted.org/packages/60/08/158445289fc8382437256c0633e6d6af80d9206117475a4334b36ddda7f8/box_intersect_lib_py-0.8.3-cp311-cp311-macosx_11_0_arm64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "e59a632bdd2f162de43678b0638eeb29767406489f9b66624502c9cf1b1412b5",
"md5": "27821b935f4341d17a09816f6be9f12d",
"sha256": "3e053c295224c77f031486b7e064046f09936fe87500c1a8058c43cad9275561"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "27821b935f4341d17a09816f6be9f12d",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.7",
"size": 327459,
"upload_time": "2024-11-17T18:25:13",
"upload_time_iso_8601": "2024-11-17T18:25:13.467193Z",
"url": "https://files.pythonhosted.org/packages/e5/9a/632bdd2f162de43678b0638eeb29767406489f9b66624502c9cf1b1412b5/box_intersect_lib_py-0.8.3-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4ff0e4f049861f525f32b9602ef3049defe0e651d0b2a47dadcee5927f49c693",
"md5": "a9c56e1bf5c235b945d37550e1bd0d33",
"sha256": "cf0686fd4633ac469be74b5def9ebf4d1567d74301218554f4aec7838ff528fc"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp311-none-win_amd64.whl",
"has_sig": false,
"md5_digest": "a9c56e1bf5c235b945d37550e1bd0d33",
"packagetype": "bdist_wheel",
"python_version": "cp311",
"requires_python": ">=3.7",
"size": 189544,
"upload_time": "2024-11-17T19:09:26",
"upload_time_iso_8601": "2024-11-17T19:09:26.999659Z",
"url": "https://files.pythonhosted.org/packages/4f/f0/e4f049861f525f32b9602ef3049defe0e651d0b2a47dadcee5927f49c693/box_intersect_lib_py-0.8.3-cp311-none-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4814a2346f56f1e5cc0cb9deca31b15602a0319c36853c5473c260fac8a5f0e5",
"md5": "d8a727c61165d0de8b545b10e18b162e",
"sha256": "b44dfa5c2741557f8f5ce185817b0a45f42ea9dbf5fcdd29c6b1b2902f4bccb4"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp312-cp312-macosx_10_12_x86_64.whl",
"has_sig": false,
"md5_digest": "d8a727c61165d0de8b545b10e18b162e",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.7",
"size": 294772,
"upload_time": "2024-11-17T19:15:15",
"upload_time_iso_8601": "2024-11-17T19:15:15.947603Z",
"url": "https://files.pythonhosted.org/packages/48/14/a2346f56f1e5cc0cb9deca31b15602a0319c36853c5473c260fac8a5f0e5/box_intersect_lib_py-0.8.3-cp312-cp312-macosx_10_12_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4b3f7f63427938015c675c1333173aab2e8ab6642ae458a6f098d6c92e3457eb",
"md5": "50550a425615fc28dd8681d53545c15a",
"sha256": "5f0a3652fe5384ecd73c00b8874782742f5ed914257c8b53efe52f84a2ba60d5"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp312-cp312-macosx_11_0_arm64.whl",
"has_sig": false,
"md5_digest": "50550a425615fc28dd8681d53545c15a",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.7",
"size": 285673,
"upload_time": "2024-11-17T19:15:17",
"upload_time_iso_8601": "2024-11-17T19:15:17.818203Z",
"url": "https://files.pythonhosted.org/packages/4b/3f/7f63427938015c675c1333173aab2e8ab6642ae458a6f098d6c92e3457eb/box_intersect_lib_py-0.8.3-cp312-cp312-macosx_11_0_arm64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4905e9337933401f7fb35829b2bfd9aa23e37674ee7c668b8b39bfe2f1cf41ec",
"md5": "2bcff00c8cd15ba46f70a26dbad2b7f2",
"sha256": "7ead1217c2cead345ea3cd8a056f8c94af6f6f83e42fe215e6aed4575c6579c0"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "2bcff00c8cd15ba46f70a26dbad2b7f2",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.7",
"size": 326915,
"upload_time": "2024-11-17T18:25:14",
"upload_time_iso_8601": "2024-11-17T18:25:14.974806Z",
"url": "https://files.pythonhosted.org/packages/49/05/e9337933401f7fb35829b2bfd9aa23e37674ee7c668b8b39bfe2f1cf41ec/box_intersect_lib_py-0.8.3-cp312-cp312-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "de019af4402e65e7f34fe93b20804b5206a08ac676affbd6cf853bdc9af29b8d",
"md5": "e88dd103244bbd4d3301faadea8f2378",
"sha256": "3ec14c7683cbefb6033a502b09d27c5bea3f14c3d6ff1bd95651fc694082054a"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp312-none-win_amd64.whl",
"has_sig": false,
"md5_digest": "e88dd103244bbd4d3301faadea8f2378",
"packagetype": "bdist_wheel",
"python_version": "cp312",
"requires_python": ">=3.7",
"size": 189083,
"upload_time": "2024-11-17T19:15:19",
"upload_time_iso_8601": "2024-11-17T19:15:19.713916Z",
"url": "https://files.pythonhosted.org/packages/de/01/9af4402e65e7f34fe93b20804b5206a08ac676affbd6cf853bdc9af29b8d/box_intersect_lib_py-0.8.3-cp312-none-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "2b90ce76081317a41f89899181456028d3dca33eb076daea087ead89d451b71b",
"md5": "e7d1f0e68cf67e9fc1ec2bcff4757a70",
"sha256": "54e75df66082116961c792257eaaea7222db61fbcebf1e62bf9886b680c43db4"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "e7d1f0e68cf67e9fc1ec2bcff4757a70",
"packagetype": "bdist_wheel",
"python_version": "cp37",
"requires_python": ">=3.7",
"size": 328191,
"upload_time": "2024-11-17T18:25:17",
"upload_time_iso_8601": "2024-11-17T18:25:17.092334Z",
"url": "https://files.pythonhosted.org/packages/2b/90/ce76081317a41f89899181456028d3dca33eb076daea087ead89d451b71b/box_intersect_lib_py-0.8.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "4c528632ece4b6416cbd6bf7318b5801a15db01e191a6bd5bac60afc988c82ef",
"md5": "e53ac5add92e1f7a3a8e7352d9432c5e",
"sha256": "2d411a88159e0f501468a077541d33ca508da88684b72be9871b8f7159911155"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp38-cp38-macosx_10_12_x86_64.whl",
"has_sig": false,
"md5_digest": "e53ac5add92e1f7a3a8e7352d9432c5e",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.7",
"size": 296467,
"upload_time": "2024-11-17T19:15:21",
"upload_time_iso_8601": "2024-11-17T19:15:21.571696Z",
"url": "https://files.pythonhosted.org/packages/4c/52/8632ece4b6416cbd6bf7318b5801a15db01e191a6bd5bac60afc988c82ef/box_intersect_lib_py-0.8.3-cp38-cp38-macosx_10_12_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "63f521ca614aea90b1775a6a6283f8319f8cfdba5640a73bdb1f41ba708dda3a",
"md5": "f78e8b331778b2ad78caa8bacf1ab23c",
"sha256": "25b66783c9a6ba03fd8143d7f42268818f0e5fbe21235a1189728da5947ca5ed"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp38-cp38-macosx_11_0_arm64.whl",
"has_sig": false,
"md5_digest": "f78e8b331778b2ad78caa8bacf1ab23c",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.7",
"size": 287065,
"upload_time": "2024-11-17T19:15:23",
"upload_time_iso_8601": "2024-11-17T19:15:23.501871Z",
"url": "https://files.pythonhosted.org/packages/63/f5/21ca614aea90b1775a6a6283f8319f8cfdba5640a73bdb1f41ba708dda3a/box_intersect_lib_py-0.8.3-cp38-cp38-macosx_11_0_arm64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "719f086baba0cf2a5d26157e3358a47b3d935bf46c422948a9bb07edf0f0158b",
"md5": "8bd281959fdeddf99da8b560b244036f",
"sha256": "bc6efeca8fe384a4eec4ed212aa8a3c505f11d2135ddfeb5eb023cfa624d501b"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "8bd281959fdeddf99da8b560b244036f",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.7",
"size": 328072,
"upload_time": "2024-11-17T18:25:19",
"upload_time_iso_8601": "2024-11-17T18:25:19.183669Z",
"url": "https://files.pythonhosted.org/packages/71/9f/086baba0cf2a5d26157e3358a47b3d935bf46c422948a9bb07edf0f0158b/box_intersect_lib_py-0.8.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "2a3a43385ddd124576a3f9d891928e8092d8b7a33a0ba98c02a45a947e827cf7",
"md5": "70e8b161a6e7f8f095940f67439d08d9",
"sha256": "197e917893a176995cb0ba5e687595cdc3b93ce70feea3cb1ec9d15bf68d8f10"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp38-none-win_amd64.whl",
"has_sig": false,
"md5_digest": "70e8b161a6e7f8f095940f67439d08d9",
"packagetype": "bdist_wheel",
"python_version": "cp38",
"requires_python": ">=3.7",
"size": 189837,
"upload_time": "2024-11-17T19:15:24",
"upload_time_iso_8601": "2024-11-17T19:15:24.725852Z",
"url": "https://files.pythonhosted.org/packages/2a/3a/43385ddd124576a3f9d891928e8092d8b7a33a0ba98c02a45a947e827cf7/box_intersect_lib_py-0.8.3-cp38-none-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "77bdc26c54ffb7d616c677554789baafc994a021368a7de43d2eabe409090385",
"md5": "caf335c77c9c96a189efc52b490791ae",
"sha256": "4a42af1be46e4cd07796e22547175d216e12fa2632dca234ca7e329ba5793879"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp39-cp39-macosx_10_12_x86_64.whl",
"has_sig": false,
"md5_digest": "caf335c77c9c96a189efc52b490791ae",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.7",
"size": 297007,
"upload_time": "2024-11-17T19:15:25",
"upload_time_iso_8601": "2024-11-17T19:15:25.946817Z",
"url": "https://files.pythonhosted.org/packages/77/bd/c26c54ffb7d616c677554789baafc994a021368a7de43d2eabe409090385/box_intersect_lib_py-0.8.3-cp39-cp39-macosx_10_12_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "717968d5c86993d1b600f5928ce6e47ece9839e133147d86868dbe1f8ed2681e",
"md5": "344b83532a63e61109e9db691d479e3c",
"sha256": "8beabce0cd014b47c92e81814fcc241e08844705865784a8e9aa9e28469769b3"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp39-cp39-macosx_11_0_arm64.whl",
"has_sig": false,
"md5_digest": "344b83532a63e61109e9db691d479e3c",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.7",
"size": 287373,
"upload_time": "2024-11-17T19:15:27",
"upload_time_iso_8601": "2024-11-17T19:15:27.192706Z",
"url": "https://files.pythonhosted.org/packages/71/79/68d5c86993d1b600f5928ce6e47ece9839e133147d86868dbe1f8ed2681e/box_intersect_lib_py-0.8.3-cp39-cp39-macosx_11_0_arm64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "7664682c3f23d9859536e5f4b59e999be30a152cf1f70889c7fb34e2cbf0bb32",
"md5": "fb4bb051cec29c044095bef65c090f2f",
"sha256": "579a012cd95714d85cdc4e6e0135a14e9adbcf76dd3999fdaf6c9c865557f909"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"has_sig": false,
"md5_digest": "fb4bb051cec29c044095bef65c090f2f",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.7",
"size": 328651,
"upload_time": "2024-11-17T18:25:20",
"upload_time_iso_8601": "2024-11-17T18:25:20.685516Z",
"url": "https://files.pythonhosted.org/packages/76/64/682c3f23d9859536e5f4b59e999be30a152cf1f70889c7fb34e2cbf0bb32/box_intersect_lib_py-0.8.3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "b33262d3799917db1dadf9a75faa032e62c7d5c4480b867b7aabea94862135d0",
"md5": "7e534a8300e3590e08980f9d41180e21",
"sha256": "8857fe071bf82d2598da40a2e3249fdbb6c04323404e27edf943b0fa289d0dec"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3-cp39-none-win_amd64.whl",
"has_sig": false,
"md5_digest": "7e534a8300e3590e08980f9d41180e21",
"packagetype": "bdist_wheel",
"python_version": "cp39",
"requires_python": ">=3.7",
"size": 190240,
"upload_time": "2024-11-17T19:15:29",
"upload_time_iso_8601": "2024-11-17T19:15:29.136471Z",
"url": "https://files.pythonhosted.org/packages/b3/32/62d3799917db1dadf9a75faa032e62c7d5c4480b867b7aabea94862135d0/box_intersect_lib_py-0.8.3-cp39-none-win_amd64.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "63a39ae64ecf381ee5ea975394729ebff0dd17352bc10ed7e4551ba0056ff7ad",
"md5": "fab93f1fabdfda895148c36b09ea0ee4",
"sha256": "a46cf5db407cdea75f236b7f0048868cdf80fecc31523d68f1c1ca3ae8ae6621"
},
"downloads": -1,
"filename": "box_intersect_lib_py-0.8.3.tar.gz",
"has_sig": false,
"md5_digest": "fab93f1fabdfda895148c36b09ea0ee4",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 33144,
"upload_time": "2024-11-17T18:25:22",
"upload_time_iso_8601": "2024-11-17T18:25:22.009471Z",
"url": "https://files.pythonhosted.org/packages/63/a3/9ae64ecf381ee5ea975394729ebff0dd17352bc10ed7e4551ba0056ff7ad/box_intersect_lib_py-0.8.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-11-17 18:25:22",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Techcyte",
"github_project": "box-intersect-lib",
"github_not_found": true,
"lcname": "box-intersect-lib-py"
}
