CN108573653B

CN108573653B - Electronic map generation method and device

Info

Publication number: CN108573653B
Application number: CN201710146848.9A
Authority: CN
Inventors: 岳大威; 孟凡超; 汤沛
Original assignee: Tencent Technology Shenzhen Co Ltd
Current assignee: Tencent Technology Shenzhen Co Ltd
Priority date: 2017-03-13
Filing date: 2017-03-13
Publication date: 2022-01-04
Anticipated expiration: 2037-03-13
Also published as: CN108573653A

Abstract

The invention discloses an electronic map generation method and device. Wherein, the method comprises the following steps: acquiring position information of key positions on block areas belonging to the same area type, wherein the block areas are acquired areas used for generating an electronic map, the key positions are located on the boundaries of the block areas, and the distance between the block areas belonging to the same area type is smaller than a preset threshold; determining a convex hull boundary matched with the region type according to the acquired position information of the key position; subdividing a convex hull area covered by a convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area; and deleting a target boundary in the basic area according to a preset condition, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas. The invention solves the technical problem of low generation accuracy of the electronic map in the prior art.

Description

Electronic map generation method and device

Technical Field

The invention relates to the field of computers, in particular to an electronic map generation method and device.

Background

Nowadays, for convenience of travel, many electronic maps applied to terminals are widely used. The spatial distribution characteristic elements displayed in the electronic map are usually generated by real-time exploration by using the collected position information of the key positions. Here, the spatial distribution characteristics include: natural geographical topography distribution, administrative region distribution, social and economic condition distribution, important building location distribution, road path distribution and the like.

For the distribution area displayed in the electronic map, a currently common method is also to generate the distribution area according to the actually collected location information of the discrete key locations. However, since the positions of the discrete point positions are actually collected, and the distribution areas displayed in the electronic map are generated by using the point positions, the areas of the distribution areas presented in the electronic map are small, and the presented positions are also dispersed, so that the generated electronic map includes a plurality of dispersed block areas, the actual spatial distribution characteristics cannot be accurately restored, and the generated electronic map has low accuracy.

In view of the above problems, no effective solution has been proposed.

Disclosure of Invention

The embodiment of the invention provides an electronic map generation method and device, which at least solve the technical problem of low generation accuracy of an electronic map in the prior art.

According to an aspect of an embodiment of the present invention, there is provided an electronic map generation method including: acquiring position information of key positions on block areas belonging to the same area type, wherein the block areas are acquired areas used for generating an electronic map, the key positions are located on the boundaries of the block areas, and the distance between the block areas belonging to the same area type is smaller than a preset threshold value; determining a convex hull boundary matched with the region type according to the acquired position information of the key position; subdividing a convex hull region covered by the convex hull boundary to obtain a plurality of basic regions corresponding to the convex hull region; and deleting the target boundary in the basic area according to a preset condition, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas.

According to another aspect of the embodiments of the present invention, there is also provided an electronic map generating apparatus, including: an acquisition unit configured to acquire position information of key positions on block areas belonging to the same area type, where the block areas are areas for generating an electronic map obtained by acquisition, the key positions are located on boundaries of the block areas, and a distance between the block areas belonging to the same area type is smaller than a predetermined threshold; a determining unit, configured to determine, according to the obtained location information of the key location, a convex hull boundary matched with the region type; the subdivision unit is used for subdividing the convex hull area covered by the convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area; and the generating unit is used for deleting the target boundary in the basic area according to a preset condition and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas.

In the embodiment of the invention, the position information of the key position on the block areas belonging to the same area type is acquired to realize effective combination of the discrete block areas in the area type, then, the convex hull boundary of the area type is determined, the convex hull area covered by the convex hull boundary is divided, the target boundary in the divided basic area is removed, so that the combined area is adjusted, and a map area in the electronic map is generated. That is to say, after the collected block regions are combined, the convex hull boundary is determined, and the boundary is split, the generated map region is more accurate, and the finely-divided region is generated no longer only based on the position information of discrete positions, so that the problem of low generation accuracy of the electronic map in the prior art is solved.

Drawings

The accompanying drawings, which are included to provide a further understanding of the invention and are incorporated in and constitute a part of this application, illustrate embodiment(s) of the invention and together with the description serve to explain the invention without limiting the invention. In the drawings:

fig. 1 is a schematic application environment diagram of an alternative electronic map generation method according to an embodiment of the present invention;

FIG. 2 is a flow diagram of an alternative electronic map generation method according to an embodiment of the present invention;

FIG. 3 is a schematic diagram of an alternative electronic map generation method according to an embodiment of the invention;

FIG. 4 is a schematic diagram of another alternative electronic map generation method according to an embodiment of the present invention;

FIG. 5 is a schematic diagram of yet another alternative electronic map generation method in accordance with embodiments of the present invention;

FIG. 6 is a schematic diagram of yet another alternative electronic map generation method in accordance with embodiments of the present invention;

FIG. 7 is a schematic diagram of an alternative electronic map generating apparatus according to an embodiment of the present invention;

fig. 8 is a schematic diagram of an alternative electronic map generation server according to an embodiment of the present invention.

Detailed Description

In order to make the technical solutions of the present invention better understood, the technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.

