1
aheadlead 2017-09-04 19:30:19 +08:00
什么叫“基础点”
|
2
xiang578 2017-09-04 19:31:41 +08:00 via iPhone
不知道是不是 kd tree
|
3
GreatHumorist 2017-09-04 19:32:24 +08:00 via iPhone
向量计算公式?
|
4
Valyrian 2017-09-04 19:39:24 +08:00 via iPad 1
|
5
jlsk OP |
6
blahgeek 2017-09-04 21:12:21 +08:00 via iPhone
|
7
lsmgeb89 2017-09-04 22:40:47 +08:00
这种算计算几何领域的算法?
|
9
yangff 2017-09-04 22:59:06 +08:00
具体你可以看 voronoi 图的扫描线构造方法,反正你是一次性的。
|
10
ryd994 2017-09-04 23:31:11 +08:00 via Android
这也叫难?你想想手机基站的工作范围就可以想通了
剩下的是怎么把想法转化为算法 |
11
jedihy 2017-09-05 02:49:23 +08:00
google onsite 题,转换为极座标之后二分搜索
|
12
jedihy 2017-09-05 02:57:02 +08:00
@yangff 预处理不能给你这样预处理的,你这样我直接算距离初始化的时候 O(N)就全部做完了。
原题是说可以你可以选择给出的坐标的形式,然后让你找出距离最近的点。提示也很明显<O(N),那就是 O(nlogn)了。 |
15
jedihy 2017-09-05 04:48:38 +08:00
@Xs0ul 给我一点时间,去年准备 google onsite 的时候和同学讨论过,现在忘了,但思路我记得很清楚是极座标然后二分。
|
17
jlsk OP |
18
linux40 2017-09-05 07:34:23 +08:00 via Android
极坐标二分要用到极坐标下的距离公式吧。
|
19
messyidea 2017-09-05 08:17:45 +08:00
想来想去总感觉极坐标二分不了(
能想到一些杂七杂八预处理优化的办法, 但都能构造出在极端情况下退化到 O(N)的情况. 坐等正解 |
20
Valyrian 2017-09-05 08:17:51 +08:00 via iPad
@jlsk 查找是 O(log n),plane subdivision: http://www.cs.cmu.edu/afs/cs/academic/class/15456-s10/ClassNotes/kirkpatrick.pdf
|
21
helica 2017-09-05 08:31:03 +08:00 via iPhone
量化后,线段树乱搞吧
|
23
yangff 2017-09-05 09:59:36 +08:00
hmm …… 如果你的 px, py 不是预先给出的话,查询是 logn 的
至于你可以用的各种算法你可以参考一下这本书…… 计算几何--算法与应用(第三版) |
24
GtDzx 2017-09-05 10:11:35 +08:00
话说 google onsite 出这题的话是想听到什么回答呢?
我如果说我知道可以用 voronoi 图搞,但是具体怎么搞不会。是不是直接就跪了 -_-!! 要不然是可以先假设基础点分布比较随机,扯一扯 kd-tree/geohash 以及 google s2 库的实现? |
25
northisland 2017-09-05 10:21:53 +08:00
图片搜索 CBIR,或者图片配准中,的最基础问题了。
属于暴力搜索的近似问题, 现在最流行 Optimized Product Quantization 和 Product Quantization Tree。之前的 FLANN ( kd-Trees 和 K-Mean Trees 结合)也很经典。 https://github.com/yahoo/lopq https://github.com/cgtuebingen/Product-Quantization-Tree 那都是高维数据的玩法,这就是二维。 |
26
1djmao 2017-09-05 10:38:15 +08:00
|
27
rashawn 2017-09-05 11:30:24 +08:00 via iPhone
预处理是啥意思…
|
28
zagreb 2017-09-05 12:12:37 +08:00 via iPhone
前几天不是有人发帖问“已知调色板中 N 个基本颜色,求任意颜色在调色板中最接近的颜色?”么。一个二位空间,一个 rgb 色彩空间。
|
29
artandlol 2017-10-26 20:45:06 +08:00 via Android
傻比
|