CN110569445A - A Location-Based Neighbor Detection Method in Social Networks - Google Patents

Abstract

the invention discloses a neighbor detection method in a social network based on positions, which is an important problem in the social network service based on the positions. Neighbor detection allows the user to select a particular geometric range on the map and then ask if his friend is within that range. In order to efficiently realize the neighbor detection in the social network, the geometric range selected by a user is abstracted into a convex polygon, the position of a friend of the user is abstracted into a point, then four characteristic vertexes of the convex polygon are extracted, one division of the convex polygon can be realized according to the four characteristic vertexes, then the given point is judged to fall into which partition, the judgment condition corresponding to the partition is called to judge the position relation between the given point and the convex polygon, and the result is finally obtained. The invention can obtain the position relation between the point and the convex polygon only by judging the point and the side once, thereby efficiently solving the problem of neighbor detection in the social network.

Description

A Location-Based Neighbor Detection Method in Social Networks

technical field

The invention belongs to the technical field of social networks, and relates to a method for detecting neighbors in a social network, in particular to a method for detecting neighbors by utilizing the positional relationship between points and convex polygons in a location-based social network service.

Background technique

With the popularization of location-aware mobile terminals and social applications, location-based social networking services (LBSNS) have brought great convenience to people's lives. Among them, the neighbor detection service is a typical application of LBS. Neighbor detection allows the user to select a specific geometric range on the map and then ask his friends if they are within this range. Usually, the geometric range selected by the user is abstracted as a convex polygon, and the position of the user's friend is abstracted as a point, and the neighbor detection problem is solved by judging the positional relationship between the point and the convex polygon.

At present, methods for judging points and convex polygons include: calculating point orientation (document 1), ray method (document 2), angle method (document 3), area method (document 4), etc. In the method of calculating the orientation of a point, it is necessary to judge the orientation of the point and each side of the convex polygon; in the angle method, it is necessary to calculate the angle between the point and each side of the convex polygon; Therefore, these methods generally have the problem of low computational efficiency. In the ray method, a ray is drawn from a given point, and the number of intersections between the ray and the convex polygon is calculated. If the number of intersections is odd, the coordinate point is inside the convex polygon, otherwise the coordinate point is outside the convex polygon. However, when the given point is located on the edge of a convex polygon, this method has the possibility of misjudgment. Therefore, how to efficiently implement neighbor detection in social networks is still a problem worthy of research.

[1] F. Feito, JC Torres, and A. Orientation, simplicity, and inclusion test for planar polygons [J]. Comput. Graph., 1995, 19(4): 595–600.

[2] GALETZKA M, GLAUNER P O.A simple and correct even-odd algorithm for the point-in-polygon problem for complex polygons [OL]. In: Proceedings of the 12th International Joint Conference on Computer Vision, Imaging and Computer Graphics Theory and Applications (VISIGRAPP 2017 ). Porto, Portugal, 2017:175-178.

[3] HORMANN K, AGATHOS A. The point in polygon problem for arbitrary polygons [J]. Computational Geometry, 2001, 20(3): 131-144.

[4] Chen Zhenhua, Li Shundong, Huang Qiong, Dong Lihong, Chen Wei. A new solution to the problem of judging two confidential locations [J]. Journal of Computer Science, 2018, 41(2): 336-348.

Contents of the invention

In order to solve the above problems, the present invention provides a method for performing neighbor detection by using the position relationship between points and convex polygons in a location-based social networking service.

The technical solution adopted in the present invention is: a method for detecting neighbors in a location-based social network, assuming that the geometric range specified by the user is a convex polygon L with n vertices, and starting from the vertex with the largest ordinate, the numbers are sequentially counterclockwise , assuming {P ₁ ,P ₂ ,…,P _n }, its coordinates are ( _xi ,y _i ), i=1,2,…,n, and the position of the user’s friend is expressed as a point P( x _p , y _p ), judge the positional relationship between the point P and the convex polygon L, that is, judge whether the point P is located outside or inside the convex polygon L; the point P is located inside the convex polygon L, including the point P on the side of the convex polygon L If the point P is located outside the convex polygon L, it means that the user's friend is not within the geometric range specified by the user; if the point P is located inside the convex polygon L, it means that the user's friend is within the geometric range specified by the user;

