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.8.tar.gz
(3.3 MB
view hashes)
Built Distributions
Close
Hashes for fast_crossing-0.0.8-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4d9a48759c6784f78f04c5139434628c25e6571bee791744bbc24bab2e29639d |
|
MD5 | 9965d127db917edb0476ae0119442c3c |
|
BLAKE2b-256 | fc7fcd782450efa40e9882b271833b778947193a5717189a8254f6fda3c3a95d |
Close
Hashes for fast_crossing-0.0.8-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0f74f99083941290557d9334ef0abdb2cea65efd5f48b7928f1a600ba873c3a1 |
|
MD5 | 4db797e244290d7ef0eb12503e4250e6 |
|
BLAKE2b-256 | 244583b00f40099931ff181c15619c8ab13ecb21199bbcdddf1708be2ef87248 |
Close
Hashes for fast_crossing-0.0.8-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a2897b42103f0c00d38328a59c1a35f00be47534ff093db5ae58566d1fd66434 |
|
MD5 | 1267b8c54c67a98dd0fd64e13e25d6be |
|
BLAKE2b-256 | 4c2e33af7ed7bd66d6f00ba0f643dd315cf94de0dc65df8ab68e1e651845de33 |
Close
Hashes for fast_crossing-0.0.8-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ff1e0bb4f8f8af288399165e8f6a5bc4e8e2bdcac41c7344f4f93049ee09e3ca |
|
MD5 | c5f64692393f837cae12e011505bde8f |
|
BLAKE2b-256 | 7dc82f09663a1892794e5ae413efa3ee92bb05fbbb17c0dd9bc118296045d3e6 |
Close
Hashes for fast_crossing-0.0.8-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 086ffe4c34bc5132b8d28387194261197f981cec6aa5060c6c3800e3fa4317f3 |
|
MD5 | 991a24c19feef30b218e035436711304 |
|
BLAKE2b-256 | 275ffbfcb6c39aa3886fb6ff9eb54681b748cff51dfebba6b8cd062e29ae9a63 |
Close
Hashes for fast_crossing-0.0.8-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 14816b6bfbe5496291b7623056d612c48f92d3aeab9efdcbd646a774885ddb9c |
|
MD5 | 126a4d773a12f43db28ca2720b9a35ca |
|
BLAKE2b-256 | ffb544cdaa24b231443aa476d683926931a33638266814fb29e927128ea51ead |
Close
Hashes for fast_crossing-0.0.8-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f3f758621425fe2fdac51cf11878d77480afc6c95e67950b1645a1dbd13437ad |
|
MD5 | ae00cd1c0326fbb85c60628243b25cf3 |
|
BLAKE2b-256 | 914c32ad154d51b1ac708cd5b82338c80d7de137431d44835973a704ca7cc9cf |
Close
Hashes for fast_crossing-0.0.8-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | de3680339f3929819fe7a074c9c83e4e4516ae4ef502b504ce811375bc8c1a6d |
|
MD5 | 2435f7792385894429f797b72d9a158e |
|
BLAKE2b-256 | fe1f3ddf299cbbe3ac8922a916099abeb8809d7dccade00e16b69efbc306930d |
Close
Hashes for fast_crossing-0.0.8-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5fb7f16676aa46dc2f83a46460f67d5e112b2ed92cc6a9b37d4bc782e24caed4 |
|
MD5 | 85199ac6cfa8153b5e39cfef38aa4d4d |
|
BLAKE2b-256 | bc7dc098a5c14ba6e46d29605c84724ddd271eae27cc27be5ddfe1e13d6dcc44 |
Close
Hashes for fast_crossing-0.0.8-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 831c7939ff9698f3cbea5d2f926d6e71b550204110bf5123e0789f2a388de992 |
|
MD5 | 9068aa0b02fa1e4ecda7c81a00593395 |
|
BLAKE2b-256 | 20cc2a3d57c42c5dab64eb1df1374d556414692397a81ca2f258fc17beb457b7 |
Close
Hashes for fast_crossing-0.0.8-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f219abe7cd33d031e319434984e1f1dd15815d57e95b5665b7fec1e710507967 |
|
MD5 | c99ce24a3a8e89c553af89eb7bb71548 |
|
BLAKE2b-256 | 62817da253e2db45fb94fcb9c583d05044c1b3c228476921f3dcdf6a2d89d4ca |
Close
Hashes for fast_crossing-0.0.8-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7f9d03bba21b6411a538267b86b95491e177cc7f17c865a1af1e8eb425554ac0 |
|
MD5 | 163f2d1003ccd840c5d3146a48ac92d6 |
|
BLAKE2b-256 | 5372d092e75087f1a443b54dddd6220c4c0c3984eafbc8d532d91dd979297b63 |
Close
Hashes for fast_crossing-0.0.8-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fbeece624113f428da6d15eeb234cb6985e7d44e0206ececda23e473d4269607 |
|
MD5 | 7507614f280b9f8b665c4da8eefeb2a1 |
|
BLAKE2b-256 | 7dbb5f3b32e9a3dc1d0f3f7696fb7978c09315024e490ac0233f0df0799b7f36 |
Close
Hashes for fast_crossing-0.0.8-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 19a2b135b4c65c5e02034b4635949d140eb7713941c8401498b177217f4ee76a |
|
MD5 | df3f9f5e19aa0835a5c62616caa07744 |
|
BLAKE2b-256 | af6df61d39a834f8c9ffac4e0620e89105a1bb28124373b965c0d1f601bae5d4 |
Close
Hashes for fast_crossing-0.0.8-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a6031f0b0c9cbe24b373a4f9e1538da715e28df6aca65af196762224ec99a09e |
|
MD5 | 1d5ef60d54eb1d13a577acb9621046a9 |
|
BLAKE2b-256 | b2d43afa66ab65eb48f13f8b1f768d3f6cdd034cba6309c1955b97c43e31efba |
Close
Hashes for fast_crossing-0.0.8-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 559fbe0d0cd26d15f60792680f7c6687449ab2999bd6c7d2b6e70e11a550373e |
|
MD5 | 6af8f945e1cea56870c412aa23e97078 |
|
BLAKE2b-256 | 45b7fd89ff7ee2278d643906b7a4d99f5addc81692981d17f2bb3350bfd5a9ce |
Close
Hashes for fast_crossing-0.0.8-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f2d1d23805e6ad0e2b5140c19d16fa764c219559dbb74411bd3c8329cab0dccb |
|
MD5 | ade4cb04c1c8f390da6ef3e0b0fe87ad |
|
BLAKE2b-256 | e03a4eed95d6169905a7d4e4614ae14e2ab8a9540d81996bd11cdef89b917c40 |
Close
Hashes for fast_crossing-0.0.8-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f62e2ab9bf49b2ab8cceb4a665bac60d61af0461e687d2f4573e56dfaced90a4 |
|
MD5 | c65a85d9927d8635d72f70a9b7811465 |
|
BLAKE2b-256 | b4cbd1cb8314213d6de20ff29171a6907f830a96cf5b64dabed6e867780360e0 |
Close
Hashes for fast_crossing-0.0.8-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c780e563a99f8eded55dbb2f715323675042fa3a47f38ab9d30f709dbb5d4e90 |
|
MD5 | f98d6bafb43a36b06168c38162f6d7fb |
|
BLAKE2b-256 | 03f8cf38106d7fcbcdd8cc8480ce0f7e8102dfaf8d6b53120c9a88286576e63b |
Close
Hashes for fast_crossing-0.0.8-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b7e9ebf37494c6376eeee423eaf9d17f6ae890c0f1ff3e2153c03180b40ee00 |
|
MD5 | 90a0f5c69d067c2b92c33fd860112fbc |
|
BLAKE2b-256 | a9bcccd2f4497e8ec1de4dc0ea6158958bfae6171ec7a4c84a2345fadbd6d3ec |
Close
Hashes for fast_crossing-0.0.8-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 699d488e172ff9d87e45ee71ec37c46a3ea275d869c5001379297d3ad4ab04c6 |
|
MD5 | 2a7f4b12f1c5b1371733a455d8c68d66 |
|
BLAKE2b-256 | 629f7c399fb962a6b0605554c462dc54acc90d10946a2881cc57e059552b4f3c |
Close
Hashes for fast_crossing-0.0.8-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d6b4898ae461ffd551f490a0e8a109f0fcd61142d8090ec13abdc5bdc5cbf747 |
|
MD5 | 1577ef9342f206620002881f881d9650 |
|
BLAKE2b-256 | 769a59e1752ab1dfccf641ef3ab4bf4be665068e40b10afb674536d1957ba28d |
Close
Hashes for fast_crossing-0.0.8-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | be16477b717b67eb81b8053cefb29170e61ec9b471f6ee0784af306997323759 |
|
MD5 | 99db18a577017fd5e852b9598af0d0d1 |
|
BLAKE2b-256 | 752667f10a37eb8374656201a6a49114e9798bc17a6f9a00fb1b89d54a4d19e2 |
Close
Hashes for fast_crossing-0.0.8-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 308dc00cd2b5d84b2e52bd88d25e5ee7fbddcdc6b64ca3bc32535a08b1519829 |
|
MD5 | b207a8cab7015b350c3908d0af9cb99f |
|
BLAKE2b-256 | 462c12be3d0c50e1481ba40463aae28af3a98d16dc7593a1dbbab48ddb586c9d |
Close
Hashes for fast_crossing-0.0.8-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e2289440d913ee5761a1fdc4c9216fad327248bf00829463b594688f8ee5fd26 |
|
MD5 | 5ef71d7b71a81c4042e49a4b7fd43c17 |
|
BLAKE2b-256 | 739f1fa2331e6809b7d2ebee834f1126c62f7058b0e2827cb20c4a83610562de |
Close
Hashes for fast_crossing-0.0.8-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 61652768ef0e2614414000e5089deefe6de6ffe1a2e64d77f088cbcdd6d5b28c |
|
MD5 | 80cfb5b824b58f32f3bf7b7e9c3c6dae |
|
BLAKE2b-256 | bc6e76ae7edc3cc30a5eeda679b0cb2950899b7a8d87f87143bdb9f4aa824f46 |
Close
Hashes for fast_crossing-0.0.8-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bd980e2ceb49d9d1629093352271a31584a84415bd7c15039aa0818b8ed2cb33 |
|
MD5 | 537904a97341e3f1343423d71f5d711f |
|
BLAKE2b-256 | 8d335346a960c1a3b31e9aeccda12ff5dd6033c820e054a10574e78b218f11fd |
Close
Hashes for fast_crossing-0.0.8-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2a9f701e1c4929bfcd51fe890ce661c2df4d47ee5f9441453184a92ea60eca22 |
|
MD5 | 3eaa54e18e266702626b0cbcb18407fd |
|
BLAKE2b-256 | 0f879e0243d80f544106c4040239836fe0cb347516a840ada44ad376efa02398 |