DinS Written on 2018/2/13
现在探讨一个非常迫切的问题：如何通过屏幕上的鼠标点击获得对应的场景中的node?换句话说，如何通过屏幕坐标得到对应的node?
urho3d并没有提供直接的方法，这是因为要在3D场景中做到这一点非常困难。不过既然是在2D，这个功能是能够实现的，也是必须实现的。
注：Camera类提供了屏幕坐标和世界坐标相互转换的方法，可以使用这个。下面进行深入探讨如何转化的公式化表达。
一、坐标转换的数学问题
先来看一下如何将场景坐标转成屏幕坐标。
这个比较容易，因为区别仅仅是原点的移动，以及尺度的问题，可以通过这个公式得到：
Screen.x = |Scene.x * 1/PIXEL_SIZE + Screen.width/2|
Screen.y = |Scene.y * 1/PIXEL_SIZE – Screen.height/2|
这个应该比较好理解，第一项是将场景坐标转成屏幕坐标相同尺度。第二项相当于把原点从中心移动到左上角。取绝对值是因为屏幕坐标没有负的。
可以对照例子看一下：
屏幕宽为960，高为640，PIXEL_SIZE是0.01。
场景坐标（0,0）位于屏幕中心，则Screen.x = |0 * 100 + 960/2| = 480，Screen.y = |0 * 100 – 640/2| = 320。(480,320)就是屏幕坐标的中心点。
接下来研究一下如何将屏幕坐标转换成场景坐标，原理跟上面差不多，公式如下：
Scene.x = (Screen.x – Screen.width/2)*PIXEL_SIZE
Scene.y = -(Screen.y – Screen.height/2)*PIXEL_SIZE
括号里面的实际上就是把原点移动到中心。但是注意屏幕坐标的y轴跟场景坐标是反的，所以要加-号。
对于屏幕坐标(0,0)，Scene.x = (0 – 960/2)*0.01 = -4.8，Scene.y = -(0 – 640/2)*0.01 = 3.2。
二、通过坐标查找node的算法
实现了2D场景中屏幕坐标与场景坐标的相互转换后，我们实际上只解决了问题的一半，我们真正的目的是通过屏幕坐标获取对应node。
思路是比较清晰的，2D中每一个node占据了屏幕上的一个矩形区域（仅考虑图片node），于是如果能够判定屏幕坐标位于某个node的矩形区域中，就可以找到该node。当然2D场景中还有一个layer的问题，上面的node优先级应该更高，先不考虑这个问题，仅关注区域问题。
最直接的思路是把矩形区域和node组成一个pair，然后每有一个pair就放到vector
然后给定一个屏幕坐标点，遍历vector看在哪个pair的矩形区域中，然后找到对应node。
思路直接，容易实现，不过效率是O(n)。由于这个功能需要频繁使用，O(n)的效率不能接受。
从效率来说，最好的是O(1)，也就是用unorder_map。
但是仔细一想发现不行，因为hash是精确匹配，但是我们需要的是点在某一区域内都算命中。
妥协后可以使用的是map。map因为可以比较大小所以能够做到范围内命中，同时效率是O(logn)，可以接受。
接下来的问题就是如何定义矩形区域的比较大小定义，这并不是显而易见的。个人认为采用中心点坐标+宽高的方式定义矩形最好。因为这样可以把区域比较简化为点的比较，容易理解，而且可以定义严格弱序，这样才能使用map。
但是代价是我们并不能精确确定矩形，为此核心算法就是使用两遍搜索卡出一个范围，然后遍历范围寻找确切的矩形，即效率为O(logn + r)，r为范围。
那么如何确定范围大小呢？可以使用一个delta做比较。原则是宁缺毋滥，后面单独分析。
另一个问题是如果两个矩形的中心点一样，但是不是同一个矩形怎么办？为此使用multimap来组织数据。
这么说有些抽象，看一个具体一点的例子，先简单定义一个矩形类：
（大图点这里）
逻辑很简单，比较大小定义为先x再y，可以构成严格弱序。
然后是判断点在矩形内，也很清晰。
接下来看如何实现查找，制作一个例子：
画成图如下：
运行起来可以看到排序情况：
应该呈现的是以x为key递增，如果x一样再以y为key递增。
这里故意设置了两个中心点一样的矩形，因为是multimap所以都保存下来。
接下来是查找代码，很简短：
（大图点这里）
假设click点是(1.5,1)，根据delta扩展一个范围，然后找出来的两个范围是这样的：
这里从数据结构而不是坐标系去理解可能更容易点。
x=2.5找出来的lower_bound就是x=3那个节点。
x=0.5找出来的lower_bound就是x=2那个节点，而且是第一个x=2的节点。
然后就是在筛选出来的范围里遍历找点了：
获取区域，然后判定，如果在就找到了。
现在进行算法层面的泛化理解，然后才能够确定delta指定策略。
假设有这样一个场景：
使用上述算法，所有的区域都存在一个multimap里，并且顺序大体是按从左到右，从下到上的顺序来的。
现在假设有这样一个click点，我们选择一个delta然后进行搜索，可以得到一个边界：
在边界内的pair就是候选区域，在这个例子里如下(暂时忽略高边界扩展一个)：
之后遍历每一个候选区域，确定对应的click点所在区域或者没有区域。
查询左边界和右边界需要2O(logn)=O(logn),从概率上来讲筛选出的候选者r<logn，所以我们期待效率是O(logn)。
但是这样的算法有一个重大的缺点：无法应对size相差特别大的区域。
来看下面这个例子：
那个绿色的区域是一个异质区域：与其他区域完全不同。
按照这个算法，候选者仍然是之前的那4个区域，不会包括绿色区域，因为其中点在边界之外。但是从用户的角度来说，点击的地方确实在绿色区域之内，应该能够选中绿色区域。
因此使用这种筛选算法，需要避免把异质区域插入相同的multimap。
幸好这个不难处理，使用vector<multimap>来区分异质区域，每种相似或者概念上临近的精灵放到同一个multimap中，异质精灵依靠vector区分。
这样反而让整个Scene更容易组织，也更有逻辑。
明白了获取思路后，加入layer就很好办了。
给Rect增加一个成员变量标明layer，然后获取时先拿到所有合法区域，然后遍历这些区域返回layer最高的。
三、通过坐标选择node的实现
下面我们封装一个类，在urho3d中实际操作。
包含必要头文件：
矩形区域声明：
实现与上面一样，这里不贴了。
然后是一个坐标-节点助手：
（大图点这里）
把multimap和相关参数包装起来，对外提供3个接口，实现如下：
（大图点这里）
GetNode其实也就上上面代码的翻版，只不过这里增加了判断layer的代码。并且注意返回空的处理。
没贴全，使用了泛型算法，比较器是一个lambda，只比较layer。
以上就是全部类，然后可以在代码中使用了。
调整一下之前的小花代码，增加private声明：
为什么要记录鼠标位置呢？因为我们将要注册鼠标按键事件，但是这个事件中无法获得鼠标坐标，于是我们还需要注册鼠标移动事件，随时把当前鼠标位置记录下来，供Helper调用。
在Start()里增加代码：
为什么不在构造函数中初始化Helper?因为构造时无法得到屏幕高和宽，只能在Start()里面做初始化。
（大图点这里）
循环随机在场景中添加50朵花，注意矩形的宽和高也需要乘以PIXEL_SIZE。
这里为了方便把图片大小写死了，因为我们知道这张图是64*64。
实际中可以增加VariantMap给node，把数值存起来。
最后是注册事件：
（大图点这里）
实现MouseMove事件，就是记录坐标：
（大图点这里）
然后MouseClick事件：
（大图点这里）
使用Helper直接通过屏幕坐标获得对应场景Node。因为我们知道Node都是什么，所以获得纹理，然后设置随机颜色。于是理论上当我们点击屏幕上一朵花，花的颜色会随机变化。
实验结果如下：
确实成功了！
而且注意重叠图片的情况，如果点击了一定是最上层花变颜色，这是因为插入node时layer顺序与循环顺序一致。
当然以上只是演示了仅有一个multimap的情况，即图片都是同质的。
聪明的读者一定可以根据自己需求扩展为多个multimap。
另外根据测试结果，随机分布50个图片，筛选出的待排查区域一般在7个左右，这个效率是可以的，肯定比O(n)要快。
不过坐标问题还没有结束，这里的前提是camera不移动，如果移动会更加复杂，见《2D场景-实现鼠标选中场景物体（二）》。