圈图的geo query处理解决方案

圈图的geo query处理解决方案

一般的geo query是在一个点找附近多少米，几公里的poi点，现在有个产品可以在地图上圈一块地方找其中的poi点,“一块”其实是用户鼠标或触屏经过的点组成的多边形(可凹可凸）。目前的做法是找出x,y的最大最小四个坐标，这样构成一个矩形，但矩形不方便直接拿geo hash的grids, 所以取最长边，放大成一个矩形，再取它占用的grids，这样几个termquery最后再加个过滤操作。

感觉上做法比较简单，可能在某些情况下性能不高，所以无事yy了一下:

1) poi点不稀疏即最小格子内平均都有较多poi时，可以用多边形填充算法把每个格子取出来，这样比较精确，甚至可以标出哪些是边界块，只对边界块内的点做过滤操作。

2)poi点较稀疏时，考虑类似原来做法，只不过这里更细一点。原来做法对于长宽比例相差较大的比较浪费,可以把矩形切割成多个正方形(边是长宽中较短的那个) ，这样就解决了这个问题。

再细一点，如果用户画了一个三角形，只要它没有一条边是水平或垂直的，那么它的实际面积会小于矩形面积的一半，并且没有边界，这时我们需要对三角形用水平线或垂直线进行切割，切割之后仍会剩下一个三角形仍需要切割，一直切割直到这个三角形小于一个格子。这样就可以保证最后拿到的矩形面积是原来三角形的两倍，问题有边界。

最后用户画的多边形不管几条边，凹或凸都可以从顶点做三角切分，最后多边形整出来的多个矩形可以保证面积之和小于要划定的多边形的两倍。

总结一下，感觉上2)的做法还是挺繁琐的，其实边界不如1的做法好，很可能复杂度也和1是一样的（或者很多时候会退化)。