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.6.tar.gz
(3.2 MB
view hashes)
Built Distributions
Close
Hashes for fast_crossing-0.0.6-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 56fd3d2194f48177644af71da581f670e00bd1d546d284b21205bc7ff0f04815 |
|
MD5 | 17493ec946c54effad33d4748a2284a8 |
|
BLAKE2b-256 | ddd1905b8c80edf4837ec3d0a7f28173eedf2b1ddad090bbd6c9a3bdfab4ef29 |
Close
Hashes for fast_crossing-0.0.6-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f3b986e7def282c9a7e4ce8075f2f85c531be62837be42a71ee2ce073747d4fe |
|
MD5 | b5c96aa4ba4b381ebe3d66779c44a697 |
|
BLAKE2b-256 | 8f296cb03cbce5b2f5865a4ce8f9e02ba7951ede4696bdf54f248c5ca5925976 |
Close
Hashes for fast_crossing-0.0.6-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fce530021107f17a789bb044fb7c39ef48cf8d4d5f573432c71c32f9ccaeecec |
|
MD5 | 0f73a8fbfa9be4977b1ec1fbe9ede892 |
|
BLAKE2b-256 | cb4dcbd944d4d3a552ced94b06b368f83f6a1bef1df3b7d43cc3bc80407cf70d |
Close
Hashes for fast_crossing-0.0.6-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc75988a9eb73ef2b4287a6422f91225015cf97ee0a501d1ff40a32fff85ee6d |
|
MD5 | 51924cac145447ff6cdcad67cac24233 |
|
BLAKE2b-256 | 0739306540d759a8665ed8a2b0b4de521147ef973238e431a9b4a46644b078bb |
Close
Hashes for fast_crossing-0.0.6-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 0f0e8880f3753d287b8f85b28b5da16f8b113225731c2062b9b69300b50f78d0 |
|
MD5 | 91d61739cbb956d15a6f0610e6d71bbc |
|
BLAKE2b-256 | 685e69e05bb6b44ac76520bad0dd33ca1c6384d720046d7ae03e76cf2119b284 |
Close
Hashes for fast_crossing-0.0.6-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 41f4e7d368f1e15d08002845569d4c9abd785d759fd8a501ff08b089dfcc7ac6 |
|
MD5 | 35f4766b86dd7769e999477d310f2fd6 |
|
BLAKE2b-256 | cbd330fea0f3b25c5d49108f1a5071ab578a71348db3738028596bb571d89bb3 |
Close
Hashes for fast_crossing-0.0.6-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fa46824528d606369156bf2227826fc80de0d438c4304f99bb328362ce6cc752 |
|
MD5 | ae2aa29e39713ce1e31ae3d63d33da8e |
|
BLAKE2b-256 | d9f800848a152cb696167f88b72e470430259b7514dc6a04e7c30c4533eedb01 |
Close
Hashes for fast_crossing-0.0.6-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 522a337109ec7c290ee844a201422f1cff152645de6824a07581f627c56e4328 |
|
MD5 | c28e7c1915d366e32bd162a0c6c97a83 |
|
BLAKE2b-256 | 98083d23d92cbe5d2709ce91d12f93772c46ce63fc13e40f0b49f08ff5195bc2 |
Close
Hashes for fast_crossing-0.0.6-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 40fdbefc779017a558ab3e27df4725a8ae5ae234bb72635ff86110d0621c1052 |
|
MD5 | cdc2b31874dedee5b26c25041df00403 |
|
BLAKE2b-256 | 128efd7f357341e2faea5921ae83ce943390feb0b0fbf5f60aee8d5b5e1fb4e8 |
Close
Hashes for fast_crossing-0.0.6-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 965493c0bd10145e937859ffbd34590c8b3fad9ea21e2a31aa13d141946abe27 |
|
MD5 | 6ef947762e5dfd3185bd8b5f70c35582 |
|
BLAKE2b-256 | 883bf5fd451e1063e7a56d31cd18f8fa50532985654f0b83716f1d3aac315020 |
Close
Hashes for fast_crossing-0.0.6-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c9e1082e68cdfcdc47ed449ee9ebe6c66891f5f059e7233d3a510fcc73e75d2b |
|
MD5 | eb0b1458b1124f087cbefaf848b47a2b |
|
BLAKE2b-256 | f1a32bee1a62324a08ffed20974a3700264283b693df7545f97adc3b6ece3ab5 |
Close
Hashes for fast_crossing-0.0.6-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ec1736695aa794c7bbd9d6cb86267f404180713c4452df6c5088335dfafb6fcb |
|
MD5 | 75b0e2421df9d712cfc1237b0aeb4a9a |
|
BLAKE2b-256 | 01c185f160a364cc29f71c3e2a61f99cfe08449c884321ea586e91433b960796 |
Close
Hashes for fast_crossing-0.0.6-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e1cd8b9747d28caa159290d92e988f9283030c4df64c2c16814895a374221870 |
|
MD5 | 6053f07c55ea9ed6b2d71b1ed29166db |
|
BLAKE2b-256 | 559ac07bec891e3d7baca3460b9a69ca9f6a0ae14945ff116aa3d7e2181ea7fd |
Close
Hashes for fast_crossing-0.0.6-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f300d4d9e930edaf45b798b33172c4f1c9c261795659200131bd31371ed751a7 |
|
MD5 | 7886395730fe83cb40e112cb5c80a669 |
|
BLAKE2b-256 | 0367e46ec319b6dc00422fe77154c0736b902012a4b44105e4ee5d48aedaa4f6 |
Close
Hashes for fast_crossing-0.0.6-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 304cec5df51d5aeb164b634a73f222a027ec4333fd23ae15c6da7b878901bbbc |
|
MD5 | 3481d135e4b8e598e054c9c690824017 |
|
BLAKE2b-256 | 1ca06839e8a1e3a94b12e0d17317f0b7a28ea15fc544e8437c5c2652c4818a2a |
Close
Hashes for fast_crossing-0.0.6-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f7f597ac2e965e665c14afeccc656d96879b64f4f2a823e5daf03cb1729d761f |
|
MD5 | 7fc1d94a2abe14eee84759087602905c |
|
BLAKE2b-256 | b93b54cdb09d26939e7c52b613aca123b68d63685a604ecbb2b6921f40a95874 |
Close
Hashes for fast_crossing-0.0.6-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 83e48dc4f68b713448da9e547379b43e2860d2c1dd503175ce5e6f62d64720f9 |
|
MD5 | 8c1f5bc29c734f9c1f1b3db1a60aadfb |
|
BLAKE2b-256 | 6633ba253adc06f5e664bf5edf4e8a947d620ab0e54ecfb69cc2337e92ad8cb7 |
Close
Hashes for fast_crossing-0.0.6-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e7e702c84bb73d5f5018377ac36294d18cc7436bf6e9adc01f0c231660989633 |
|
MD5 | d10e7a0f600b0a17b5e2bb71a6f9a12f |
|
BLAKE2b-256 | d4921f0dd102bcf4e5f82fc88fe9defdc6ad370e4b194cca1db938300dd9d9c3 |
Close
Hashes for fast_crossing-0.0.6-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fad8231b734fb8a39814df9fcdbba650d6454de136629e55bf78cb17763259fb |
|
MD5 | 0afbd6dac18cb04d2c3b7f1b2f43e6be |
|
BLAKE2b-256 | a0767ca5aede1a53e9abe35c049b847f416c63220ab76cb8473c88415f961861 |
Close
Hashes for fast_crossing-0.0.6-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6f7e1792d588b4e0765a37997bb3133856d5345fb7b1ca3cf46de501588b359b |
|
MD5 | f1019afb243b24ba8d762b30cb1e6f49 |
|
BLAKE2b-256 | 7afbc738d34bd57455e54b0fc3145f4ea250f8fe76509f79e73fa480aea776e1 |
Close
Hashes for fast_crossing-0.0.6-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | b8871e1bdcfb0ceddf87a5008bf3ea0977fbefa66257696c866151472fa45a11 |
|
MD5 | e3ecd01c9e4082089227b7aa730fffde |
|
BLAKE2b-256 | 84837f5548769e3913ca09a95ddee2f6d037efc6c4a8742e51f4eae6435e4a37 |
Close
Hashes for fast_crossing-0.0.6-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | dc0bb751b3da818fb6682b4f4957475a728b7c1c364f878c079e3e2892809c36 |
|
MD5 | 589ab0d66d93e0e5d54a049a5111d8f4 |
|
BLAKE2b-256 | 92c0ce04d79c6963e5bc4c0349702f2f7ebc195ed8eb0020dc69bd6c8ee32654 |
Close
Hashes for fast_crossing-0.0.6-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7b71c4e11757eb72ec344ac6980f6537b24be7c6751f110b2b08bcdb23385060 |
|
MD5 | a8b33e170b4883bee385d73539132aa7 |
|
BLAKE2b-256 | 2deb94e77c10b7d9e01f0289fd49cfbc50ee749d616ffb509afd229fe296c085 |
Close
Hashes for fast_crossing-0.0.6-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e44c15c18d2d9161214d0f477cd83c472c6fc9d97c1ee7da318b9095b6afa1d0 |
|
MD5 | 378b0e8f053cb0a05765a5b480904cdf |
|
BLAKE2b-256 | 7a01853da9877b291614aca863c462e930c1a755685ba5a05a46e1e56850b9c4 |
Close
Hashes for fast_crossing-0.0.6-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a56bbb5d59d7589134046c5a9f1f0286549d336e8383415309276135658f685f |
|
MD5 | cca6e248c19e6d79c5ff873571c5f3b5 |
|
BLAKE2b-256 | a5a6633a2eacc6f89ca1eaecce5cce5a4b217611d8942eaf0bd7f5190708f1d3 |
Close
Hashes for fast_crossing-0.0.6-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 731b15665b8e1479f772ad68fbb39a223cc76cc1e94f445ac68f9bc619ecc8ad |
|
MD5 | 35f02d889302be244e37f41b8855435b |
|
BLAKE2b-256 | 7c6764cd1fb35728cd7c1ad8cd891648dc39ecec0c158253fe044067accc16ea |
Close
Hashes for fast_crossing-0.0.6-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 73e11a9ff6ecb6cee2537f9c7f4a40b8193b5b9f470b4ca09d34b1979410db30 |
|
MD5 | 4f0eb7ef0d6ddc964b8a6d66973d5a05 |
|
BLAKE2b-256 | b2a528cf4a3738e603426d7d7adf5406a778aff366b3b4ceb456347cadb838ca |
Close
Hashes for fast_crossing-0.0.6-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c46add4c01c47e6983334e4222d7454f7aec5074c0d6bfd48be3be55cade253 |
|
MD5 | 33f9c852173014d68ff3b2d891f86fb4 |
|
BLAKE2b-256 | 8565bd79373cbfa6022a0a9580a56ec278211262eb79869384571bef579d1e35 |