It is characterized in that the method comprises the following steps:

Step ₁ : find out the four characteristic vertices of the convex polygon _L : the uppermost vertex, the leftmost vertex, the lowermost vertex and the rightmost vertex; P _d , the rightmost vertex is recorded as P _r , then 1≤l≤d≤r≤n;

Step 2: Determine the positional relationship between the given point P and the convex polygon L;

Step 3: If the point P is inside the convex polygon L, return the user's friend is within the user-specified geometric range; if the point P is outside the convex polygon L, return the user's friend is not within the user-specified geometric range.

Preferably, the specific realization of step 2 includes the following sub-steps:

Step 2.1: If y _p <y _d or y _p >y ₁ or x _p <x _l or x _p >x _r , then the given point P(x _p , y _p ) is located outside the convex polygon L, and the procedure ends;

Otherwise go to step 2.2;

Step 2.2: If x _p ≤ x ₁ and y _p ≥ y _l , that is, the given point P(x _p , y _p ) is located on the left side of the uppermost vertex P ₁ and on the upper side of the leftmost vertex P _l , at this time, Execute the judgment process I, and this process ends;

Otherwise go to step 2.3;

The concrete realization of described judging process I comprises the following substeps:

Step 2.2.1: Find two adjacent vertices P _i and P _i+1 in the vertices {P ₁ ,P ₂ ,…,P _l } such that x _i ≤x≤x _i+1 , where 1≤i ≤ l-1;

Step 2.2.2: Calculate the straight line between vertices P _i and P _i+1 , and use the symbol f ₁ (x) to represent the straight line;

Step 2.2.3: If y _p ≤ f ₁ (x _p ), then the given point P(x _p ,y _p ) is inside the convex polygon L, otherwise the given point P(x _p ,y _p ) is inside the convex polygon L external;

Step 2.3: If x _p ≤ x _d and y _p <y _l , that is, the given point P(x _p , y _p ) is located on the left side of the lowest vertex P _d and the lower side of the leftmost vertex P _l at this time. , execute the judgment process II, and this process ends;

Otherwise go to step 2.4;

The concrete realization of described judging process II comprises the following sub-steps:

Step 2.3.1: Find two adjacent vertices P _i and P _i+1 in the vertices {P _l ,P _l+1 ,P _l+2 ,…,P _d } such that x _i+1 ≤x≤ x _i , where l-1≤i≤d;

Step 2.3.2: Calculate the straight line through the vertices P _i and P _i+1 , and use the symbol f ₂ (x) to represent the straight line;

Step 2.3.3: If y _p ≥ f ₂ (x _p ), then the given point P(x _p ,y _p ) is inside the convex polygon L, otherwise the given point P(x _p ,y _p ) is inside the convex polygon L external;

Step 2.4: If x _p >x _d and y _p <y _r , that is, the given point P(x _p , y _p ) is located on the right side of the lowest vertex P _d and the lower side of the rightmost vertex P _r at this time, then , execute the judgment process III, and this process ends;

Otherwise go to step 2.5;

The concrete realization of described judging process III comprises the following substeps:

Step 2.4.1: Find two adjacent vertices P _i and P _i+1 in the vertices {P _d , P _d+1 , P _d+2 ,…,P _r }, so that x _i ≤ x ≤ x _{i +1} , where d≤i≤r-1;

Step 2.4.2: Calculate the straight line between vertices P _i and P _i+1 , and use the symbol f ₃ (x) to represent the straight line;

Step 2.4.3: If y _p ≥ f ₃ (x _p ), then the given point P(x _p ,y _p ) is inside the convex polygon L, otherwise the given point P(x _p ,y _p ) is inside the convex polygon L external;

Step 2.5: If x _p >x ₁ and y _p ≥ y _r , that is, the given point P(x _p , y _p ) is located on the right side of the uppermost vertex P ₁ and on the upper side of the rightmost vertex P _r , at this time, Execute the judgment process IV, and this process ends;

