fast crossing
Project description
fast crossing
(See jupyter notebook here)
Fast polyline (line segments) intersection (fast version of bentley-ottmann).
Installation
via pip
pip install -U fast-crossing
from source
git clone --recursive https://github.com/cubao/fast-crossing
pip install ./fast-crossing
Or
pip install git+https://github.com/cubao/fast-crossing.git
(you can build wheels for later reuse by pip wheel git+https://github.com/cubao/fast-crossing.git
)
Related
Inspired by anvaka/isect: Segments intersection detection library.
Usage & Tests
See tests/test_basic.py
:
import numpy as np
import pytest
from fast_crossing import FastCrossing
def test_fast_crossing():
fc = FastCrossing()
# add your polylines
"""
2 C
|
1 D
0 | 5
A---------------o------------------B
|
|
-2 E
"""
fc.add_polyline(np.array([[0.0, 0.0], [5.0, 0.0]])) # AB
fc.add_polyline(np.array([[2.5, 2.0], [2.5, 1.0], [2.5, -2.0]])) # CDE
# build index
fc.finish()
# num_poylines
assert 2 == fc.num_poylines()
rulers = fc.polyline_rulers()
assert len(rulers) == 2
ruler0 = fc.polyline_ruler(0)
ruler1 = fc.polyline_ruler(1)
assert not ruler0.is_wgs84()
assert not ruler1.is_wgs84()
assert ruler0.length() == 5
assert ruler1.length() == 4
assert fc.polyline_ruler(10) is None
# intersections
ret = fc.intersections([1.5, 0], [3.5, 2])
assert len(ret) == 2
assert np.linalg.norm(fc.coordinates(ret[0]) - [1.5, 0, 0]) < 1e-15
assert np.linalg.norm(fc.coordinates(ret[1]) - [2.5, 1, 0]) < 1e-15
xyz = fc.coordinates(0, 0, 0.2)
assert np.linalg.norm(xyz - [1.0, 0, 0]) < 1e-15
with pytest.raises(IndexError) as excinfo:
xyz = fc.coordinates(2, 0, 0.5)
assert "map::at" in str(excinfo)
# query all line segment intersections
# [
# (array([2.5, 0. ]),
# array([0.5 , 0.33333333]),
# array([0, 0], dtype=int32),
# array([1, 1], dtype=int32))
# ]
ret = fc.intersections()
# print(ret)
assert len(ret) == 1
for xy, ts, label1, label2 in ret:
# xy 是交点,即图中的 o 点坐标
# t,s 是分位点,(0.5, 0.33)
# 0.5 -> o 在 AB 1/2 处
# 0.33 -> o 在 DE 1/3 处
# label1 是 line segment 索引,(polyline_index, point_index)
# e.g. (0, 0),polyline AB 的第一段
# label2 是另一个条 line seg 的索引
# e.g. (1, 1),polyline CDE 的第二段(DE 段)
# print(xy)
# print(ts)
# print(label1)
# print(label2)
assert np.all(xy == [2.5, 0])
assert np.all(ts == [0.5, 1 / 3.0])
assert np.all(label1 == [0, 0])
assert np.all(label2 == [1, 1])
# query intersections against provided polyline
polyline = np.array([[-6.0, -1.0], [-5.0, 1.0], [5.0, -1.0]])
ret = fc.intersections(polyline)
ret = np.array(ret) # 还是转化成 numpy 比较好用
xy = ret[:, 0] # 直接取出所有交点
ts = ret[:, 1] # 所有分位点
label1 = ret[:, 2] # 所有 label1(当前 polyline 的 label)
label2 = ret[:, 3] # tree 中 line segs 的 label
# print(ret, xy, ts, label1, label2)
assert np.all(xy[0] == [0, 0])
assert np.all(xy[1] == [2.5, -0.5])
assert np.all(ts[0] == [0.5, 0])
assert np.all(ts[1] == [0.75, 0.5])
assert np.all(label1 == [[0, 1], [0, 1]])
assert np.all(label2 == [[0, 0], [1, 1]])
polyline2 = np.column_stack((polyline, np.zeros(len(polyline))))
ret2 = np.array(fc.intersections(polyline2[:, :2]))
assert str(ret) == str(ret2)
def test_fast_crossing_intersection3d():
fc = FastCrossing()
"""
2 C
|
1 D
0 | 5
A---------------o------------------B
|
|
-2 E
"""
fc.add_polyline(np.array([[0.0, 0.0, 0.0], [5.0, 0.0, 100]])) # AB
fc.add_polyline(np.array([[2.5, 2.0, 0.0], [2.5, 1.0, 100], [2.5, -2.0, 0]])) # CDE
fc.finish()
ret = fc.intersections()
assert len(ret) == 1
ret = ret[0]
xyz1 = fc.coordinates(ret, second=False)
xyz2 = fc.coordinates(ret)
assert np.linalg.norm(xyz1 - [2.5, 0, 50]) < 1e-10
assert np.linalg.norm(xyz2 - [2.5, 0, 2 / 3 * 100.0]) < 1e-10
def test_fast_crossing_auto_rebuild_flatbush():
fc = FastCrossing()
fc.add_polyline(np.array([[0.0, 0.0, 0.0], [5.0, 0.0, 100]])) # AB
fc.add_polyline(np.array([[2.5, 2.0, 0.0], [2.5, 1.0, 100], [2.5, -2.0, 0]])) # CDE
ret = fc.intersections()
assert len(ret) == 1
fc.add_polyline([[1.5, 0], [3.5, 2]])
ret = fc.intersections()
assert len(ret) == 4 # should dedup to 3?
def test_fast_crossing_filter_by_z():
fc = FastCrossing()
fc.add_polyline([[0, 0, 0], [1, 0, 0]])
fc.add_polyline([[0, 0, 10], [1, 0, 10]])
fc.add_polyline([[0, 0, 20], [1, 0, 20]])
ret = fc.intersections([[0.5, -1], [0.5, 1]])
assert len(ret) == 3
ret = fc.intersections([[0.5, -1], [0.5, 1]], z_min=-1, z_max=1)
assert len(ret) == 1
assert fc.coordinates(ret[0])[2] == 0
ret = fc.intersections([[0.5, -1, 10], [0.5, 1, 10]], z_min=-1, z_max=1)
assert len(ret) == 1
assert fc.coordinates(ret[0])[2] == 10
ret = fc.intersections([[0.5, -1, 20], [0.5, 1, 20]], z_min=-1, z_max=1)
assert len(ret) == 1
assert fc.coordinates(ret[0])[2] == 20
ret = fc.intersections([[0.5, -1, 15], [0.5, 1, 15]], z_min=-6, z_max=6)
assert len(ret) == 2
assert fc.coordinates(ret[0])[2] == 10
assert fc.coordinates(ret[1])[2] == 20
def test_fast_crossing_dedup():
# should be stable
for _ in range(100):
fc = FastCrossing()
fc.add_polyline([[0, 0, 0], [1, 0, 0], [2, 0, 0]])
fc.add_polyline([[0, 1, 0], [1, 1, 0], [2, 1, 0]])
ret = fc.intersections([[1, -1], [1, 1]])
assert len(ret) == 2
assert np.all(ret[0][-1] == [0, 0]), ret
assert np.all(ret[1][-1] == [1, 0]), ret
assert ret[0][1][1] == 1.0, ret
assert ret[1][1][1] == 1.0, ret
ret = fc.intersections([[1, -1], [1, 1]], dedup=False)
# for idx, row in enumerate(ret):
# print(idx, row)
assert len(ret) == 4
Project details
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
fast_crossing-0.0.4.tar.gz
(3.2 MB
view hashes)
Built Distributions
Close
Hashes for fast_crossing-0.0.4-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a39b09c5cc7de2b07da197b9acd76c98960663ddf59bac9f2365ed3e59061679 |
|
MD5 | ef6f9fb3eeee537e4198baac651bc308 |
|
BLAKE2b-256 | d4d7a5e5d5826df04626229c8a650189401a21e9490622aab0c7c93647c521be |
Close
Hashes for fast_crossing-0.0.4-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e17030cc3ef5edfe53cb94d6f777e8cdca70607189c4a02542a719961febafcc |
|
MD5 | ce69dff39317da964e070a675915dfdf |
|
BLAKE2b-256 | 360310b146b43a7b1361327d9b26da2c548bac6ad9f28581b61891a9fe921a5e |
Close
Hashes for fast_crossing-0.0.4-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 97f6cfeaca9faf7dac16751f5b93caf4cad7313ce44d697bd4690eb62061c1a7 |
|
MD5 | b31014641ad708b88cfe14ab3dbd7558 |
|
BLAKE2b-256 | 7845c127bbdf3dc0211e416f4b20e83473f84cca151412101234c27290fa3f03 |
Close
Hashes for fast_crossing-0.0.4-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 513539d860541c572530e4fccae5b3fbe11d5a0cbe63fc8dd79a040b2317bc26 |
|
MD5 | 7ed3cf1a50a9079e750519dd4c051604 |
|
BLAKE2b-256 | 73d5e70ee96e30b33263eee7e0888d223b6cc9ef027da545c267d7fe42ee51e6 |
Close
Hashes for fast_crossing-0.0.4-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5be8dd0dee019be99a629fa69c9c3888ee386055d1890faebae0a73ec5ebe268 |
|
MD5 | bce0848822fafb96c56a3f449ac23558 |
|
BLAKE2b-256 | ac12e6ca571ac2e1e17b912c6b6159f930d85c061bf122bcd8350f294a011191 |
Close
Hashes for fast_crossing-0.0.4-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7f8de6e66d9e47b31be5fb6630247b444694ebdce6bd547e0b27423b543c4a8d |
|
MD5 | 81b530349d3f15ef69a712a12dda300a |
|
BLAKE2b-256 | 5a40340133ed92b85cfe957166445a37440adf797ddb8d4a1bfe1d220aabd735 |
Close
Hashes for fast_crossing-0.0.4-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 887a5f92c11e1de233711b296547979f976bf970c7b8e4c0cd35b60030bf8e5b |
|
MD5 | 8c5449ce446d23c6b37326710183761f |
|
BLAKE2b-256 | 4bdc57b8b00c91aeba4a35ba7e4ffe7a49852021807949788fd684cf9a977b96 |
Close
Hashes for fast_crossing-0.0.4-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 157dbd77c0ab6dea9a4dd5d0ae9d5246528235bbb737490994a5cd00a851fa63 |
|
MD5 | 85fb6ab402fa91c3a485a7ac9d17702b |
|
BLAKE2b-256 | 7342c3386f5af38754550fd53d3fd0f602b51ab17fff73f0566c214802dcba10 |
Close
Hashes for fast_crossing-0.0.4-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5fd217f182ea7a265f40175c80e0833fcf2317251380a58ca2c0ea9e98e4af43 |
|
MD5 | 887699d8a5ae0ab438dda7d7ee186086 |
|
BLAKE2b-256 | 1fc5f61dd1433dabd9520be65c5153006f12ecc8143f1a8f5a89913f0d1ec893 |
Close
Hashes for fast_crossing-0.0.4-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a71a6ba58d1a15c68b5411db6093842288f64c30d3a518c22f213d704bbd7df1 |
|
MD5 | 75981b66b141fb46d71afee31a3e6491 |
|
BLAKE2b-256 | d744f16d5bb055f6067b721e47dfdc1dd5c61467a2abdeb908214b00ae372868 |
Close
Hashes for fast_crossing-0.0.4-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 07c473e18499bc86ab1672f5102a0844634dc922b53e925d80a9db8e0d91ac54 |
|
MD5 | 579d01416b3f8602392bdced309ecf95 |
|
BLAKE2b-256 | 1ba9c9b3823e5856e3e09356ba3b24e797b2e7d4c5c86e2c8b221184e18629ae |
Close
Hashes for fast_crossing-0.0.4-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ffe05b221f3c297d419d90268b8c60beb4193a2f282dbebf424c22ca4fb2c1a |
|
MD5 | a80995aeb3f54974fdf98867d2a4a72b |
|
BLAKE2b-256 | c80df198fcefe3be9881b746dd269231802d08192d76697efa236e920fea4827 |
Close
Hashes for fast_crossing-0.0.4-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b2c225c51354f62cf0236c0164c952d414a4164315850278632ecd219d6b3ba4 |
|
MD5 | 1b8ae0c53ac9ba49d2a7c87ee72ad60f |
|
BLAKE2b-256 | a317cccb2ff413bb654f10c4d4e688dfb98e3cd3f6c70c489f37e88488344a02 |
Close
Hashes for fast_crossing-0.0.4-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0253d90434cc041aa5793e4b7cb8a30e671701f56557bbe72e507a8637d8cadc |
|
MD5 | 0918ed39878f2826d69b9038fdaac96c |
|
BLAKE2b-256 | 5dfb53088da76ea348375ff33dac6d26d89aa28a1beac2986801ab7b54d8fe48 |
Close
Hashes for fast_crossing-0.0.4-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 41c0be0b15d173ab11ac1904674dc9062ff8142cf0d21710e97fda3454c64830 |
|
MD5 | 2747f561de95b86b7785d8360df9eb79 |
|
BLAKE2b-256 | e24ba244db1e2787b28a7e0f421eaa632f99a55e413e18b22e46e2cab5f0c230 |
Close
Hashes for fast_crossing-0.0.4-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d567dc7c4d8adebd1b2f9a8ec9838020d02c71f244c61ff14280f33a19c2416a |
|
MD5 | f49903d55b8e7a28088ed5d1e047c9dc |
|
BLAKE2b-256 | 582c212b3cfba1c56881a51108f491fc052a38eda5d8e404e1eb6ab3f01b012f |
Close
Hashes for fast_crossing-0.0.4-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 48e921d1e3917724312b05421cf188ba63fc5f90c9fe83d031889f4642cd2919 |
|
MD5 | 31d99d37dc169c48e29b8a0eaa8f5fed |
|
BLAKE2b-256 | eadd975c0c59f3616aa0f0b2e5b4b46a0e31257c7be6c526dee12ac7ba48d0a5 |
Close
Hashes for fast_crossing-0.0.4-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 967cd07cce89f0ad54b0109b9b259679db4ece0628fd2dc21cc7ccae9c67f4c9 |
|
MD5 | 83877b1832de8e993b682d8c6d979aed |
|
BLAKE2b-256 | 0a6c51eebadd9da32487f84fe6d3f1d7579a51956c384e6b8e4b1f8bebdfbf2d |
Close
Hashes for fast_crossing-0.0.4-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a26860021ab7702245f70b69dc3ef57e4dd026c30cbbc5348851405fd4c256e1 |
|
MD5 | 5db8943f59dc0850c04040d23153e248 |
|
BLAKE2b-256 | 2bf27a8831655607f3a1124c1c74f208264cc5d3e28fcf7fd26f260cac6c9042 |
Close
Hashes for fast_crossing-0.0.4-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 47709f829077b5cc1b3e69691bacc3940e873ab3d57e82f8ab197ae1034f8a78 |
|
MD5 | d84366264852551a931fffe2918ff7ed |
|
BLAKE2b-256 | e68175b6e85f7a59364aad54c0008c437b2f4022330d372fb3e69b2f957c79f3 |
Close
Hashes for fast_crossing-0.0.4-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 23d105442993ed9a444c22a9f40f93c28813cb9f57df8e84940b866009b6a7ab |
|
MD5 | 878e11ab0f33983b314ee305ef456019 |
|
BLAKE2b-256 | 8164b993774d09872b32b2ea3a82bc85876dac29c5585ec44da895005165c9fc |
Close
Hashes for fast_crossing-0.0.4-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 34095424347c4dcf7691237cebf1624b16c32420d057f78c495a96ae07d09d26 |
|
MD5 | f367be8c43d801b2f03d4f918430aba8 |
|
BLAKE2b-256 | ecd07341dd4d2e59e534f1cfb72d50e9161ff00738ed33c22ca30615eb3bcd84 |
Close
Hashes for fast_crossing-0.0.4-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9ba465343f1c44990ff95625572b294ce1cedfce288c5c0a49e91605839141d3 |
|
MD5 | 68faee35fa59fffa5fbc87f8ca86ad27 |
|
BLAKE2b-256 | 9fd1b64c35e72b37d2df6f1ef71bef911749f9885a20fb445e9fc74cd6e97576 |
Close
Hashes for fast_crossing-0.0.4-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e4e62135f5a2a88f78f1fba984bf6be5fa838ef582ec99799ce511c83d527913 |
|
MD5 | 868e2f88ef1ed3b6b04609f783b4259a |
|
BLAKE2b-256 | 315ad98b8c5e84f04e142a59161c8adf0fc2d8119fe76c308614a616af88936e |
Close
Hashes for fast_crossing-0.0.4-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dd5a75e584eca3ab053a122124de082b5a697e01976ab7c61dd19d4ef0e72093 |
|
MD5 | 3abdd28a0160baf2dbc770502f82d1fd |
|
BLAKE2b-256 | 3b0e97c2107af4d6263e1715debfebb1f4841a02ab2e081bbedde0c459bde3bc |
Close
Hashes for fast_crossing-0.0.4-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7e1a4a13121dcbce63a435a7dac68ac49560aa9af319f0a7d9912c857f31ae4d |
|
MD5 | d25fd2264aeb7509ea8febc827e4cdb5 |
|
BLAKE2b-256 | 5d9966c491658efee3deb746d8dc58009f414ee3b419aaf59490efe4d666f790 |
Close
Hashes for fast_crossing-0.0.4-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c564be934f1abc058ac4bb8ccd033c5d0722cc3620eb8102da00c1c4feeca95e |
|
MD5 | 4ac0843c3ec2df44da549572c7e2c0a3 |
|
BLAKE2b-256 | fd9d305f29a53afb7ed31626658f2d91260430a7acb5e5e310088f9728c246e3 |
Close
Hashes for fast_crossing-0.0.4-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8906dfb159d653f4f77fea00b912420958c2d30776d6d35e29981abbc060d915 |
|
MD5 | 89e04abf528ae6804237e14b4a8f2eb1 |
|
BLAKE2b-256 | 12d17251192818bd8fa6b4d27d404fa1dcbf04d2ce9e3a8f70c58c6cb5f8a08d |