fast crossing
Project description
fast crossing
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
)
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.3.tar.gz
(3.2 MB
view hashes)
Built Distributions
Close
Hashes for fast_crossing-0.0.3-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 04dfba996ec816c30696ab6d0b122f3a8b3bb5490ae6ddfc3980d174c3d59b2a |
|
MD5 | 43ec8ee3b0b5d6fda6ce27ebafe565af |
|
BLAKE2b-256 | 74d00a53ae06887aab7a4fd92cf800bf3a2bd95652f59e0e2df7b5b4e75a8a78 |
Close
Hashes for fast_crossing-0.0.3-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8842d670145934e7ce2a4878565b096824dcfedfe10c0ae4995ebc3fac67573f |
|
MD5 | d449fc8d18cd4cb61dd59da85a99a7f5 |
|
BLAKE2b-256 | 4ce46a5b0ad9c1e3bd714d7e764f566d42150fb8b7a1afd7147dd6960ef5c519 |
Close
Hashes for fast_crossing-0.0.3-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5aa930d5379f57d2029541dfdc3267c1c3bf4745b481927c21b7c54b955496e7 |
|
MD5 | db045b7442ebefdf888793224c06abd1 |
|
BLAKE2b-256 | b173886e6ed947239c4a4e311af9102c88ab8d34bd9285adbad4c598178daef4 |
Close
Hashes for fast_crossing-0.0.3-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6edcf7583697d552c2b31c751d56f743e17f0e03f036db3c78737f87b39bc946 |
|
MD5 | 7c73c6156c4ce20a0bceb13b840ec523 |
|
BLAKE2b-256 | 759c4fa4200ea0ca24949e988ae79366d8da9816e5f9f6baee068305ca6b965e |
Close
Hashes for fast_crossing-0.0.3-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 68dae15f9d37e3882ec56e032e0944dea159ce63296fe555baa51a8e6bf5246f |
|
MD5 | f470bad3d2f8f012d3543d2e9224227f |
|
BLAKE2b-256 | a0c989d07eb85a958349d744718eed47bcb17bc723148f3c8193a896f46059e6 |
Close
Hashes for fast_crossing-0.0.3-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 27996879a10b5a43b78c76206c474ed05269df6ac802972491f414accb0f53c0 |
|
MD5 | d50a308b065981cb11ce58bc74a2d278 |
|
BLAKE2b-256 | 106e140daf596badf414bf58eb2f4929b83175eb36ac094afbb27d2fbe08e4fb |
Close
Hashes for fast_crossing-0.0.3-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9669a17bdb8501b8ae1d4c33b154d8f1af5cd497e072c456c250e8269981b77 |
|
MD5 | e9a669e9599a1b1c4b39f1d84fbeb264 |
|
BLAKE2b-256 | ebc92ba39cdd0fc53cb789d0928c538feb4bfed4d6fd660fa7bef9b775f36b61 |
Close
Hashes for fast_crossing-0.0.3-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 16e335413a59ed4457f91ea5f52707ed19d55ed18beaf67b6647f6bb4415d8a9 |
|
MD5 | 1e9e1157e2d077075f5c51e4b242c44e |
|
BLAKE2b-256 | c333d3521cd2d702b24d3a5890f4688f1a3e2037955ebd7675bed5795ea2e319 |
Close
Hashes for fast_crossing-0.0.3-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0ea86d8b3cffc4846c6e19e3d76b01448197e2e7037f45570215b2858b2f7ede |
|
MD5 | 2b65f453f593b1f5ddfa3ce807cdb6cf |
|
BLAKE2b-256 | 0df9c5bd502c69a49856d61ed643ce9d9a65ebaf56ec0628443c0f68a76f8d37 |
Close
Hashes for fast_crossing-0.0.3-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3e67229b4da981588c16327b5b6ecdbce54b59049e8a810aae30892339d36b3f |
|
MD5 | 32897850f531ce36514e48d637fd9c66 |
|
BLAKE2b-256 | a7ec76b2940e3c55120b356e7278955d95878ccbd70fb3005a2e71dee0d5e54b |
Close
Hashes for fast_crossing-0.0.3-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 260673a713f273c2bfd5cd3d8d54ea2f4406ad6dfc6639d44fed465717e98809 |
|
MD5 | 370de86aad72b6afb3efc56803e47f69 |
|
BLAKE2b-256 | 611db776239a347ea3e13138630f4173d104562213d207dcaaaad5c279075caf |
Close
Hashes for fast_crossing-0.0.3-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d80ef46587d46ee3177a3c7f19d8bcfbfc0b3cef1c5cd59d70017a35d02fde67 |
|
MD5 | a378a64025c8933877440a23cf33485e |
|
BLAKE2b-256 | ac8077cd9613228f453e625c6e57dc1f90e6638197803a89175148a2e8428264 |
Close
Hashes for fast_crossing-0.0.3-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 43aaf525fb6522a8f5672e43ff2b35fd7c467ad4f4c9cbef18c868676a937c37 |
|
MD5 | dc110bee5ad4d8cf84a901d26d8e8d96 |
|
BLAKE2b-256 | f70900bb804eda16ecb516a6a8d7b754f87dbd84ee6279d51e57230941e280db |
Close
Hashes for fast_crossing-0.0.3-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae77836d9d7d2a52b0b077b6952bbf0bc9b5d93189331fea44de8552231bb1c4 |
|
MD5 | 1066d7681dec555ef08fd4619f0d327a |
|
BLAKE2b-256 | d9f6158f92bae2c9a7a79383a7ca93dfb485910bb5977920a3b7d8a7bf367f88 |
Close
Hashes for fast_crossing-0.0.3-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f512bbc970171775435154e12b1de4483052ab3ac8afd36096123b699ddb5d36 |
|
MD5 | 3db0c15e71ab996271be669ebe2ba308 |
|
BLAKE2b-256 | b6912176dadf444ece1da1ff5e6b02309bfcec925daeb2dd84960c4eb9ed9354 |
Close
Hashes for fast_crossing-0.0.3-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8dead9d1c9eacfd321bb2056318b0b017e2225e6e8567271f1bb127a54b5f1e1 |
|
MD5 | 5beea0c285a0ff4e3931a266db79f90a |
|
BLAKE2b-256 | 1cf784034471ced311840c07e83d3f1d78d6487c52fcef6dec0d91d86f0caf17 |
Close
Hashes for fast_crossing-0.0.3-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0477d7cd4347454cda15d7d6410cdf3a9fdd8e295c9ff559039844bc653f26aa |
|
MD5 | 5ef8eebd95f0e022439c8c59fdcfa372 |
|
BLAKE2b-256 | 677599fbf4702bdc9fa32ae51cefcec85c68aefc2f95a794ceb1090ec547569b |
Close
Hashes for fast_crossing-0.0.3-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 46700ae136e444bf8f1f9eb057d3614abad43237313b3bc3c0c0f3608db3cdbb |
|
MD5 | cfc8f7900dd370348322f284433b0f84 |
|
BLAKE2b-256 | fd7890eb9f1d5c8d15ffed40c443367a2a7619a71772b70384440eac94cd767e |
Close
Hashes for fast_crossing-0.0.3-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4fae23ed7307bea6cda2d2b5ac8cf9631881b59e7bbb8495ff7dcf7f7a456a67 |
|
MD5 | 97aeb3684ef4a9d555feb824a88ba1ce |
|
BLAKE2b-256 | 0a1ebd761bab2e668e424061c3ef71fdf444cc5f1aee72e21edda5f1ee2af427 |
Close
Hashes for fast_crossing-0.0.3-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 349c80e50677b869d0543d32de321c980875ed2abe9e3ba17c864512746c155a |
|
MD5 | 463c10c0265a80191b9f42e96c7da53f |
|
BLAKE2b-256 | 1d935b5b3bc41ffa0801449f2dc978fb8728512c12d7d300574658b1fc0375d7 |
Close
Hashes for fast_crossing-0.0.3-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ef63fb50b7745f0e636820a2b446d3eb0ac1c35eff34baa518346ff9fc39251b |
|
MD5 | a97a707546bddc8383ec7ea16d4ed399 |
|
BLAKE2b-256 | 07121b7477ca7fbe3e7089d703d2daea3ebfed2d4fa54613b12d458f814d1122 |
Close
Hashes for fast_crossing-0.0.3-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f0f7604fddc2049fc029a3d30339d47b9c5d8eb7bf07a89faf320ecd9bff17cd |
|
MD5 | 912ee7e07b5777b634bee05f73cb475e |
|
BLAKE2b-256 | 48a3316184370e23a190e4d7e44b245a198bcb883e5d83fc215c00ac7f975d9e |
Close
Hashes for fast_crossing-0.0.3-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b6bc7af710fc88659a9845a6b713603769f368044c7e3ce87b01740634157054 |
|
MD5 | f916198ade766e9b77fa0bd95acf1bff |
|
BLAKE2b-256 | 3742ecb111be4334a8a9328522fe54e6e5ad1787620e4bd6e2eb7975f6a954de |
Close
Hashes for fast_crossing-0.0.3-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3ef786fd3e6cd98b3d8d306847818431a9a6f07437f17a389eea2e88217275a9 |
|
MD5 | 4f2fd4d6c2236cbbc92c62b2134b31a0 |
|
BLAKE2b-256 | 07e3750ffde65d2a10b1b9a99d88da972313fed32b5107d897f4c4f24451bd0e |
Close
Hashes for fast_crossing-0.0.3-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7bef55e549917ea9591892e91c511688d87cdeacebaddc687a4e6281a0d95036 |
|
MD5 | e90e5b84029535a503a28bff9c04fc88 |
|
BLAKE2b-256 | d049c05fcf3d2e40cc9ddaeb6dac46137f88cab2b779e9e394d8b0bef52449a3 |
Close
Hashes for fast_crossing-0.0.3-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6b1d35fd742665b58ecb93a18b1f6d6c26328de508b54f50f57b50d3ae9a089a |
|
MD5 | eae9ec61af3100c31906db9104b82123 |
|
BLAKE2b-256 | 896d6364a15f14d981a83d223c4b137a5d2659672664c1da57cbfbb04179853a |
Close
Hashes for fast_crossing-0.0.3-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 06755f8732559efa70ee1fbbef22cf508c3520c47a5417a216bad84e27de7805 |
|
MD5 | b4993934f7e82acde5ddc5bd46e69f67 |
|
BLAKE2b-256 | 32d7f52f78abdf62c47c199055c61dc6fae1eb48fcb1131d8c11337628e0929a |
Close
Hashes for fast_crossing-0.0.3-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0262c34970a59853533753ee17097aee0b342eee134e131dd45eb746a7d534e7 |
|
MD5 | 8811cbbf5cecf0bfc9c146ab0b8590c8 |
|
BLAKE2b-256 | a9631a8063f2adf51d14eae1141db6540095260c8ce7c6cbc3fe049b98f7a45a |