The concrete realization of described judging process IV comprises the following sub-steps:

Step 2.5.1: If x ₁ ≤x≤x _n , select vertices P _n and P ₁ , otherwise find adjacent vertices {P _r ,P _r+1 ,P _r+2 ,…,P _n } Two vertices P _i and P _i+1 such that x _i+1 ≤ x ≤ x _i , where r-1≤i≤n;

Step 2.5.2: If the selected vertices are P _n and P ₁ , calculate the straight line between vertices P _n and P ₁ , otherwise calculate the straight line between vertices P _i and P _i+1 , denoted by symbol f ₄ (x) The calculated straight line;

Step 2.5.3: If y _p ≤ f ₄ (x _p ), then the given point P(x _p ,y _p ) is inside the convex polygon L, otherwise the given point P(x _p ,y _p ) is inside the convex polygon L external.

Aiming at the problems of computational cost and low efficiency in existing methods, the present invention discloses a location-based neighbor detection method in social networks; the present invention first abstracts the geometric range selected by the user into a convex polygon, and the location of the user's friends Abstract as a point, then extract the four characteristic vertices of the convex polygon, divide the convex polygon according to the four characteristic vertices, and give the position determination process of the point and the convex polygon in each partition; finally judge the position according to the coordinates of the given point Which partition the point falls in, and then perform the corresponding position determination process, and finally get the solution of the problem. In the method proposed by the present invention, the given point does not need to determine the position with all the sides of the convex polygon, nor does it need to perform problem conversion. Therefore, the present invention greatly reduces the calculation cost.

Description of drawings

Figure 1: A given convex polygon of an embodiment of the present invention;

Figure 2: Schematic diagram of given convex polygon division in the embodiment of the present invention;

Fig. 3: method flowchart of the embodiment of the present invention;

Figure 4: A schematic diagram of the positional relationship between the first point and a given convex polygon in the embodiment of the present invention;

Figure 5: A schematic diagram of the positional relationship between the second point and a given convex polygon in the embodiment of the present invention;

Figure 6: A schematic diagram of the positional relationship between the third point and a given convex polygon in the embodiment of the present invention;

Figure 7: A schematic diagram of the positional relationship between the fourth point and a given convex polygon in the embodiment of the present invention;

Figure 8: A schematic diagram of the positional relationship between the fifth point and a given convex polygon in the embodiment of the present invention;

Figure 9: A schematic diagram of the positional relationship between the sixth point and a given convex polygon in the embodiment of the present invention;

Figure 10: A schematic diagram of the positional relationship between the seventh point and a given convex polygon in the embodiment of the present invention;

Figure 11: A schematic diagram of the positional relationship between the eighth point and a given convex polygon in the embodiment of the present invention;

Fig. 12: A schematic diagram of the positional relationship between the ninth point and a given convex polygon in the embodiment of the present invention.

specific implementation

In order to facilitate those of ordinary skill in the art to understand and implement the present invention, the present invention will be described in further detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the implementation examples described here are only used to illustrate and explain the present invention, and are not intended to limit this invention.

Please refer to Figure 1, assuming that the geometric range specified by the user is a convex polygon L with n vertices, and the numbers are counterclockwise from the vertex with the largest ordinate, assuming {P ₁ ,P ₂ ,…,P _n }, The coordinates are respectively ( _xi , y _i ), i=1, 2,..., n. The four feature vertices are P ₁ (the uppermost vertex), P _l (the leftmost vertex), P _d (the lowermost vertex), and P _r (the rightmost vertex).

Please refer to Figure 2. The position of the user's friend is expressed as a point P, and a division of the convex polygon is realized according to the four characteristic vertices, and 5 partitions are obtained: the first partition corresponds to the blank area in Figure 2, if Point P falls into this area, indicating that point P is outside the convex polygon (see Figure 4); the second partition corresponds to the shaded area marked I in Figure 2, if point P falls into this area, further judgment is required Its position relationship with the convex polygon (see Figure 5 and Figure 6); the third partition corresponds to the shaded area marked II in Figure 2, if point P falls into this area, it is necessary to further judge its position with the convex polygon relationship (see Figure 7 and Figure 8); the fourth partition corresponds to the shaded area marked III in Figure 2, if point P falls into this area, it is necessary to further judge its positional relationship with the convex polygon (see Figure 9 and Fig. 10); the fifth partition corresponds to the shaded area marked as IV in Fig. 2, if point P falls into this area, it is necessary to further judge its positional relationship with the convex polygon (see Fig. 11 and Fig. 12).