It should be noted that the terms "first," "second," and the like in the description and claims of the present invention and in the drawings described above are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used is interchangeable under appropriate circumstances such that the embodiments of the invention described herein are capable of operation in sequences other than those illustrated or described herein. Furthermore, the terms "comprises," "comprising," and "having," and any variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method, system, article, or apparatus that comprises a list of steps or elements is not necessarily limited to those steps or elements expressly listed, but may include other steps or elements not expressly listed or inherent to such process, method, article, or apparatus.

Example 1

In an embodiment of the present invention, an embodiment of the electronic map generation method is provided. As an optional implementation, the electronic map generation method may be but is not limited to be applied to the application environment shown in fig. 1, where the server 106 acquires, through the network 104, location information of an area that is reported by the terminal 102, and acquires location information of a key location on block areas belonging to the same area type, where the block areas are areas that are obtained through acquisition and used for generating the electronic map, the key location is located on a boundary of the block areas, and a distance between the block areas belonging to the same area type is smaller than a predetermined threshold; then, determining a convex hull boundary matched with the region type according to the acquired position information of the key position; subdividing a convex hull area covered by the convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area; and deleting the target boundary in the basic area according to a preset condition, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas.

In this embodiment, the discrete block areas in the area type are effectively merged by acquiring the position information of the key position on the block areas belonging to the same area type, and then, the convex hull boundary of the area type is determined, the convex hull area covered by the convex hull boundary is divided, and the target boundary in the divided basic area is removed, so that the merged area is adjusted, and a map area in the electronic map is generated. That is to say, the collected block regions are merged and adjusted to generate a more accurate map region, and the finely divided regions are generated no longer only based on the position information of discrete positions, so that the problem of low accuracy in generating an electronic map in the prior art is solved.

Optionally, in this embodiment, the terminal may include, but is not limited to, at least one of the following: mobile phones, tablet computers, notebook computers, desktop PCs and other hardware devices for collecting location information. The network may include, but is not limited to, at least one of: wide area networks, metropolitan area networks, and local area networks. The above is only an example, and the present embodiment is not limited to this.

According to an embodiment of the present invention, there is provided an electronic map generation method, as shown in fig. 2, the method including:

s202, acquiring position information of key positions on block areas belonging to the same area type, wherein the block areas are acquired and used for generating an electronic map, the key positions are located on the boundaries of the block areas, and the distance between the block areas belonging to the same area type is smaller than a preset threshold;

s204, determining a convex hull boundary matched with the region type according to the acquired position information of the key position;

s206, subdividing a convex hull area covered by a convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area;

and S208, deleting the target boundary in the basic area according to a preset condition, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas.

Optionally, in this embodiment, the method for generating the electronic map may be, but is not limited to, applied to different client applications or Web applications, where the application may be an electronic map application, a navigation positioning application, or other applications that require displaying an electronic map. The above is only an example, and this is not limited in this embodiment.

It should be noted that, in this embodiment, the position information of the key position on the block areas belonging to the same area type is obtained to implement effective merging of discrete block areas in the area type, then, the convex hull boundary of the area type is determined, the convex hull area covered by the convex hull boundary is split, and the target boundary in the split basic area is removed to implement adjustment of the merged area, so as to generate one map area in the electronic map. That is to say, after the collected block regions are combined, the convex hull boundary is determined, and the boundary is split, the generated map region is more accurate, and the finely-divided region is generated no longer only based on the position information of discrete positions, so that the problem of low generation accuracy of the electronic map in the prior art is solved. Further, after the above-mentioned processing is performed on the finely divided area, the processing efficiency when the subsequent display processing is performed on the electronic map will also be improved.

Optionally, in this embodiment, the obtaining of the location information of the key location on the block areas belonging to the same area type may include, but is not limited to: acquiring a block area within a preset range; judging the distance between each block area in the preset range; when the distance between the two block areas is smaller than a preset threshold value, judging that the two block areas belong to the same area type; when the distance between the two block regions is greater than or equal to a predetermined threshold, it is determined that the two block regions belong to different region types.

It should be noted that, the above-mentioned distance between the block regions determined to be within the predetermined range may include, but is not limited to: the distance between two positions where two block regions are closest is determined. Wherein, the predetermined range can be but not limited to be determined according to the display scale of the electronic map,

for example, the collected position information in all block areas is stored in a memory according to the proportion of 1: 25000; taking the reference point as the center of a circle, obtaining the distance between the block areas with the radius of 2.5 kilometers, if the distance between the two nearest positions on the two block areas is calculated, if the distance is less than 10 meters, the two block areas are considered to belong to the same area type; and if the distance is greater than or equal to 10 meters, discarding until all block areas belonging to the same area type are acquired.

Optionally, in this embodiment, determining, according to the obtained location information of the key location, a convex hull boundary matched with the area type may include, but is not limited to: and according to the principle of vector included angle homodromous, carrying out recursion test on the obtained key positions in sequence to determine whether the key positions belong to target positions on the convex hull boundary.

