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.0-cp39-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | bc57b7bb1e2376712ce8487239015b1b55b345b91d560566820bf8bbc6b3c2d6 |
|
MD5 | 012262c3ad6b2fa39937659e2b37e03d |
|
BLAKE2b-256 | 1abbcdbfbf9e99f5b119ea3188d2570da2267d110d3e05ed9e946edec4642d38 |
Hashes for flanders-0.3.0-cp39-cp39-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 9f75cce2fccb951be67d164cc161674b232f079dd69a8b4c8013f47b15df98cc |
|
MD5 | 0a0edf57f3870a99a37e6ac851e28f85 |
|
BLAKE2b-256 | be12a74d9ad2f8c802862f9ce9d6cd78ad76f9fc21545ae8901d891e16eb03c5 |
Hashes for flanders-0.3.0-cp39-cp39-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 346e67a75e69861b7b239a420ebafc41cfdaf36788d6fc1e143dcb36923455f1 |
|
MD5 | 8725cad6d04e5fa1ff6895b0fa0907a1 |
|
BLAKE2b-256 | e09b3826d5838c1ee4ed977124ed4699da5f407c190e9675a948986bcb523e00 |
Hashes for flanders-0.3.0-cp38-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 807dfd701fde17fbc85bc0ddfad41fb84d7c206c0bbbceec94995b499bc4e569 |
|
MD5 | 29e43040e121a5fe5fccea8241091c56 |
|
BLAKE2b-256 | 7317d5dff6b152b6caf8aebb4f67ec363f2b7c61fa1db2b0a43997868e553a30 |
Hashes for flanders-0.3.0-cp38-cp38-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 07c8b331751d19db449db50eb25c5fe92e58090bfcf1ddf1787f2392bfa03595 |
|
MD5 | d990c30bed67e2b5b2d2dabdd21be8b8 |
|
BLAKE2b-256 | dbecddd024ea8c22c8e95848cfb24a5367bf79ccb5eeb5b2d3b2c8949d42fc44 |
Hashes for flanders-0.3.0-cp38-cp38-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 441a0bcc9c76635f651a6325e741f772880b5018aed5e800894bac9da6f34810 |
|
MD5 | 30ab2c042464ba7b5fe70c81d4be4e75 |
|
BLAKE2b-256 | 0ff472a582bdf22d89f6a1667807986addb7f8a003778e393eb3a910466116cd |
Hashes for flanders-0.3.0-cp37-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f652740fe36ff46f71674404543cc4c8efa473b988fd960e7ea0f0a243d8425c |
|
MD5 | c56387be90b1a6f7eb69e5988e2b5564 |
|
BLAKE2b-256 | b4199daa31826a130cfa070306402b3f35ebc1d28cee33614dd7e8c62233dbef |
Hashes for flanders-0.3.0-cp37-cp37m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 587277f16d02efbe6d5bd2f8a601d2d3e58c5c9184256d9ef4ed57d8b9885053 |
|
MD5 | ad7671802ac961ce268466ab01a7d29c |
|
BLAKE2b-256 | cdae9ecf2aa4c5b9b817818cfcb4b0eb29ff0f4401108bd1c9f79edac43d02b3 |
Hashes for flanders-0.3.0-cp37-cp37m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 92f2d590eba9d94b8d9b307633a0b517412d2e1476ba4c7e02bfbcb8316e3c00 |
|
MD5 | c1d7c4931c3f54a8667ec3eb25ff3b14 |
|
BLAKE2b-256 | 4795371e26da5d9d417ff44b101abf15e941d6f73141532d7cb2e4d270208e49 |
Hashes for flanders-0.3.0-cp36-none-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 3e77c695ac7272e90667e6ca03d835611c94c1c54b986ca4fab025296083b552 |
|
MD5 | 4174d507d4dcaacd69fbd5b6b60e8936 |
|
BLAKE2b-256 | cbb30fb154ce043a3c9ff5aa974092b4457a878f4a521e2277919fb01fdf3dfe |
Hashes for flanders-0.3.0-cp36-cp36m-manylinux2010_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8e4381666f6d6df895511cc5bfb7633b8982da00b8859fe6b01805c4b73cd776 |
|
MD5 | 9be2f76148111a0d0a992460ebfa764b |
|
BLAKE2b-256 | c4bf7f5012af465a6afd93e59347ef6a1253c7d37a709a4fb7ac549a8d3a9639 |
Hashes for flanders-0.3.0-cp36-cp36m-macosx_10_7_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 417d311c13b92ce86ef68338ef6bd02767f14d4996292c6b1ec74fad6f851246 |
|
MD5 | c239e0cabb906c067b9294a5b42711a1 |
|
BLAKE2b-256 | f7efd8b10f8c1b73ba771ce6c2c283f0db9f94c56c08f19d455f0b70bdde85bc |