Please see Fig. 3, a kind of neighbor detection method in the location-based social network that the present invention provides, comprises the following steps:

Step 1: Find four characteristic vertices of the convex polygon L: the uppermost vertex, the leftmost vertex, the lowermost vertex and the rightmost vertex. According to the numbering rules above, the uppermost vertex is P ₁ , assuming the leftmost vertex is P _l , the lowermost vertex is P _d , and the rightmost vertex is P _r , then 1≤l≤d≤r≤n. Based on the four characteristic vertices, a division of the convex polygon is actually realized. Please refer to Figure 2. The given convex polygon is divided into 5 partitions.

Step 2: Determine the positional relationship between the given point P and the convex polygon L.

Please see steps 2.1 to 2.5 in Figure 3 and Figure 4 to Figure 12, the specific implementation of step 2 includes the following sub-steps:

Step 2.1: If y _p <y _d or y _p >y ₁ or x _p <x _l or x _p >x _r , the point P(x _p ,y _p ) falls into the blank area (corresponding to the situation shown in Figure 4) , then the given point P(x _p ,y _p ) is located outside the convex polygon L, otherwise go to step 2.2;

Step 2.2: If x _p ≤ x ₁ and y _p ≥ y _l , that is, the point P(x _p , y _p ) falls into area I, then execute the following steps 2.2.1 to 2.2.3, otherwise go to step 2.3 .

Step 2.2.1: Find two adjacent vertices P _i and P _i+1 in the vertices {P ₁ ,P ₂ ,…,P _l } such that x _i ≤x≤x _i+1 , where 1≤i ≤ l-1;

Step 2.2.2: Calculate the straight line between vertices P _i and P _i+1 , and use the symbol f ₁ (x) to represent the straight line;

Step 2.2.3: If y _p ≤ f ₁ (x _p ) (corresponding to the situation shown in Figure 5), then the given point P(x _p ,y _p ) is located inside the convex polygon L, otherwise (corresponding to the situation shown in Figure 6 ) A given point P(x _p , y _p ) lies outside the convex polygon L.

Step 2.3: If x _p ≤ x _d and y _p <y _l , that is, the point P(x _p , y _p ) falls into area II, then execute the following steps 2.3.1 to 2.3.3, otherwise go to step 2.4 .

Step 2.3.1: Find two adjacent vertices P _i and P _i+1 in the vertices {P _l ,P _l+1 ,P _l+2 ,…,P _d } such that x _i+1 ≤x≤ x _i , where l-1≤i≤d;

Step 2.3.2: Calculate the straight line through the vertices P _i and P _i+1 , and use the symbol f ₂ (x) to represent the straight line;

Step 2.3.3: If y _p ≥ f ₂ (x _p ) (corresponding to the situation shown in Figure 7), then the given point P(x _p ,y _p ) is located inside the convex polygon L, otherwise (corresponding to the situation shown in Figure 8 ) A given point P(x _p , y _p ) lies outside the convex polygon L.

Step 2.4: If x _p >x _d and y _p <y _r , that is, the point P(x _p ,y _p ) falls into region III, then execute the following steps 2.4.1 to 2.4.3, otherwise go to step 2.5 .

Step 2.4.1: Find two adjacent vertices P _i and P _i+1 in the vertices {P _d , P _d+1 , P _d+2 ,…,P _r }, so that x _i ≤ x ≤ x _{i +1} , where d≤i≤r-1;

Step 2.4.2: Calculate the straight line between vertices P _i and P _i+1 , and use the symbol f ₃ (x) to represent the straight line;