It should be noted that the principle of the above-mentioned vector included angle homodromous may be, but is not limited to: judging whether the vector included angle of two adjacent vectors is the same-direction included angle or not in a plurality of vectors which are connected end to end; the vertexes of the vectors which are the same-direction included angles are divided into a class. Wherein, the polarities of the vector products of the equidirectional included angles are the same, like positive or same negative. That is, in the present embodiment, but not limited to, the key position corresponding to the vertex position of the boundary vector whose vector product on the convex hull boundary is all positive may be determined to belong to the target position on the convex hull boundary.

For example, as shown in fig. 3, a vector formed from key position 0 to key position 3 is determined to satisfy the principle of vector angle homodromous by using key position 0 as a reference origin, and thus, key position 0 to key position 3 belong to target positions on the convex hull boundary; and for key positions 4-5, the judgment shows that the key positions in front do not satisfy the vector included angle homodromous principle, because the key positions 4-5 do not belong to the target positions on the convex hull boundary. The above is only an example, and this is not limited in this embodiment.

Furthermore, it should be noted that the above convex hull may be, but is not limited to, a convex hull in a real vector space V, where the intersection S of all convex sets containing X is called X' S convex hull for a given set X, and the convex hull is conceivable as a rubber band that just encloses all points in a two-dimensional euclidean space.

Optionally, in this embodiment, the partitioning the convex hull region covered by the convex hull boundary to obtain the plurality of basic regions corresponding to the convex hull region may be, but is not limited to, partitioning the convex hull region covered by the convex hull boundary according to a triangulation to obtain a plurality of basic regions corresponding to the convex hull region, where the basic regions include: a triangular region. Alternatively, in this embodiment, the triangulation may be, but is not limited to, Delaunay triangulation, that is, a network composed of only triangles and obtained by dividing polygons corresponding to convex hull regions, where the minimum angle is maximized, for example, the triangular regions obtained after the triangulation are shown in fig. 4.

Optionally, in this embodiment, deleting the target boundary in the basic area according to the preset condition may be, but is not limited to, predating the basic area corresponding to the area type according to the preset condition, so as to implement more accurate boundary adjustment on the synthesized area.

According to the embodiment provided by the application, the position information of the key position on the block areas belonging to the same area type is acquired to realize effective combination of the discrete block areas in the area type, then, the convex hull boundary of the area type is determined, the convex hull area covered by the convex hull boundary is divided, the target boundary in the divided basic area is removed, the combined area is adjusted, and therefore a map area in the electronic map is generated. That is to say, after the collected block regions are combined, the convex hull boundary is determined, and the boundary is split, the generated map region is more accurate, and the finely-divided region is generated no longer only based on the position information of discrete positions, so that the problem of low generation accuracy of the electronic map in the prior art is solved.

As an alternative, deleting the target boundary in the base area according to the preset condition includes:

s1, acquiring a key position from the convex hull boundary as a first reference origin;

s2, sequentially performing the following operations on boundaries located on a preset trajectory among the boundaries of the base area, with the first reference origin as a starting point, wherein the preset trajectory is a dynamic trajectory having a predetermined width;

s22, judging whether the current boundary meets the preset condition;

s24, when the current boundary meets the preset conditions, identifying the current boundary as a target boundary, deleting the target boundary, and acquiring an adjacent boundary which has a coincident starting point with the current boundary as a next current boundary in the preset track;

and S26, when the current boundary does not meet the preset condition, acquiring a boundary which is adjacent to the current boundary and has a coincident end point as a next current boundary in the preset track.

Specifically, the following example is used to explain that the acquired convex hull boundary is as shown in fig. 5, and the base region is a triangular region. Further, assuming that a key position F is obtained from the convex hull boundary as the first reference origin, the predetermined width of the preset trajectory is D, and the boundary on the basic area is obtained from the start point of the key position F in the counterclockwise direction as the current boundary.

For example, assuming that the current boundary is an FA, when the current boundary FA meets a preset condition, identifying the current boundary FA as a target boundary, deleting the target boundary, and then acquiring an adjacent boundary FM having a coincident starting point with the current boundary FA as a next current boundary in a preset track;

further, assuming that the current boundary is FM, when the current boundary FM does not satisfy the preset condition, acquiring a boundary MA adjacent to the current boundary FM and having a coincident end point as a next current boundary in the preset trajectory.

Through the embodiment provided by the application, the boundary on the basic area is dynamically judged to obtain the deleted boundary as the target boundary, so that the deleted area is more actually fitted, and the obtained map area is more accurate.

As an optional scheme, the determining whether the current boundary meets the preset condition includes:

s1, judging whether the preset width of the preset track is smaller than the length of the current boundary;

s2, when the preset width is smaller than the length of the current boundary, judging that the current boundary meets the preset condition;

s3, when the preset width is larger than or equal to the length of the current boundary, judging whether the preset width is larger than the length of an adjacent boundary which has a coincident starting point with the current boundary;

s4, when the preset width is larger than the length of the adjacent boundary with the coincidence starting point with the current boundary, judging that the current boundary meets the preset condition; and when the preset width is smaller than the length of an adjacent boundary which has a coincidence starting point with the current boundary, judging that the current boundary does not meet the preset condition.

Specifically, the following example is used to explain, assuming that the acquired convex hull boundary is still as shown in fig. 5, and the base region is a triangular region. Further, assuming that a key position F is obtained from the convex hull boundary as the first reference origin, the predetermined width of the preset trajectory is D, and the boundary on the basic area is obtained from the start point of the key position F in the counterclockwise direction as the current boundary.

