No project description provided
Project description
Flanders: Fast 2D nearest neighbor search with an angle
`.-:://////:-.`
`-/oyhddddmmddddddNmdmdhs/`
-ohddddddddddddNddddddNddddmmds.
`hmmmmmdddddddddddNddddmmddddmmddm.
`hddddddmmddddddhyyysoossyhdmNmdddNs
sddddddddmmho/:-------------:odmmmmo
:mddddddddd+-------------------:hddd.
dddddddddm+---------------------:ms.
:mddddddddd-----------------------s/`
yddddddddds------------------------:s
`mddddddddm+-----://////+/:---://////y`
-Nddddddddm/----+:` `./+-+-` `.+:
/mddddddddN:---o` -d- -. o-
omddddddddN////y -d/ `m. y+ +:
sdddhhNmmmN+/::o: `-` `+so++//:. `:+`
`---. ydd+::mdddm:----/+-.````-:+:------:+s/-
o/::/+- sN:-oomdddm+------://+///:---------:s
`.-.` s-----+/` oN:---smddds------------:+oyhhysssydhs:.
-o/://+-`.o:----/o` /mh:---hyyy/----------+hdmmmmdddddmmmddho.
/+-----:+/-o:----:+` `.. .mddyyydo-----:///::ohdmmdmmdmddNdmmdmmddd/
:+/-----:+/y-----:+-` .:+///+. dddddddd----:mMMNNddddddmddmdddmmdmddmdddm:
``-/+:----::-------:/+++:----/+ +mdddddN----:MMMMMNmmmmmmmdddddddhhhhhys+/.
.////+//+o:--------------/-----/o` sdddddm/----oNmdmNNNNMMMm//os--...``
y:-----:/+o------------------:o: :ydddm+-----:oyyyysydMMm:::o+.
:o/:----------------+o:-----:s` .::+o--------://++oooo+:--:s
-:/+/:--------------s/----s. -o------------------:/o+.
`-/+o------------/---+d- `+o------------------::h
.s/---------:::ohhhs y.-++:-----------------d:`
dhys+///+oyhhhhyhm/ `s````:/++o+//:::://+++/-.s.
/dddhhhhhhyyhhhddhym` -s`````````..-:::/h/s-````.s`
:dyyhddddddddddhyyyym `ydy-`````````````s:.-o/````sy/-`
yyyyyyyyyyyyyyyyyyyhs `./+ooymhyhy/.`````````:o....++``:dmdhhhso:`
dyyyyyyyyyyyyyyyyyym:`-/oyddhyyyyhddyyhhs+-``````hso++ohd++dyyddyyyyhhyo/`
myyyyyyyyyyyyyyyyyyNhhhyyyyyyyyyyyyddyyyyyhdyso++ddhmhmddhhyyyyddyyyyyyyhdy+.
Installation
$ pip install flanders
Example
In this example we have 6 points (numbered 0 to 5) and two observer points with a certain view vector and view angle (90 degrees). The first observer point finds point 2. The second observer point does not find any neighbor within the view angle and returns -1.
Example code:
import flanders
# as a first step we build the search tree
# we can later reuse the search tree many times
points = [
(60.4, 51.3),
(173.9, 143.8),
(132.9, 124.9),
(19.5, 108.9),
(196.5, 9.9),
(143.3, 53.3),
]
tree = flanders.build_search_tree(points)
# now we will search the indices of nearest neighbor points
# for two observer points
observer_coordinates = [(119.2, 59.7), (155.2, 30.2)]
view_vectors = [(0.0, 1.0), (-1.0, -1.0)]
view_angles_deg = [90.0, 90.0]
indices = flanders.nearest_indices_from_coordinates(
tree, observer_coordinates, view_vectors, view_angles_deg
)
assert indices == [2, -1]
# instead of using observer coordinates, also the original
# points themselves can be observers and we can select them
# by their index
observer_indices = [0, 1, 2, 3, 4, 5]
view_vectors = [(1.0, 1.0) for _ in observer_indices]
view_angles_deg = [90.0 for _ in observer_indices]
indices = flanders.nearest_indices_from_indices(
tree, observer_indices, view_vectors, view_angles_deg
)
assert indices == [5, -1, 1, 2, -1, 1]
Efficiency considerations
The above example is very small and simple but this library starts to shine once you have very many points and/or very many observers where a noddy implementation would take too long to compute.
Example timing for 1 M points and 10 k observers (on i7-10710U):
- constructing the search tree: 3.0 s
- nearest neighbor search: 9.6 s
If you compute nearest neighbors for many observers it is a good idea to send in an entire batch of observers instead of computing one by one. If you send in an entire batch, the code will shared-memory parallelize the loop over the observers.
References used during development
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distributions
Built Distributions
Hashes for flanders-0.3.1-cp310-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 90dcfd74e92d542a9b54940c77c2429046d3d4643079adc905270828a6fb4408 |
|
MD5 | 78e68f5a17611859347d4e1c19d3c0c0 |
|
BLAKE2b-256 | 8a0e1936c3ddfc7d810f68c306421481e0d782a39184f3a79ae7cdfc318111df |
Hashes for flanders-0.3.1-cp310-cp310-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 4f88c6b16fb202b07bc6d46e1d729e71404a1abff52c342f729788435cf8c189 |
|
MD5 | 29e84edd8af098f9f245e95bbdbcee6e |
|
BLAKE2b-256 | d09debf6409ed7bcdb172b0a34158e155f19c12102fa91eb46c0e2e9058c1051 |
Hashes for flanders-0.3.1-cp310-cp310-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | ce7789d19d8cb113a795f08bff1e8b9b4468617f03a36ce3cad5ffe9ca9840e9 |
|
MD5 | 421e7769fae0ae937d9c817fc802c680 |
|
BLAKE2b-256 | 6ae29ddaf0577b9b2ad12909a13ff04bc114b3f0ec0f0b8302ad037471859727 |
Hashes for flanders-0.3.1-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 5654e0c2c6dfe4189f4f6edfaff02db0188d5a5aab56835eccfc8df437695a71 |
|
MD5 | 7813b81f526419bd71a1825db5d6c231 |
|
BLAKE2b-256 | 04f0e742b7ac35718548ca89849843303cc79ba17107fea71a3ed50bbf4ac460 |
Hashes for flanders-0.3.1-cp39-cp39-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8f179530ed22901352dcb8b1d2c6a2be80b604cb6d6b299c4969156a72f4c408 |
|
MD5 | 1883bb46ad857042f616ea6c79523682 |
|
BLAKE2b-256 | 0090c6ac0f24d2074241ddac4f0e5c736da9ac2d1200ed1f5d63129ad769ade8 |
Hashes for flanders-0.3.1-cp39-cp39-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f25b453ab34ebcc1d3f5425c32307eec5bf64644c73fb7b4a120f2f8126e77fe |
|
MD5 | 65b4198c5b9327079b7c3b67e3f22534 |
|
BLAKE2b-256 | fc0cbcd3777468a335418e77cfd33fb441a0c9cf8eee933dc79f6f0f0e85d09a |
Hashes for flanders-0.3.1-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bb3a28269bd9460a57e2ec19acbebd01b5bdd96dba9a87dee3a7b8c8f1a66065 |
|
MD5 | 0c20a5956b6d31431a765603e2f1e9ad |
|
BLAKE2b-256 | 58d6d1ebd218ded804ee6a3372ccd20480b7557aca2b476f506d2d1ef8c6a379 |
Hashes for flanders-0.3.1-cp38-cp38-manylinux_2_34_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 7ed6597a77997258a3eea1a09ae541dc491555b80e95054eac1bd9f2da179c3d |
|
MD5 | 91af4f07351d81e6ab9c537e4f2b736c |
|
BLAKE2b-256 | c0913a2b86237b5e8986d92d630eadcde00064fd1f2572dcf9da3109e09235e2 |
Hashes for flanders-0.3.1-cp38-cp38-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | e329c7cadd905b1eedbc6ed9dd11a59b751e72049e713ffdc5fce392c7e1e0b2 |
|
MD5 | eaf17943d0c6c17105cd297b56de403c |
|
BLAKE2b-256 | 4a42f5a4206d3e4cbbcd48575a8c8647cd1d0b2c3bceeaf833293d1280cbb956 |