Step 2.4.3: If y _p ≥ f ₃ (x _p ) (corresponding to the situation shown in Figure 9), then the given point P(x _p ,y _p ) is located inside the convex polygon L, otherwise (corresponding to the situation shown in Figure 10 ) A given point P(x _p , y _p ) lies outside the convex polygon L.

Step 2.5: At this point x _p >x ₁ and y _p ≥y _r , that is, the point P(x _p ,y _p ) falls into region IV, and the following steps 2.5.1 to 2.5.3 are performed.

Step 2.5.1: If x ₁ ≤x≤x _n , select vertices P _n and P ₁ , otherwise find adjacent vertices {P _r ,P _r+1 ,P _r+2 ,…,P _n } Two vertices P _i and P _i+1 such that x _i+1 ≤ x ≤ x _i , where r-1≤i≤n;

Step 2.5.2: If the selected vertices are P _n and P ₁ , calculate the straight line between vertices P _n and P ₁ , otherwise calculate the straight line between vertices P _i and P _i+1 , denoted by symbol f ₄ (x) The calculated straight line;

Step 2.5.3: If y _p ≤ f ₄ (x _p ) (corresponding to the situation shown in Figure 11), then the given point P(x _p ,y _p ) is located inside the convex polygon L, otherwise (corresponding to the situation shown in Figure 12 ) A given point P(x _p , y _p ) lies outside the convex polygon L.

Step 3: If the point P is inside the convex polygon L, return the user's friend is within the user-specified geometric range; if the point P is outside the convex polygon L, return the user's friend is not within the user-specified geometric range.

Aiming at the problem of neighbor detection in social networks, the present invention firstly abstracts the geometric range selected by the user into a convex polygon, and abstracts the position of the user's friend into a point, then extracts four characteristic vertices of the convex polygon, and performs a convex alignment according to the four characteristic vertices. The polygon is divided, and the position judgment process of the point and the convex polygon in each partition is given; finally, according to the coordinates of the given point, it is judged which partition the point falls in, and then the corresponding position judgment process is performed, and finally the solution of the problem is obtained. The invention only needs to judge the point and the edge once to obtain the positional relationship between the point and the convex polygon, thus efficiently solving the problem of neighbor detection in the social network.

It should be understood that the parts not described in detail in this specification belong to the prior art.

It should be understood that the above-mentioned descriptions for the preferred embodiments are relatively detailed, and should not therefore be considered as limiting the scope of the patent protection of the present invention. Within the scope of protection, replacements or modifications can also be made, all of which fall within the protection scope of the present invention, and the scope of protection of the present invention should be based on the appended claims.

Claims (2)

1. A neighbor detection method in a social network based on positions is characterized in that a geometric range specified by a user is a convex polygon L with n vertexes, and the geometric range is sequentially numbered anticlockwise from the vertex with the largest ordinate, and is assumed to be { P₁,P₂,…,P_nAre respectively (x) in coordinates_i,y_i)，i1,2, …, n, and represents the location of the user's friend as a point P (x)_p,y_p) Judging the position relation between the point P and the convex polygon L, namely judging whether the point P is positioned outside or inside the convex polygon L; the point P is positioned inside the convex polygon L and comprises the condition that the point P is positioned on the side of the convex polygon L; if the point P is positioned outside the convex polygon L, the situation that the friends of the user are not in the geometric range specified by the user is shown; if the point P is positioned inside the convex polygon L, the situation that the friend of the user is positioned in the geometric range specified by the user is shown;

Characterized in that the method comprises the following steps:

Step 1: finding four characteristic vertexes of the convex polygon L: a top vertex, a left vertex, a bottom vertex and a right vertex; the uppermost vertex is marked as P₁Let the leftmost vertex be denoted as P_lthe lowest vertex is denoted as P_dAnd the rightmost vertex is marked as P_rIf l is more than or equal to 1 and less than or equal to d and less than or equal to r and less than or equal to n;

step 2: judging the position relation between the given point P and the convex polygon L;

And step 3: if the point P is inside the convex polygon L, returning that the friend of the user is positioned in the geometric range specified by the user; if the point P is outside the convex polygon L, the friend returning to the user is not within the user-specified geometric range.