For example, assuming that the current boundary is an FA, determining a size relationship between the width D and the length of the current boundary FA, assuming that the width D is smaller than the length of the current boundary FA, identifying the current boundary FA as a target boundary, deleting the target boundary, and then acquiring an adjacent boundary FM having a coincident starting point with the current boundary FA as a next current boundary in the preset track;

for another example, assuming that the current boundary is FA, the magnitude relationship between the width D and the length of the current boundary FA is determined, and assuming that the width D is greater than the length of the current boundary FA, it is determined whether the width D is greater than the length of the adjacent boundary FM having the start point of coincidence with the current boundary FA. Further, assuming that the width D is greater than the length of the adjacent boundary FM, it is determined that the current boundary FA is the target boundary, and the target boundary is deleted; and assuming that the width D is smaller than the length of the adjacent boundary FM, it is determined that the current boundary FA is not the target boundary.

That is to say, when the predetermined width of the preset track is greater than the length of the current boundary, further, by comparing the predetermined width of the preset track with the length of an adjacent boundary having a coincident starting point with the current boundary, further, it is determined whether to identify the current boundary as the target boundary, thereby achieving the purpose of improving the accuracy of obtaining the target boundary.

It should be noted that the preset trajectory may be, but is not limited to, a dynamic closed trajectory obtained by rolling a rolling ball, that is, the preset trajectory obtains different trajectories according to the determination result of different boundaries, and the obtained trajectory is a closed trajectory. In addition, the predetermined width of the preset track may be, but is not limited to, a small sphere diameter, that is, when the small sphere diameter is smaller than the boundary width of the boundary, the small sphere will be sunk into the convex hull region to find that the boundary is the target boundary, and needs to be identified as the target boundary and deleted; and when the diameter of the small ball is larger than or equal to the width of the boundary, the small ball cannot fall into the convex hull area, so that the boundary is not the target boundary. The above is only an example, and this is not limited in this embodiment.

Optionally, in this embodiment, before determining whether the current boundary meets the preset condition, the method further includes: dividing boundaries located on a preset track in each boundary of the basic area into a plurality of sub-boundaries, wherein the preset track is a closed track; a current boundary is obtained from the plurality of sub-boundaries.

It should be noted that, the boundary is divided into sub-boundaries to improve the accuracy of acquiring the target boundary. That is, by dividing more sub-boundaries, the accuracy of predation inside the base region corresponding to the convex hull region is improved. For example, a plurality of reference positions are added between the boundary FAs, so that the boundary FAs are divided into a plurality of sub-boundaries, the reference positions are respectively connected with the key positions M, so as to obtain a plurality of newly added base areas, and the refined base areas are further subjected to silkworm rearing judgment, so as to determine the refined target boundaries, thereby further improving the accuracy of silkworm rearing.

Through the embodiment provided by the application, each boundary on the basic area is accurately judged so as to achieve the aim of accurately acquiring the target boundary to be deleted, and further the accuracy of silkworm feeding in the basic area corresponding to the convex hull area of the area type is improved.

As an optional scheme, determining, according to the obtained position information of the key position, a convex hull boundary matched with the region type includes:

s1, acquiring the key position with the minimum coordinate value indicated by the position information in the area type as a second reference origin;

s2, connecting other key positions in the region type with a second reference origin respectively to obtain corresponding connecting lines, and obtaining included angles between the connecting lines and a preset transverse axis passing through the second reference origin;

s3, sorting according to the included angle;

and S4, sequentially determining whether the key positions in the region types are target positions located on the convex hull boundary according to the sequence.

Specifically, the following example is used to explain that the acquired key positions belonging to the same area type are key position 0-key position 12 shown in fig. 6. Assume that key position 1 at which the coordinate value indicated by the position information is minimum is acquired as the second reference origin.

It should be noted that the second reference origin in this embodiment does not have a necessary association relationship with the first reference origin in the above embodiment, that is, the two may be the same key position or different key positions, which is not limited in this embodiment.

Specifically, other key positions (namely key position 0, and key position 2-key position 12) in the region type are respectively connected with the second reference origin to obtain corresponding connecting lines, and an included angle between each connecting line and a preset transverse axis passing through the second reference origin is obtained; sorting according to the size of the included angle; and sequentially determining whether the key positions in the region types are target positions located on the convex hull boundary according to the sequence.

For example, as shown in fig. 6, when all the acquired included angles are forward included angles, the included angles may be, but are not limited to, key position 2, key position 3 …, key position 12, and key position 0 in the above order.

Through the embodiment that this application provided, confirm the order that is used for judging convex closure boundary according to the size of contained angle to guarantee the reasonable order of judgement, and then reach the effect that improves the acquisition efficiency who acquires convex closure boundary.

As an optional scheme, sequentially determining whether the key positions in the region types are target positions located on the convex hull boundary according to the sorting includes:

s1, repeatedly executing the following steps until all the key positions in the region type are traversed according to the sorting:

