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.5.tar.gz
(3.2 MB
view hashes)
Built Distributions
Close
Hashes for fast_crossing-0.0.5-cp311-cp311-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 232d5c5b17df1bda96e313709e6307b723a3014991388d1c354a5e1dedd19643 |
|
MD5 | 409f2a8860f4c29333e2b43ca7fa38e4 |
|
BLAKE2b-256 | 397b79eefd480a3fcfba25c1d3b110a7b73954a25738d8eea4c14d61ae7a1a08 |
Close
Hashes for fast_crossing-0.0.5-cp311-cp311-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 67c98e2c4585de51b93a31f09aeb601093b382e53ed214c1e9f20b8e41283dab |
|
MD5 | e64eac75549f225252daba6f96c0e6dc |
|
BLAKE2b-256 | 1587c393b8a8e560ba2cbd83c367e882e56425fd92b49eb3109aa855a27fea24 |
Close
Hashes for fast_crossing-0.0.5-cp311-cp311-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | fd393b45b704c0a9ff1b7f44aaa1998aad5765e4f98b0cb09911f1d7a031197a |
|
MD5 | 2866e9a7685fd1662660081f4ca1a1a3 |
|
BLAKE2b-256 | e87e96d01834b10440d99068079cfc67b3de426708a690bdb611b3ed50a85195 |
Close
Hashes for fast_crossing-0.0.5-cp311-cp311-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e330d586c5c23a576454c3b9e80017c0b269c088d66f8a8a6e01f28dd447d28 |
|
MD5 | 215fe7d4b37f626e397d2b9f28082891 |
|
BLAKE2b-256 | 995012df1b81874ad23a030d46866105da24580881c06894ee9170b49fb4df4c |
Close
Hashes for fast_crossing-0.0.5-cp311-cp311-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a3957c4a32e991163649724fba0fa50b9a02f1a4618db6145452b94e967c0b7c |
|
MD5 | 8db4bfefe4faa65d60f42cba91a03c60 |
|
BLAKE2b-256 | b95a03a522065d66d72e4c9005523279d696da30bea9e8a9ace74dd2c8e314c0 |
Close
Hashes for fast_crossing-0.0.5-cp310-cp310-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e9f5a9e31f7103abc4dfe10da20e1ffb5fd595ce29cf6b974320450fa20273a |
|
MD5 | 02c11d0afcea6b904aabe45fd4a947cf |
|
BLAKE2b-256 | 26ef7c95abacb7c57404dc96431b518597702c0994f42cadfcacf816361bad77 |
Close
Hashes for fast_crossing-0.0.5-cp310-cp310-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c2d70277dcf68da663afdbe064c4c0c6e6ab4b18cd9baa9a83d568974d87c26 |
|
MD5 | e9574134f9a2692eb0b5ad1031243c68 |
|
BLAKE2b-256 | 604b3190e043159700b7c43698346e21f5327a204c8aeaf1ec385b528fec3dfc |
Close
Hashes for fast_crossing-0.0.5-cp310-cp310-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 262531bc8d1e2c09e5551b0f84848703262a2f927358ffc89575a0871cab5391 |
|
MD5 | b65e46883c930b0e9753507608621114 |
|
BLAKE2b-256 | 7588fab87d64d2381faf7685766d30293bce87f6bbaa5e4edce5a54cde363e62 |
Close
Hashes for fast_crossing-0.0.5-cp310-cp310-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6c6fb642732a3801f7ea88fe3572953d82401dfc3c513ef42800e06a8e9cb911 |
|
MD5 | 46dc6998b07240509425b9f66048d3b0 |
|
BLAKE2b-256 | 7ff15a60c7e2a88a1e471dd01975312117a716873df05dceb9077950f04bbbb0 |
Close
Hashes for fast_crossing-0.0.5-cp310-cp310-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 948b3773af3ec41fff0ee8778cefbe7726e90acfa48110b9fa4d52137eb414de |
|
MD5 | 78de312631225fb74d9849cc4caa3cae |
|
BLAKE2b-256 | d687a391a480c9a548f09bb8abebd1b46fb4a87419d33d60e914ace52e62355f |
Close
Hashes for fast_crossing-0.0.5-cp39-cp39-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 25b08f135de7cca9a114b9bf279c3069498b552e1e144e6ede7bf0579168ae71 |
|
MD5 | b39f488a1bf5a85cbde7460fae2af52c |
|
BLAKE2b-256 | abba610244c7d4910450c4d72249a36ff4470551144b645dd23158e6aa99e64d |
Close
Hashes for fast_crossing-0.0.5-cp39-cp39-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 2d1fbac5a1ca1877d62bdb9e406a931abded32342370cbae11f34690699004a5 |
|
MD5 | 14216262c1acca40ead47be245f5b1aa |
|
BLAKE2b-256 | 1479ee0d1e7c6d22a79caf237ad278ce4c3bd1cc5e6fe4781dbb150a4f5a85e0 |
Close
Hashes for fast_crossing-0.0.5-cp39-cp39-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 51ccf018d04a16d2ef42808ffc09f722d1f08c94f3ebcfcf5ae9695c183d6b60 |
|
MD5 | 34bbd5058324d0fd2a8ab92aedca163a |
|
BLAKE2b-256 | 38b3a97e51351c64c08b52ed2351088ac2851eecc58a230e6b228f84c69397be |
Close
Hashes for fast_crossing-0.0.5-cp39-cp39-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9713e221dc4dcb5b23e460c554963ad320327915c9d712e30181f3f02fb969f6 |
|
MD5 | 2ed1e961740a423993c05bde0b5788d5 |
|
BLAKE2b-256 | 4a47b908ac5409904118eefad3fdbd389b79799baf61f9ab7d8a1a859895721d |
Close
Hashes for fast_crossing-0.0.5-cp39-cp39-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6419e431e93c372839600307254ea0fd955d5ed08e9536877db8290892ec23e9 |
|
MD5 | ba84d553eaadb63448ba678ccb7854f0 |
|
BLAKE2b-256 | 8fe59c01f0fad2f151d47b44019ec9981a3cc2b211014f91b8173bc091b6a35f |
Close
Hashes for fast_crossing-0.0.5-cp38-cp38-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 796226af408d0be0e03f77ddfbb50e148f50f6501a3d3b6604206c5f70c9ee4c |
|
MD5 | 5c95ddd5ac50362d23a0ddd85ed7ef6f |
|
BLAKE2b-256 | 776c86aa4da1904ecc2e77400fbb8b76407f5034c64ab511042216a9af2d064f |
Close
Hashes for fast_crossing-0.0.5-cp38-cp38-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 75383a18f1d628426231dcf48bd5847f082c767ab5c23c29ef38e779bba607a5 |
|
MD5 | d530d882d839faa9dc82ffdb3eb92a72 |
|
BLAKE2b-256 | cc807ea84e191b0224b1bdfef4b704bbef3dd997f3c4d34cabac9bc735409f06 |
Close
Hashes for fast_crossing-0.0.5-cp38-cp38-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c4c396616f0e5854801e9cf4e4d915e96b8c28c127e34ca44301fa80a1a21b7c |
|
MD5 | 7db3ed7caa2b5659e633fe66840a67cb |
|
BLAKE2b-256 | 4fa20af4248621a1e8a49ad8dbc8a1d09685974792e1b84a2a49406c1e0d798e |
Close
Hashes for fast_crossing-0.0.5-cp38-cp38-macosx_11_0_arm64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8d32a349b0da4f4aa4b8f4e98d50d9ec685f682fe3748a1d41e90658decccf20 |
|
MD5 | 377d733bbe94623ac4c7b7bd3180037c |
|
BLAKE2b-256 | 1cee080241c5210460858a979967fd0601222093a0a5e5203a3f56dbded4fa59 |
Close
Hashes for fast_crossing-0.0.5-cp38-cp38-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1108d0d85c7226c5ec0840e10637ec210168ff802d2561a44257dbe26906c192 |
|
MD5 | c4dc4121f3c6c0e720296e50fb1bc1e0 |
|
BLAKE2b-256 | 6ab2026d03c8ab28628269605f0f708c867d2b8a57d4a8087ef5aed767881d0d |
Close
Hashes for fast_crossing-0.0.5-cp37-cp37m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c0ded45fe547e52735cd8deb233b11644890952d26916366c1461c1ba7923117 |
|
MD5 | 65f162a6ac89dfdcad60efc475c3ca70 |
|
BLAKE2b-256 | 397c80108081cc4dcc6d7caf06f8d7c93997c287165aa9364fe1d801748f5575 |
Close
Hashes for fast_crossing-0.0.5-cp37-cp37m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f020bb61f227d605d2f34de400aa5c2861fa903c5de129ab1ad8b6a7415d37f4 |
|
MD5 | ce1a99b1369fdf667c9213de0fa42447 |
|
BLAKE2b-256 | bbd30ce1d9c76255898a8e8ff68bf109ec2de51172868c63c61af7520bcb694d |
Close
Hashes for fast_crossing-0.0.5-cp37-cp37m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | a48f4a3d3f55fa17c9cbd4386dd9887d78542e91fa4740445b5b3fe0bec4c599 |
|
MD5 | b3fae13740639e511aadb2cad9293cc9 |
|
BLAKE2b-256 | 676ec9ac35539d583c6dcbf3cd7bb9b48cfdc8f3eb4fe509bf4cc4c8e3abe153 |
Close
Hashes for fast_crossing-0.0.5-cp37-cp37m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 96c9ed2f97cc65293778d12f52f29498289cc557afec5e85e0636c0f42a60d96 |
|
MD5 | e72dbc0f6325178907959d9f6ba89897 |
|
BLAKE2b-256 | 85b90a0b3a6c743fd15aeeab4489855054dc92afa2f9a7933bcee3ff9a59e5b1 |
Close
Hashes for fast_crossing-0.0.5-cp36-cp36m-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 84889a9ee36cef6395944d79f438df798d5af67edcc4143bd066687854b75d85 |
|
MD5 | 15a56f8be3a24a3373f50679e024b4e7 |
|
BLAKE2b-256 | b4f5b8fa4505eda37a472d011cf7d4f8685e4f75379d877aa8972d52be7b6492 |
Close
Hashes for fast_crossing-0.0.5-cp36-cp36m-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f74ffff28ae5df58701f2b0d3365dd1d451ce0e22523fedb2f547e181c0667af |
|
MD5 | 2aad082e73e74bf8fe301a57db697307 |
|
BLAKE2b-256 | eb50563d3e322f9df660e8f2413a854ff275e71e029a40cec9a550c8bd2c706b |
Close
Hashes for fast_crossing-0.0.5-cp36-cp36m-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 49163e88f4923c87853e1a07d3ef2f47d36d8ccbdd11955750bb673598e361ff |
|
MD5 | 207f5a14d0b55554a094f5e058366cc3 |
|
BLAKE2b-256 | f83d8366dad627dd88af9c3cf635719a519238aaff3ca5a985f10407cca2ce05 |
Close
Hashes for fast_crossing-0.0.5-cp36-cp36m-macosx_10_9_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | c4aa18bab7d838f03ad8c42025ff7f7f4eddd29311569993a0e38e6ed2c918b7 |
|
MD5 | b1c34c0a92a1a97c01aa1f3ed3130292 |
|
BLAKE2b-256 | 7b539d178080120cc6b60c572b68d59ee2f1e3dc5855982205a9ef3ce831e57a |