“你附近有什么标识？”——基于邻近相关性的搜寻-亚博88体育

　　我们外出旅游，无论在繁华城市，还是在荒郊野外，往往可能走散。这时，我们要通过呼喊或用手机等进行联系，以便确定方位，大家才能很快重新集合在一起。在寻找过程中，大家常常对话：你附近有什么标识，有什么特别的标识？然后，根据这些标识，确定寻找路径，以最短的时间会面。 

　　现在计算机技术已应用于很多方面，给我们的生产实践和日常生活带来了很大的效率提升和便利。在各种计算机技术中，有一项重要的技术就是快速定位。为此，先对要处理的问题形成一个空间，然后将此空间划分成许多区域，计算机要通过一定的计算、判断等处理，快速确定要寻找的内容在哪个区域中。比如说，北京市就划分成东城区、西城区、海淀区、朝阳区、丰台区、石景山区等，我们要寻找一个人在哪个区，就要根据这个人所在位置的情况，判断这个位置所在的区域，以确定这个人在那个区。常见的一种方法是建立坐标系，然后确定这个人的位置坐标，然后对比各个区的坐标范围，就可判定这个人在哪个区了。 

　　但这样处理有些不足。各个城区的边界比较复杂，要获取各个城区的坐标覆盖范围，要进行比较复杂的计算，费时费力。如果事先算好，存储起来，在定位计算时可以很快判断。但这样需要很多的存储空间，浪费资源；特别是，存储往往是离散化处理的，有些地方可能被遗漏，由此使得定位判断可能出现失误。比如说，存储了“黄庄——知春桥”、“四通桥——蓟门桥”这两条线段之间的部分都是属于海淀区的，那么位于这两条线之间的双榆树公园是否属于海淀区呢？不能直接判断，还要通过一些复杂的计算。如果直接判断，双榆树公园跟这两条线都不搭界，可能误判为“不知道”。 

　　在计算机图形学中，关于“判断一个点是否位于一个多边形中”的问题有许多研究，提出了许多方法，供计算机实现以处理相关事情。一个基本的处理原则是：从这个点发出一条射线，统计这条射线与多边形的边界相交的次数；然后根据统计数的奇偶性进行判断。如果次数为偶数，就表示这个点在多边形外面，因为这条射线穿进多边形又穿出了，不停的穿进穿出，最后还是穿出了。同理，如果为奇数，就是这条射线穿进穿出多次后，最终穿进而不出来了，就表明该点在多边形内。如图1所示。 

　　以上处理方法，虽然简单，但与多边形的每条边要进行相交测试，时间开销是很大的。怎么办呢？我们提出一个方法，画一个方框将这个多边形包围起来，然后将这个方框均匀地划分成许多方块，并预先计算好每个方块中的中心点是否位于多边形内。然后，在判断一个点是否位于多边形中时，我们先找到这个点在哪个方块中。由于方块是均匀划分的，各个方块的边长一样。这样,我们根据这个点的坐标情况，可得到这个点到方框边界的距离，将该距离除以方块的边长，根据商数和余数，就可判断出这个点位于哪个方块中。 

　　下一步，就是将这个点与它所在方块的中心点进行连线，统计这条连线与多边形的边相交的计数情况。显然，这时我们只需考察位于这个方块中的多边形的边，而不必考察这个方块外的多边形的边，由此节省大量的计算。那么在判断时，除了要依据统计数的奇偶性外，还要依据中心点是否位于多边形内的信息。但这样的判断也是很容易处理的。如图2所示。 

　　这样处理，存储空间不需要很多，而计算效率可提高很多。该方法也容易推广来处理“判断一个点是否位于一个多面体内”的三维问题。我们推广到三维问题的处理，可将计算复杂度降至o(1)，实验数据表明: 相比已有的方法，改进方法可加速上千倍。相关论文，也发表在国际一流刊物computer-aided design上。 

　　这个工作就是利用了附近的“标识”信息，节省了大量无关计算。这与我们找人时“你附近有什么标识”有异曲同工之妙。生活中有着无穷无尽的智慧之光，只要我们有心，就能在高技术等科研工作中取得很好的进展。大家都能做科学研究呵。