s12, acquiring a first vector formed by a first key position adjacent to the current key position and the current key position, and a second vector formed by the current key position and a second key position adjacent to the current key position, wherein the first key position is positioned in front of the current key position according to the sequence, and the second key position is positioned behind the current key position according to the sequence;

and S14, obtaining a vector product between the first vector and the second vector by taking the current key position as a vertex, and judging whether the current key position is a target position on the convex hull boundary according to the vector included angle in the same direction.

Optionally, in this embodiment, the determining, according to the vector included angle, whether the current key position is a target position located on the convex hull boundary includes:

1) when the vector product is positive, judging that the current key position is a target position on the convex hull boundary, and taking a second key position adjacent to the current key position as a next current key position;

2) and when the vector product is negative, judging that the current key position is not the target position on the convex hull boundary, eliminating the current key position, acquiring the position information of the key position after elimination in the region type, and taking the previous key position adjacent to the eliminated key position as the next current key position.

Specifically, with reference to the following example, assume that as shown in fig. 6, the current key position is key position 2, the first key position is key position 1, the second key position is key position 3, and the first key position 1 and the current key position 2 constitute a first vector

The current key position 2 and the second key position 3 constitute a second vector

And acquiring the vector product of the two vectors. If the vector product is judged to be positive, the current key position 2 is judged to be a target position on the convex hull boundary, and a second key position 3 adjacent to the current key position 2 is taken as a next current key position.

Further, the current key position is key position 3, the first key position is key position 2, the second key position is key position 4, and the first key position 2 and the current key position 3 form a first vector

Current key position 3 and second key positionSet 4 constitutes a second vector

And acquiring the vector product of the two vectors. Assuming that the vector product is judged to be negative, judging that the current key position 4 is not the target position located on the convex hull boundary, removing the current key position 4, and obtaining the position information of the key position after being removed in the region type, namely, the position information of the key position 4 is not included, and taking the previous key position 3 adjacent to the removed key position 4 as the next current key position, namely, the updated current key position is still the key position 3, the first key position is the key position 2, and the second key position is changed into the key position 5.

And continuing to judge whether the current key position belongs to the target position on the convex hull boundary. If the key position 5 does not meet the above judgment condition, the key position 5 is rejected, further, the key position 3 is still used as the updated current key position, the first key position is still the key position 2, and the second key position is changed to the key position 6.

According to the embodiment provided by the application, whether the key position in the acquired region type belongs to the target position on the convex hull boundary is judged by utilizing the principle that the vector included angle is homodromous, so that the convex hull boundary used for generating the electronic map can be accurately acquired.

As an optional scheme, a convex hull region covered by a convex hull boundary is subdivided to obtain a plurality of basic regions corresponding to the convex hull region:

s1, subdividing the convex hull area covered by the convex hull boundary according to triangulation to obtain a plurality of basic areas corresponding to the convex hull area, wherein the basic areas comprise: a triangular region.

Alternatively, in this embodiment, the triangulation may be, but is not limited to, Delaunay triangulation, that is, a network composed of only triangles and obtained by dividing polygons corresponding to convex hull regions, where the minimum angle is maximized, for example, the triangular regions obtained after the triangulation are shown in fig. 4.

Specifically, the following example is combined to describe, and the convex hull boundary is divided into two position sets; if the number of the key positions in the set is less than or equal to 3, connecting the key positions in the set, such as a straight line or a triangle; if the number of the key positions in the set is more than 3, the bisection is continued.

Further, backtracking and combining the position set after bisection, and repeatedly executing the following steps until all key positions are subdivided;

s1, finding two position sets which belong to the same level after bisection, obtaining the positions which are not combined currently and have the smallest vertical coordinate in the two position sets, and connecting the positions to form a boundary;

s2, taking the boundary as a base, obtaining a key position which has a coincident start point with one end of the base and is not combined in a position set, and forming a new triangle with the base;

s3, judging whether a fourth fixed point is in the circumscribed circle of the triangle;

s4, if yes, obtaining another position set, and forming a triangle by the key positions which have coincident start points with the other end of the bottom edge and are not combined;

and S5, if not, the triangle is split completely.

Through the embodiment provided by the application, more stable subdivision is realized through triangulation, so that the acquired basic area is more favorable for generating a map area in an electronic map, and the effect of improving the generation efficiency of the electronic map is achieved.

It should be noted that, for simplicity of description, the above-mentioned method embodiments are described as a series of acts or combination of acts, but those skilled in the art will recognize that the present invention is not limited by the order of acts, as some steps may occur in other orders or concurrently in accordance with the invention. Further, those skilled in the art should also appreciate that the embodiments described in the specification are preferred embodiments and that the acts and modules referred to are not necessarily required by the invention.

Through the above description of the embodiments, those skilled in the art can clearly understand that the method according to the above embodiments can be implemented by software plus a necessary general hardware platform, and certainly can also be implemented by hardware, but the former is a better implementation mode in many cases. Based on such understanding, the technical solutions of the present invention may be embodied in the form of a software product, which is stored in a storage medium (e.g., ROM/RAM, magnetic disk, optical disk) and includes instructions for enabling a terminal device (e.g., a mobile phone, a computer, a server, or a network device) to execute the method according to the embodiments of the present invention.

Example 2

