# Tag Info

25

I see MerseyViking has recommended a quadtree. I was going to suggest the same thing and in order to explain it, here's the code and an example. The code is written in R but ought to port easily to, say, Python. The idea is remarkably simple: split the points approximately in half in the x-direction, then recursively split the two halves along the y-...

6

See if this algorithm gives enough anonymity for your data sample: start with a regular grid if polygon has less than threshold, merge with neighbor alternating (E, S, W, N) spiraling clockwise. if polygon has less than threshold, go to 2, else go to next polygon For example, if the minimum threshold is 3:

5

Similarly to Paulo's interesting solution, how about using a quad tree subdivision algorithm? Set the depth you would like the quadtree to go to. You could also have a minimum or maximum number of points per cell so some nodes would be deeper/smaller than others. Subdivide your world, discarding empty nodes. Rinse and repeat until the criteria are met.

5

I am not a Java developer and don't know of any existing Java implementations for this, but using the k-Nearest Neighbors algorithm with a k-d tree will likely give much better performance. However, if accuracy is important, you will need to implement the Haversine (spherical) or Vincenty (ellipsoidal) distance formulae for the distance metric, since ...

3

TL;DR; Don't bother, PostGIS is your friend and will be way faster than storing in memory and searching. I did some tests with random bounding boxes on a relatively sparse data set (Electricity Transmission Lines in Great Britain) and got the following headline figures: Memory Time: 121.0 time, 0.0121 average for 10000 queries Indexed Time: 108.0 time, 0....

3

What you're trying to do doesn't really make sense. Quadtree.query works by intersecting the extents of the elements with a rectangular extent. It's up to you to further filter them. However, you can use the overloaded version of query with a subclass of ItemVisitor to achieve what you want. public class QtreeTest { public static class HoleVisitor ...

2

There are several benefits to geohash over quadkey: cross language support. geohash has open source implementations in a number of languages (c, java, python, ruby, perl, javascript). If you need external contributors to connect with your quadtree based data, you gain maximum flexibility with geohash. If you are using python, there is a pre-built c-...

2

from functools import reduce # required in Python 3 def quad_to_xy(quadtree_coordinate): return [reduce(lambda result, bit: (result << 1) | bit, bits, 0) for bits in zip(*(reversed(divmod(digit, 2)) for digit in (int(c) for c in str(quadtree_coordinate))))] or somewhat more readable: from functools import reduce # required ...

1

Not used it myself (not used Java for ages) but Java Topology Suite should be worth looking into. I'm not sure what you'd use for the database connectivity, but this library should cover the spatial indexing and operations side of things. The C++ port of JTS is GEOS (which is what QGIS uses for a lot of its geometry work), but some other Java based GIS ...

1

There is a PyPI package available for this problem. pip install pyGeoTile From the Github project: https://github.com/geometalab/pyGeoTile Usage: from pygeotile.tile import Tile Tile.from_quad_tree('203').google # (1, 5)

1

ol.Map.forEachFeatureAtPixel() actually already uses a R-Tree to speed up the search. But it is a bit more complicated. Intersecting the mouse-position with the features' geometry does not necessarily bring the result you would expect, because the styling of the features is totally ignored. E.g. if you click on a feature's icon, you would expect to select ...

1

I asked the question a little differently in another post and my question was answered completely although I'm still unable to access the url in question. For anyone else that may need to know I'm posting the link here and marking this question as answered. Further to this, the code in the answer is below: // quadkey function var quadkey = function (x, y, ...

1

Another approach is to create a very fine grid, and use the max-p algorithm. http://pysal.readthedocs.org/en/v1.7/library/region/maxp.html

Only top voted, non community-wiki answers of a minimum length are eligible