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.7.tar.gz
(3.2 MB
view hashes)
Built Distributions
Close
Hashes for fast_crossing-0.0.7-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 22f53d2f552dbc68b74e59103cb8783ad30ce8b79d64281086b952121f3770d4 |
|
MD5 | 99e04b36b2c8558fc96aa73f093d99b6 |
|
BLAKE2b-256 | 7e90dcada99450c83e9fd6ffe02d4ff2991edc942d8fc71f2a9b08171d86409a |
Close
Hashes for fast_crossing-0.0.7-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 98f423ac97d468177b60151920b1b0a06073f8739f606aba5d45a1aa4e8b08ad |
|
MD5 | 21aa3eb66814e5cfc0935fb7beac20e3 |
|
BLAKE2b-256 | 3429b1681969ca9e83fcc8bdd2801764d057fed335fdbae8e05f098aeffdf948 |
Close
Hashes for fast_crossing-0.0.7-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4418cad870a9c9a9aa7043e77a6a8e8c121de3c0b1bfadcf67e69598f9f4aa3b |
|
MD5 | 5d14ee895890abd396db80379ccad601 |
|
BLAKE2b-256 | 2b044916071909d432db987fca36c9de112ffe7afaa851db48297a66df9d4fe6 |
Close
Hashes for fast_crossing-0.0.7-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a2129066ed812ad17bacd634b1cab8340f01377de6b121c347db0b8c4f2f0fef |
|
MD5 | 433cbdfc89f87d80780c6202224aecdd |
|
BLAKE2b-256 | 5c19e6499387071a95f967f15da753298538a43142cf200b8a876eb1c8afeb56 |
Close
Hashes for fast_crossing-0.0.7-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | df069a015bdd96d896f880794ea8c8efe862d679302b6fed29fb412afab8f9b3 |
|
MD5 | bf616f7e604571c5951e29cf85d8f9b3 |
|
BLAKE2b-256 | 1729339c1af75ad84afca52e1b7556de32b913705d3629c04e74a3132f2bf472 |
Close
Hashes for fast_crossing-0.0.7-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e9392b72d5b0bcb2745aa6f647c91e4189543cfff5e3b45c1876d02160b564ff |
|
MD5 | e46054890ac98ff434e83b0a6418f13f |
|
BLAKE2b-256 | c7aa27bc3dbd6f79209f960dd33c5e84ed76a97cc6ae5e5c442faba1901e9752 |
Close
Hashes for fast_crossing-0.0.7-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 00f48b82441fd276ca9f247c61e2640ecaa2fae61a469a22370555afadf57c7c |
|
MD5 | abcffc5ce1dc21c0fa4b290cc9af48c0 |
|
BLAKE2b-256 | 79c5b54676726b8bdd15a11569af53b9d88347eea79c8b88223ed7a74f6c9475 |
Close
Hashes for fast_crossing-0.0.7-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5fd4f02c2f57bf411fe2cb368d72407eb7d35c92e1446c900d3fe1e3d53e8087 |
|
MD5 | b63e2fc04df43c9605886fffaf64e7b3 |
|
BLAKE2b-256 | f18c45c0487128aa7f3b04c282ef08b3ea054d2bd186096d7807056fcd1bd051 |
Close
Hashes for fast_crossing-0.0.7-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e82edc89427ca3db7014a0a4450a159a89f5697437139da68ed4b83c03b638b3 |
|
MD5 | 876f357e2d8342f5274a459e9450bd9d |
|
BLAKE2b-256 | 40cb09eb0e2a06e97c1ef159f9b96e470d8fb619177bdf773c9fa365c1ed686d |
Close
Hashes for fast_crossing-0.0.7-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | aec91af053c6313fc5330ef94962264dfa8ccdeea66e7806e5c43710d505b7c7 |
|
MD5 | e7a3d0caca0e5c085b434e1a9e4f510b |
|
BLAKE2b-256 | f2e9877706c183bc5b4e98a6019cb2f722c5057676129509ef79701800abe3a7 |
Close
Hashes for fast_crossing-0.0.7-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd2b64f3841239885f56a58298e5abba7895d133fe314103f342ca92e48415c7 |
|
MD5 | 2387c71ec2ac850ad56abe6aefff13c6 |
|
BLAKE2b-256 | 4ce829480a72ef0fd5cff94d148d66eff7f613a27d27e641cb42e69c03599986 |
Close
Hashes for fast_crossing-0.0.7-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7d5b8fb872cd46a459d217f149a549920f0ef28b2150f72a79741e756c133078 |
|
MD5 | fcbfd4a8515e74c049e82a1544b8e47a |
|
BLAKE2b-256 | c67b6245fa86e8d72986505acb84b5f108dd9b9f7dcddd019e2214d31b428279 |
Close
Hashes for fast_crossing-0.0.7-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d394f28c49cee64736d08714a4268f9eb2acda67f1b1c90162e7b71103a96c9 |
|
MD5 | 71b7eb547e16151b80d839e6bd9eb747 |
|
BLAKE2b-256 | 302a19798b335546df5075ce2d750a4813e78a96af239c3d058a74dab5dca0a3 |
Close
Hashes for fast_crossing-0.0.7-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9d872672f80b06a2ba39fe62f8a89daf3c8c13ea6530e62437d9cfc6c8a3915c |
|
MD5 | a55580d9f8f2d5b264d09bb3db3f3f1f |
|
BLAKE2b-256 | 7aec18624df57c1a196a19a067f627639d9dbefd37c7d809b02695f885968d50 |
Close
Hashes for fast_crossing-0.0.7-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b414a042f051d284ee7e308f8308f68a33a52f04701fc4ca0432056e7b49a44b |
|
MD5 | f9355ee39e2b33ae3f4c2ce460728d08 |
|
BLAKE2b-256 | 1ee073b603e6556a3be5e23b819d416cbcf62eaa8f92275ea6a8ec04dc7f79b3 |
Close
Hashes for fast_crossing-0.0.7-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 41f1739c8107c21e60c9171db1d34db92c8cbba5b70f6efe50bd3bc137a1acc4 |
|
MD5 | da4b5b9ff2dfc9ef3dbe04f2a1d86e23 |
|
BLAKE2b-256 | c41be14aa4f987922c000e50d037bf88d870c54a04367984f613f05d9cdc005e |
Close
Hashes for fast_crossing-0.0.7-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f4b5e41252f19f14e5bf31bd5da114b8d4132596bac9437cf519056d9a4870c3 |
|
MD5 | 9c77336164e1871f572d5cbe9bb06294 |
|
BLAKE2b-256 | 375a7c791107562447ae09ab8fcf2915dc059c47f0334c98790f60e11788d07c |
Close
Hashes for fast_crossing-0.0.7-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 56eaf3a5f2a97a1d56e2f44ae1ef645f1fa12f07e63bcca45863bf9ab63cecd7 |
|
MD5 | e571c231216786328de6342950c68a9a |
|
BLAKE2b-256 | f61e22c7ac20673648a2c3d039d3e09e125e6088c8a8aafbfb47364855687173 |
Close
Hashes for fast_crossing-0.0.7-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 57de5af6cb3a1d872d7170850570c49f61382c987628eb933ba74d0000be4d87 |
|
MD5 | f0f744c3b5bae2d087d6b1fa6cc517c9 |
|
BLAKE2b-256 | 45e2052af5dbcad3bc801e4bac3259d4cb6d312ac1d0a64637d30cdc0e9bef7f |
Close
Hashes for fast_crossing-0.0.7-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ae96606619c557b710f69c896338324b5e70c52de21650e67616d1c7e812ee89 |
|
MD5 | c6e5d96930af4ec4906bbb0cc7ea2a2e |
|
BLAKE2b-256 | 7267b3e6c120a9509bcaa46d5bb7789b48df820b52cb337f2193779241a2468e |
Close
Hashes for fast_crossing-0.0.7-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 84041ef23345e165e25bb8acb57401b2fc29e7886df5d20c1aa98a422476f9c8 |
|
MD5 | bec45477702f8e0a7f841c97ca322c70 |
|
BLAKE2b-256 | f240f8bbea6c42dab3bb01cc371adf02757443cf8c4f5b928d7081873104013c |
Close
Hashes for fast_crossing-0.0.7-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d7c8a61a9da4568aaed0bd8537d602abe2cd316f8e93d4ce1e346741d8991010 |
|
MD5 | 4a19bb6033800172e2af6384bfcfe6a8 |
|
BLAKE2b-256 | a9be4e7dc745616907bc39bc545b157fa036599c16447bfd2bab20136215482a |
Close
Hashes for fast_crossing-0.0.7-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 497335b2f89d0a9e57cff564611c1695f2c0ba5a157bb9d8e20483c173b6e1b1 |
|
MD5 | 20f2449e45af6dc0c19089f1a0ac56c3 |
|
BLAKE2b-256 | eaeb3271ba904441e3c2969091ff063179b52678b1bf0ad775a564cf9a7041ba |
Close
Hashes for fast_crossing-0.0.7-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c941c4436494b9ea63f1b7b00fd83d7b0b2b714298300e858c55460558fffb21 |
|
MD5 | e52c63b1603eff21c1558274cfc5bfe8 |
|
BLAKE2b-256 | 4e00c43f19bf58545acc6e5859d96f986c231f9b41a1ac53ace5349c9aede017 |
Close
Hashes for fast_crossing-0.0.7-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 35a00a80908bc3c6dea9ca274021af1dd2968c2879f3463c8f84c65fe9811138 |
|
MD5 | 9d87999491d7c30de100aa59e217f6bc |
|
BLAKE2b-256 | dc447b8af91f9d6e570ce52bc3450edbff8e6c6b98718969eb68c24afaf972b9 |
Close
Hashes for fast_crossing-0.0.7-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 07cf7aab23cde31ad35b66f45c31ac830155a21f647e0b2dc6fcc913df759f7f |
|
MD5 | 68c678dbac85c676791bf989ed879cdd |
|
BLAKE2b-256 | 4efd994ba563425ecf7ebc409ea36826c1e8253637b2f5b20738327dddf9af02 |
Close
Hashes for fast_crossing-0.0.7-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c6ff1211000afd09ee2d67a9de6cf104378736868ae4805be19d387b88e85873 |
|
MD5 | d8da9f64fde1aef5717276c12862c93f |
|
BLAKE2b-256 | 346c9c780919c07bb39c2c25b3eb35a877490220fff526420e58fd9aae2a3ce5 |
Close
Hashes for fast_crossing-0.0.7-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ab9ac16f159dbcd8efcee54a46d11c959989bed38a9970b12c86a94520c7ec05 |
|
MD5 | 2169ee7f6e836f46979d022d80f3c2d7 |
|
BLAKE2b-256 | 512e607d1392f4f6893e302cb27058bbacd50a1e6314f5cbd8c10e337e82e4e5 |