According to an embodiment of the present invention, there is also provided an electronic map generating apparatus for implementing the electronic map generating method described above, as shown in fig. 7, the apparatus includes:

1) an obtaining unit 702, configured to obtain location information of key locations on block areas belonging to the same area type, where the block areas are areas obtained through collection and used for generating an electronic map, the key locations are located on boundaries of the block areas, and a distance between the block areas belonging to the same area type is smaller than a predetermined threshold;

2) a determining unit 704, configured to determine, according to the obtained position information of the key position, a convex hull boundary matched with the area type;

3) a subdivision unit 706, configured to subdivide a convex hull region covered by a convex hull boundary to obtain multiple basic regions corresponding to the convex hull region;

4) the generating unit 708 is configured to delete a target boundary in the base area according to a preset condition, and generate a map area corresponding to the area type by using the base area after the target boundary is deleted, where the electronic map includes one or more map areas.

Optionally, in this embodiment, the electronic map generation apparatus may be applied, but not limited to, to different client applications or Web applications, where the application may be an electronic map application, a navigation positioning application, or other applications that require displaying an electronic map. The above is only an example, and this is not limited in this embodiment.

As an optional solution, the generating unit 708 includes:

1) the first acquisition module is used for acquiring a key position from the convex hull boundary as a first reference origin;

2) the processing module is used for sequentially executing the following operations on boundaries which are positioned on a preset track in each boundary of the basic area by taking the first reference origin as a starting point, wherein the preset track is a dynamic track with a preset width;

s1, judging whether the current boundary meets the preset condition;

s2, when the current boundary meets the preset conditions, identifying the current boundary as a target boundary, deleting the target boundary, and acquiring an adjacent boundary which has a coincident starting point with the current boundary as a next current boundary in the preset track;

and S3, when the current boundary does not meet the preset condition, acquiring a boundary which is adjacent to the current boundary and has a coincident end point as a next current boundary in the preset track.

As an optional scheme, the processing module determines whether the current boundary meets a preset condition by:

Optionally, in this embodiment, the processing module is further configured to perform the following steps: before judging whether the current boundary meets a preset condition, dividing a boundary on a preset track in each boundary of a basic area into a plurality of sub-boundaries, wherein the preset track is a closed track; a current boundary is obtained from the plurality of sub-boundaries.

As an alternative, the determining unit 704 includes:

1) the second acquisition module is used for acquiring the key position with the minimum coordinate value indicated by the position information in the region type as a second reference origin;

2) the third acquisition module is used for respectively connecting other key positions in the region type with the second reference origin to obtain corresponding connecting lines and acquiring included angles between the connecting lines and a preset transverse shaft passing through the second reference origin;

3) the sorting module is used for sorting according to the size of the included angle;

4) and the determining module is used for sequentially judging whether the key positions in the region types are target positions located on the convex hull boundary according to the sequence.

As an optional solution, the determining module includes:

1) a processing submodule, configured to repeatedly perform the following steps until all key positions in the region type are traversed according to the ranking:

s1, acquiring a first vector formed by a first key position adjacent to the current key position and the current key position, and a second vector formed by the current key position and a second key position adjacent to the current key position, wherein the first key position is positioned in front of the current key position according to the sequence, and the second key position is positioned behind the current key position according to the sequence;

and S2, obtaining a vector product between the first vector and the second vector by taking the current key position as a vertex, and judging whether the current key position is a target position on the convex hull boundary according to the vector included angle in the same direction.

Optionally, in this embodiment, the processing sub-module performs equidirectional judgment on whether the current key position is the target position located on the convex hull boundary according to the vector included angle by: when the vector product is positive, judging that the current key position is a target position on the convex hull boundary, and taking a second key position adjacent to the current key position as a next current key position; and when the vector product is negative, judging that the current key position is not the target position on the convex hull boundary, eliminating the current key position, acquiring the position information of the key position after elimination in the region type, and taking the previous key position adjacent to the eliminated key position as the next current key position.

The current key position 3 and the second key position 4 constitute a second vector

As an optional scheme, the subdivision unit 706 includes:

1) the subdivision module is used for subdividing a convex hull area covered by a convex hull boundary according to triangulation to obtain a plurality of basic areas corresponding to the convex hull area, wherein the basic areas comprise: a triangular region.

and S5, if not, the triangle is split completely.

Example 3

According to an embodiment of the present invention, there is also provided an electronic map generating server for implementing the electronic map generating method, as shown in fig. 8, the server includes:

1) a communication interface 802 configured to acquire position information of key positions on block areas belonging to the same area type, where the block areas are areas for generating an electronic map acquired through acquisition, the key positions are located on boundaries of the block areas, and a distance between the block areas belonging to the same area type is smaller than a predetermined threshold;

2) the processor 804 is connected with the communication interface 802 and is configured to determine a convex hull boundary matched with the region type according to the acquired position information of the key position; the method also comprises the steps of dividing a convex hull area covered by the convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area; and deleting a target boundary in the basic area according to a preset condition, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas.

3) The memory 806 is connected to the communication interface 802 and the processor 804, and is configured to store the block area, the map area, and the electronic map.

Optionally, the specific examples in this embodiment may refer to the examples described in embodiment 1 and embodiment 2, and this embodiment is not described herein again.

Example 4