2. The method for detecting the nearest neighbor in the social network based on the position as claimed in claim 1, wherein the step 2 comprises the following steps:

step 2.1: if y is_p<y_dOr y_p>y₁Or x_p<x_lOr x_p>x_rThen, given point P (x)_p,y_p) The flow is finished when the convex polygon L is positioned outside the convex polygon L;

Otherwise, entering step 2.2;

step 2.2: if x_p≤x₁And y is_p≥y_lat this time, the given point P (x)_p,y_p) At the uppermost vertex P₁Left and leftmost vertex P_lAt this time, the judgment is performedprocess I, the process is finished;

Otherwise, entering step 2.3;

The specific implementation of the judgment process I comprises the following sub-steps:

Step 2.2.1: at the vertex { P₁,P₂,…,P_lFind two adjacent vertexes P_iand P_i+1So that x is_i≤x≤x_i+1Wherein i is more than or equal to 1 and less than or equal to l-1;

Step 2.2.2: computing over-vertex P_iAnd P_i+1Straight line of (2), with the symbol f₁(x) Represents the straight line;

step 2.2.3: if y is_p≤f₁(x_p) Then, given point P (x)_p,y_p) Located inside the convex polygon L, otherwise given a point P (x)_p,y_p) Located outside the convex polygon L;

Step 2.3: if x_p≤x_dAnd y is_p<y_lat this time, the given point P (x)_p,y_p) At the lowest vertex P_dLeft and leftmost vertex P_lAt this time, the judgment process II is executed, and the process is ended;

otherwise, entering step 2.4;

The specific implementation of the judgment process II comprises the following substeps:

step 2.3.1: at the vertex { P_l,P_l+1,P_l+2,…,P_dfind two adjacent vertexes P_iAnd P_i+1so that x is_i+1≤x≤x_iwherein l-1 is more than or equal to i is more than or equal to d;

Step 2.3.2: computing over-vertex P_iand P_i+1Straight line of (2), with the symbol f₂(x) Represents the straight line;

Step 2.3.3: if y is_p≥f₂(x_p) Then, given point P (x)_p,y_p) Located inside the convex polygon L, otherwise given a point P (x)_p,y_p) Located outside the convex polygon L;

Step 2.4: if x_p>x_dAnd y is_p<y_rAt this time, the given point P (x)_p,y_p) At the lowest vertex P_dRight side and rightmost vertex P of_rAt this time, the judgment process III is executed, and the process is ended;

Otherwise, entering step 2.5;

The specific implementation of the judgment process III includes the following substeps:

step 2.4.1: at the vertex { P_d,P_d+1,P_d+2,…,P_rFind two adjacent vertexes P_iAnd P_i+1So that x is_i≤x≤x_i+1Wherein d is not less than i and not more than r-1;

Step 2.4.2: computing over-vertex P_iand P_i+1Straight line of (2), with the symbol f₃(x) Represents the straight line;

step 2.4.3: if y is_p≥f₃(x_p) Then, given point P (x)_p,y_p) Located inside the convex polygon L, otherwise given a point P (x)_p,y_p) Located outside the convex polygon L;

Step 2.5: if x_p>x₁and y is_p≥y_rat this time, the given point P (x)_p,y_p) At the uppermost vertex P₁right side and rightmost vertex P of_rAt this time, the judgment process IV is executed, and the process is ended;

The specific implementation of the judgment process IV includes the following substeps:

step 2.5.1: if x₁≤x≤x_nSelecting the vertex P_nAnd P₁Otherwise at vertex { P_r,P_r+1,P_r+2,…,P_nfind two adjacent vertexes P_iAnd P_i+1So that x is_i+1≤x≤x_iwherein r-1 is not less than i and not more than n;

Step 2.5.2: if the selected vertex is P_nAnd P₁Then the vertex P is calculated_nand P₁Otherwise, the vertex P is calculated_iAnd P_i+1Straight line of (2), with the symbol f₄(x) Representing the calculated straight line;

Step 2.5.3: if y is_p≤f₄(x_p) Then, given point P (x)_p,y_p) Located inside the convex polygon L, otherwise given a point P (x)_p,y_p) Outside the convex polygon L.