{ "info": { "author": "Radovan Bast", "author_email": "radovan.bast@uit.no", "bugtrack_url": null, "classifiers": [ "Development Status :: 3 - Alpha", "Intended Audience :: Science/Research", "Programming Language :: Python :: 2.7", "Programming Language :: Python :: 3.6" ], "description": ".. image:: https://travis-ci.org/bast/flanders.svg?branch=master\n :target: https://travis-ci.org/bast/flanders/builds\n.. image:: https://img.shields.io/badge/license-%20MPL--v2.0-blue.svg\n :target: ../master/LICENSE\n\n\nFlanders: Fast 2D nearest neighbor search with an angle\n=======================================================\n\n::\n\n `.-:://////:-.`\n `-/oyhddddmmddddddNmdmdhs/`\n -ohddddddddddddNddddddNddddmmds.\n `hmmmmmdddddddddddNddddmmddddmmddm.\n `hddddddmmddddddhyyysoossyhdmNmdddNs\n sddddddddmmho/:-------------:odmmmmo\n :mddddddddd+-------------------:hddd.\n dddddddddm+---------------------:ms.\n :mddddddddd-----------------------s/`\n yddddddddds------------------------:s\n `mddddddddm+-----://////+/:---://////y`\n -Nddddddddm/----+:` `./+-+-` `.+:\n /mddddddddN:---o` -d- -. o-\n omddddddddN////y -d/ `m. y+ +:\n sdddhhNmmmN+/::o: `-` `+so++//:. `:+`\n `---. ydd+::mdddm:----/+-.````-:+:------:+s/-\n o/::/+- sN:-oomdddm+------://+///:---------:s\n `.-.` s-----+/` oN:---smddds------------:+oyhhysssydhs:.\n -o/://+-`.o:----/o` /mh:---hyyy/----------+hdmmmmdddddmmmddho.\n /+-----:+/-o:----:+` `.. .mddyyydo-----:///::ohdmmdmmdmddNdmmdmmddd/\n :+/-----:+/y-----:+-` .:+///+. dddddddd----:mMMNNddddddmddmdddmmdmddmdddm:\n ``-/+:----::-------:/+++:----/+ +mdddddN----:MMMMMNmmmmmmmdddddddhhhhhys+/.\n .////+//+o:--------------/-----/o` sdddddm/----oNmdmNNNNMMMm//os--...``\n y:-----:/+o------------------:o: :ydddm+-----:oyyyysydMMm:::o+.\n :o/:----------------+o:-----:s` .::+o--------://++oooo+:--:s\n -:/+/:--------------s/----s. -o------------------:/o+.\n `-/+o------------/---+d- `+o------------------::h\n .s/---------:::ohhhs y.-++:-----------------d:`\n dhys+///+oyhhhhyhm/ `s````:/++o+//:::://+++/-.s.\n /dddhhhhhhyyhhhddhym` -s`````````..-:::/h/s-````.s`\n :dyyhddddddddddhyyyym `ydy-`````````````s:.-o/````sy/-`\n yyyyyyyyyyyyyyyyyyyhs `./+ooymhyhy/.`````````:o....++``:dmdhhhso:`\n dyyyyyyyyyyyyyyyyyym:`-/oyddhyyyyhddyyhhs+-``````hso++ohd++dyyddyyyyhhyo/`\n myyyyyyyyyyyyyyyyyyNhhhyyyyyyyyyyyyddyyyyyhdyso++ddhmhmddhhyyyyddyyyyyyyhdy+.\n\n\nInstallation using pip\n----------------------\n\n.. code:: shell\n\n $ pip install flanders\n\n\nExample\n-------\n\nIn this example we have 6 points (numbered 0 to 5) and two reference\npoints with a certain view vector and view angle. The first reference\npoint finds point 2. The second reference point does not find any\nneighbor within the view angle and returns -1.\n\n.. image:: https://github.com/bast/flanders/raw/master/example/flanders.png\n :width: 300 px\n\n.. code:: python\n\n import flanders\n\n 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)]\n\n num_points = len(points)\n\n context = flanders.new_context(num_points=num_points,\n points=points)\n\n indices = flanders.search_neighbors(context=context,\n coordinates=[(119.2, 59.7), (155.2, 30.2)],\n view_vectors=[(0.0, 1.0), (-1.0, -1.0)],\n angles_deg=[90.0, 90.0])\n\n assert indices == [2, -1]\n\n flanders.free_context(context)\n\nIf you leave out the view vectors and angles, the code will search for\nthe nearest neighbor without taking any angles into account:\n\n.. code:: python\n\n indices = flanders.search_neighbors(context=context,\n coordinates=[(119.2, 59.7), (155.2, 30.2)])\n\n assert indices == [5, 5]\n\nInstead of searching nearest neighbors of coordinates, you can also\nsearch by nearest neighbors of the points by their indices:\n\n.. code:: python\n\n indices = flanders.search_neighbors(context=context,\n ref_indices=list(range(num_points)),\n view_vectors=[(1.0, 1.0) for _ in range(num_points)],\n angles_deg=[90.0 for _ in range(num_points)])\n\n assert indices == [2, -1, 1, 2, -1, 1]\n\nFor debugging you can employ the naive slow implementation:\n\n.. code:: python\n\n indices = flanders.search_neighbors(context=context,\n coordinates=[(119.2, 59.7), (155.2, 30.2)],\n view_vectors=[(0.0, 1.0), (-1.0, -1.0)],\n angles_deg=[90.0, 90.0],\n naive=True)\n\n assert indices == [2, -1]\n\n\nEfficiency considerations\n-------------------------\n\nIf you compute nearest neighbors for many points it is a good idea to\nsend in an entire batch of points instead of computing point by point.\nIf you send in an entire batch, the code will shared-memory parallelize\nthe loop over the points.\n\n\nReferences\n----------\n\n- https://en.wikipedia.org/wiki/Nearest_neighbor_search\n- https://en.wikipedia.org/wiki/K-d_tree\n- http://www.slideshare.net/awebneck/the-post-office-problem\n- http://www.cs.nyu.edu/~roweis/papers/Ahmed_msc_thesis.pdf\n- http://dl.acm.org/citation.cfm?doid=361002.361007", "description_content_type": null, "docs_url": null, "download_url": "", "downloads": { "last_day": -1, "last_month": -1, "last_week": -1 }, "home_page": "https://github.com/bast/flanders", "keywords": "", "license": "MPL-2.0", "maintainer": "", "maintainer_email": "", "name": "flanders", "package_url": "https://pypi.org/project/flanders/", "platform": "", "project_url": "https://pypi.org/project/flanders/", "project_urls": { "Homepage": "https://github.com/bast/flanders" }, "release_url": "https://pypi.org/project/flanders/0.2.0/", "requires_dist": null, "requires_python": "", "summary": "Fast 2D nearest neighbor search with an angle.", "version": "0.2.0" }, "last_serial": 3550208, "releases": { "0.2.0": [ { "comment_text": "", "digests": { "md5": "eebada4084ccf5299dc7be8b0f5361cf", "sha256": "215c941e4fb5bb75ce6c391d4921bf1fff471e7db33fe60212b7215ffd03e220" }, "downloads": -1, "filename": "flanders-0.2.0.tar.gz", "has_sig": false, "md5_digest": "eebada4084ccf5299dc7be8b0f5361cf", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 33693, "upload_time": "2018-02-04T12:36:40", "url": "https://files.pythonhosted.org/packages/6f/c0/4896db46b3ce1f32747d208049b1909a70e74994cc227779a9a4289db0d0/flanders-0.2.0.tar.gz" } ] }, "urls": [ { "comment_text": "", "digests": { "md5": "eebada4084ccf5299dc7be8b0f5361cf", "sha256": "215c941e4fb5bb75ce6c391d4921bf1fff471e7db33fe60212b7215ffd03e220" }, "downloads": -1, "filename": "flanders-0.2.0.tar.gz", "has_sig": false, "md5_digest": "eebada4084ccf5299dc7be8b0f5361cf", "packagetype": "sdist", "python_version": "source", "requires_python": null, "size": 33693, "upload_time": "2018-02-04T12:36:40", "url": "https://files.pythonhosted.org/packages/6f/c0/4896db46b3ce1f32747d208049b1909a70e74994cc227779a9a4289db0d0/flanders-0.2.0.tar.gz" } ] }