The embodiment of the invention also provides a storage medium. Optionally, in this embodiment, the storage medium may be located in at least one of a plurality of network devices in a network.

Optionally, in this embodiment, the storage medium is configured to store program code for performing the following steps:

s1, acquiring position information of key positions on block areas belonging to the same area type, wherein the block areas are acquired areas used for generating an electronic map, the key positions are located on the boundaries of the block areas, and the distance between the block areas belonging to the same area type is smaller than a preset threshold value;

s2, determining a convex hull boundary matched with the region type according to the acquired position information of the key position;

s3, subdividing a convex hull area covered by a convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area;

and S4, deleting the target boundary in the basic area according to preset conditions, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas.

Optionally, in this embodiment, the storage medium may include, but is not limited to: a U-disk, a Read-Only Memory (ROM), a Random Access Memory (RAM), a removable hard disk, a magnetic or optical disk, and other various media capable of storing program codes.

The above-mentioned serial numbers of the embodiments of the present invention are merely for description and do not represent the merits of the embodiments.

The integrated unit in the above embodiments, if implemented in the form of a software functional unit and sold or used as a separate product, may be stored in the above computer-readable storage medium. Based on such understanding, the technical solution of the present invention may be embodied in the form of a software product, which is stored in a storage medium and includes several instructions for causing one or more computer devices (which may be personal computers, servers, network devices, etc.) to execute all or part of the steps of the method according to the embodiments of the present invention.

In the above embodiments of the present invention, the descriptions of the respective embodiments have respective emphasis, and for parts that are not described in detail in a certain embodiment, reference may be made to related descriptions of other embodiments.

In the several embodiments provided in the present application, it should be understood that the disclosed client may be implemented in other manners. The above-described embodiments of the apparatus are merely illustrative, and for example, the division of the units is only one type of division of logical functions, and there may be other divisions when actually implemented, for example, a plurality of units or components may be combined or may be integrated into another system, or some features may be omitted, or not executed. In addition, the shown or discussed mutual coupling or direct coupling or communication connection may be an indirect coupling or communication connection through some interfaces, units or modules, and may be in an electrical or other form.

The units described as separate parts may or may not be physically separate, and parts displayed as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the units can be selected according to actual needs to achieve the purpose of the solution of the embodiment.

In addition, functional units in the embodiments of the present invention may be integrated into one processing unit, or each unit may exist alone physically, or two or more units are integrated into one unit. The integrated unit can be realized in a form of hardware, and can also be realized in a form of a software functional unit.

The foregoing is only a preferred embodiment of the present invention, and it should be noted that, for those skilled in the art, various modifications and decorations can be made without departing from the principle of the present invention, and these modifications and decorations should also be regarded as the protection scope of the present invention.

Claims

1. An electronic map generation method, comprising:

acquiring position information of key positions on block areas belonging to the same area type, wherein the block areas are acquired areas used for generating an electronic map, the key positions are located on the boundaries of the block areas, and the distance between the block areas belonging to the same area type is smaller than a preset threshold value;

performing recursive test on the acquired position information of the key position according to the vector included angle in the same direction to determine a convex hull boundary matched with the region type;

subdividing a convex hull area covered by the convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area;

deleting a target boundary in the basic area according to a preset condition, and generating a map area corresponding to the area type by using the basic area after the target boundary is deleted, wherein the electronic map comprises one or more map areas, the target boundary is a boundary which is positioned on a preset track in each boundary of the basic area, the preset track is a dynamic track with a preset width, and the preset condition is used for indicating the relation between the preset width and the length of the target boundary and the length of an adjacent boundary which has a coincident starting point with the target boundary.

2. The method according to claim 1, wherein the deleting the target boundary in the base area according to a preset condition comprises:

acquiring a key position from the convex hull boundary as a first reference origin;

sequentially executing the following operations on boundaries located on the preset track in each boundary of the basic area by taking the first reference origin as a starting point;

judging whether the current boundary meets the preset condition or not;

when the current boundary meets the preset condition, identifying the current boundary as the target boundary, deleting the target boundary, and acquiring an adjacent boundary which has a coincident starting point with the current boundary as a next current boundary in the preset track;

and when the current boundary does not meet the preset condition, acquiring a boundary which is adjacent to the current boundary and has a coincident end point as a next current boundary in the preset track.

3. The method according to claim 2, wherein the determining whether the current boundary satisfies the preset condition comprises:

judging whether the preset width of the preset track is smaller than the length of the current boundary;

when the preset width is smaller than the length of the current boundary, judging that the current boundary meets the preset condition;

when the preset width is larger than or equal to the length of the current boundary, judging whether the preset width is larger than the length of an adjacent boundary which has a coincident starting point with the current boundary;

when the preset width is larger than the length of an adjacent boundary with a coincident starting point with the current boundary, judging that the current boundary meets the preset condition; when the predetermined width is smaller than the length of an adjacent boundary having a coincident start point with the current boundary, determining that the current boundary does not satisfy the preset condition.

4. The method according to claim 2, before said determining whether the current boundary satisfies the preset condition, further comprising:

dividing boundaries located on the preset track in each boundary of the basic area into a plurality of sub-boundaries, wherein the preset track is a closed track;

