1.一种基于位置的社交网络中近邻检测方法，假设用户指定的几何范围是一个具有n个顶点的凸多边形L，从纵坐标最大的顶点开始依次进行逆时针编号，假设为{P1,P2,…,Pn}，其坐标分别为(xi,yi)，i＝1,2,…,n，并将用户朋友的位置表示为一个点P(xp,yp)，判断点P与凸多边形L之间的位置关系，即判断点P是位于凸多边形L的外部还是内部；点P位于凸多边形L的内部包括点P在凸多边形L边上的情况；如果点P位于凸多边形L的外部，则说明用户的朋友不在用户指定的几何范围内；如果点P位于凸多边形L的内部，则说明用户的朋友位于用户指定的几何范围内；

其特征在于，所述方法包括以下步骤：

步骤1：找出凸多边形L的四个特征顶点：最上顶点、最左顶点、最下顶点和最右顶点；最上顶点记为P1，假设最左顶点记为Pl，最下顶点记为Pd，最右顶点记为Pr，则有1≤l≤d≤r≤n；

步骤2：判定给定点P与凸多边形L的位置关系；

步骤2的具体实现包括以下子步骤：

步骤2.1：如果ypy1或者xpxr，则给定点P(xp,yp)位于凸多边形L的外部，本流程结束；

否则进入步骤2.2；

步骤2.2：如果xp≤x1且yp≥yl，即此时给定点P(xp,yp)位于最上顶点P1的左侧和最左顶点Pl的上侧，此时，执行判断过程I，本流程结束；

否则进入步骤2.3；

所述判断过程I的具体实现包括以下子步骤：

步骤2.2.1：在顶点{P1,P2,…,Pl}中找到相邻的两个顶点Pi和Pi+1，使得xi≤x≤xi+1，其中1≤i≤l‑1；

步骤2.2.2：计算过顶点Pi和Pi+1的直线，用符号f1(x)表示该直线；

步骤2.2.3：如果yp≤f1(xp)，则给定点P(xp,yp)位于凸多边形L的内部，否则给定点P(xp,yp)位于凸多边形L的外部；

步骤2.3：如果xp≤xd且yp

否则进入步骤2.4；

所述判断过程II的具体实现包括以下子步骤：

步骤2.3.1：在顶点{Pl,Pl+1,Pl+2,…,Pd}中找到相邻的两个顶点Pi和Pi+1，使得xi+1≤x≤xi，其中l‑1≤i≤d；

步骤2.3.2：计算过顶点Pi和Pi+1的直线，用符号f2(x)表示该直线；

步骤2.3.3：如果yp≥f2(xp)，则给定点P(xp,yp)位于凸多边形L的内部，否则给定点P(xp,yp)位于凸多边形L的外部；

步骤2.4：如果xp>xd且yp

否则进入步骤2.5；

所述判断过程III的具体实现包括以下子步骤：

步骤2.4.1：在顶点{Pd,Pd+1,Pd+2,…,Pr}中找到相邻的两个顶点Pi和Pi+1，使得xi≤x≤xi+1，其中d≤i≤r‑1；

步骤2.4.2：计算过顶点Pi和Pi+1的直线，用符号f3(x)表示该直线；

步骤2.4.3：如果yp≥f3(xp)，则给定点P(xp,yp)位于凸多边形L的内部，否则给定点P(xp,yp)位于凸多边形L的外部；

步骤2.5：如果xp>x1且yp≥yr，即此时给定点P(xp,yp)位于最上顶点P1的右侧和最右顶点Pr的上侧，此时，执行判断过程IV，本流程结束；

所述判断过程IV的具体实现包括以下子步骤：

步骤2.5.1：若x1≤x≤xn，则选中顶点Pn和P1，否则在顶点{Pr,Pr+1,Pr+2,…,Pn}中找到相邻的两个顶点Pi和Pi+1，使得xi+1≤x≤xi，其中r‑1≤i≤n；

步骤2.5.2：若选中的顶点为Pn和P1，则计算过顶点Pn和P1的直线，否则计算过顶点Pi和Pi+1的直线，用符号f4(x)表示计算得到的直线；

步骤2.5.3：如果yp≤f4(xp)，则给定点P(xp,yp)位于凸多边形L的内部，否则给定点P(xp,yp)位于凸多边形L的外部；

步骤3：如果点P在凸多边形L的内部，则返回用户的朋友位于用户指定的几何范围内；

如果点P在凸多边形L的外部，则返回用户的朋友不在用户指定的几何范围内。