obtaining the current boundary from the plurality of sub-boundaries.

5. The method according to claim 1, wherein the performing a recursive test on the acquired position information of the key position according to a vector included angle in the same direction to determine a convex hull boundary matched with the region type includes:

acquiring a key position with the minimum coordinate value indicated by the position information in the area type as a second reference origin;

respectively connecting other key positions in the region type with the second reference origin to obtain corresponding connecting lines, and obtaining included angles between the connecting lines and a preset transverse axis passing through the second reference origin;

sorting according to the size of the included angle;

and sequentially determining whether the key positions in the region types are target positions located on the convex hull boundary according to the sequence.

6. The method of claim 5, wherein the sequentially determining whether the key locations in the region types are target locations located on the convex hull boundary according to the ordering comprises:

repeatedly executing the following steps until all the key positions in the region types are traversed according to the sorting:

acquiring a first vector formed by a first key position adjacent to a current key position and the current key position, and a second vector formed by the current key position and a second key position adjacent to the current key position, wherein the first key position is positioned in front of the current key position according to the sequence, and the second key position is positioned behind the current key position according to the sequence;

and acquiring a vector product between the first vector and the second vector by taking the current key position as a vertex, and judging whether the current key position is a target position on the convex hull boundary according to the vector included angle in the same direction.

7. The method according to claim 6, wherein said determining whether the current key position is a target position located on the convex hull boundary according to a vector included angle in a same direction comprises:

when the vector product is positive, judging that the current key position is the target position on the convex hull boundary, and taking the second key position adjacent to the current key position as the next current key position;

and when the vector product is negative, judging that the current key position is not the target position on the convex hull boundary, eliminating the current key position, acquiring the position information of the key position after elimination in the region type, and taking the previous key position adjacent to the eliminated key position as the next current key position.

8. The method of claim 1, wherein the subdividing the convex hull region covered by the convex hull boundary to obtain a plurality of base regions corresponding to the convex hull region comprises:

subdividing a convex hull region covered by the convex hull boundary according to triangulation to obtain a plurality of basic regions corresponding to the convex hull region, wherein the basic regions comprise: a triangular region.

9. An electronic map generation apparatus, comprising:

an obtaining unit, configured to obtain location information of key locations on block areas belonging to a same area type, where the block areas are areas obtained through collection and used for generating an electronic map, the key locations are located on boundaries of the block areas, and a distance between the block areas belonging to the same area type is smaller than a predetermined threshold;

the determining unit is used for carrying out recursive testing on the acquired position information of the key position according to the vector included angle in the same direction so as to determine a convex hull boundary matched with the region type;

the subdivision unit is used for subdividing the convex hull area covered by the convex hull boundary to obtain a plurality of basic areas corresponding to the convex hull area;

the generation unit is configured to delete a target boundary in the basic area according to a preset condition, and generate a map area corresponding to the area type by using the basic area from which the target boundary is deleted, where the electronic map includes one or more map areas, the target boundary is a boundary located on a preset trajectory in each boundary of the basic area, the preset trajectory is a dynamic trajectory having a predetermined width, and the preset condition is used to indicate a relationship between the predetermined width and a length of the target boundary and a length of an adjacent boundary having a coincident start point with the target boundary.

10. The apparatus of claim 9, wherein the generating unit comprises:

the first acquisition module is used for acquiring a key position from the convex hull boundary as a first reference origin;

the processing module is used for sequentially executing the following operations on boundaries which are positioned on a preset trajectory in each boundary of the basic area by taking the first reference origin as a starting point, wherein the preset trajectory is a dynamic trajectory with a preset width;

judging whether the current boundary meets the preset condition or not;

11. The apparatus of claim 10, wherein the processing module determines whether the current boundary satisfies the preset condition by:

12. The apparatus of claim 10, wherein the processing module is further configured to perform the steps of:

before the current boundary is judged to meet the preset condition, dividing the boundary on the preset track in each boundary of the basic area into a plurality of sub-boundaries, wherein the preset track is a closed track;

obtaining the current boundary from the plurality of sub-boundaries.

13. The apparatus of claim 9, wherein the determining unit comprises:

a second obtaining module, configured to obtain, as a second reference origin, a key position at which a coordinate value indicated by the position information in the area type is minimum;

a third obtaining module, configured to connect other key positions in the region type and the second reference origin point respectively, obtain corresponding connection lines, and obtain an included angle between each connection line and a predetermined horizontal axis passing through the second reference origin point;

the sorting module is used for sorting according to the size of the included angle;

and the determining module is used for sequentially judging whether the key positions in the region types are target positions located on the convex hull boundary according to the sequence.

14. The apparatus of claim 13, wherein the means for determining comprises:

a processing sub-module, configured to repeatedly perform the following steps until all the key positions in the region type are traversed according to the ranking:

15. The apparatus according to claim 14, wherein the processing sub-module performs homodromous determination of whether the current key position is a target position located on the convex hull boundary according to a vector included angle by:

16. The apparatus of claim 9, wherein the subdivision unit comprises:

a subdivision module, configured to subdivide, according to triangulation, a convex hull region covered by the convex hull boundary to obtain a plurality of basic regions corresponding to the convex hull region, where the basic regions include: a triangular region.