[go: up one dir, main page]

CN104573396A - Generation algorithm of least independent closed loops and shortest annexed lines for leveling network - Google Patents

Generation algorithm of least independent closed loops and shortest annexed lines for leveling network Download PDF

Info

Publication number
CN104573396A
CN104573396A CN201510044832.8A CN201510044832A CN104573396A CN 104573396 A CN104573396 A CN 104573396A CN 201510044832 A CN201510044832 A CN 201510044832A CN 104573396 A CN104573396 A CN 104573396A
Authority
CN
China
Prior art keywords
route
leveling
line
algorithm
shortest
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Pending
Application number
CN201510044832.8A
Other languages
Chinese (zh)
Inventor
王斌
刘晓芸
赵大江
张世娟
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Center For Geodetic Data Processing National Administration Of Surveying Mapping And Geoinformation
Original Assignee
Center For Geodetic Data Processing National Administration Of Surveying Mapping And Geoinformation
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Center For Geodetic Data Processing National Administration Of Surveying Mapping And Geoinformation filed Critical Center For Geodetic Data Processing National Administration Of Surveying Mapping And Geoinformation
Priority to CN201510044832.8A priority Critical patent/CN104573396A/en
Publication of CN104573396A publication Critical patent/CN104573396A/en
Pending legal-status Critical Current

Links

Landscapes

  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

The invention provides a generation algorithm of least independent closed loops and shortest annexed lines for a leveling network. The algorithm includes the step of using ends of each leveling line as nodal points and other middle points as transitional points; storing the leveling lines in a two-dimensional array; distinguishing the different lines identical in nodal point and cumulative-sum distance; uniformly numbering nodal points of the leveling network; dividing the lines into independent connected sub-networks according to the nodal point adjacency feature, searching the sub-networks for the least independent closed loops and the shortest annexed lines; adjusting the directions of the closed loops to ensure that all loops of the leveling network are clockwise or anticlockwise. Compared with the traditional techniques, the algorithm has the advantages that the structure is simple, an algorithm idea is clear, a program developed on the basis of the algorithm runs fast, the closed loops are ensured being least, the annexed lines are ensured being shortest, the closed loops and the annexed lines are mutually independent and complete, closure conditions are omission free and non-redundant, the closed loops are all uniformly clockwise or anticlockwise, efficiency is improved, cost is saved, and synergy is achieved.

Description

Leveling network independence minimal closure ring, the shortlyest conform to line generating algorithm
Technical field
The present invention relates to geodetic surveying leveling data processing technology field, particularly a kind of leveling network independence minimal closure ring, the shortlyest conform to line generating algorithm.
Background technology
Measurement of the level, is the method measuring the ground point-to-point transmission discrepancy in elevation with spirit-leveling instrument and levelling staff, take sea level as benchmark, measure the absolute altitude of object.It is the main method of the measurement of higher degree, for setting up national leveling network, and the land subsidence that monitoring radial diastrophism and artificial origin cause, and set up the vertical control network required for engineering survey.
Along with socioeconomic development, the progress of scientific and technological level, require more and more higher, due to measurement of the level Instrumental Errors, observational error and external influence, make inevitably to there is error in measurement of the level, mis-tie is exactly the concentrated expression of each error effect in measurement of the level observational error, and calculating the loop closure of leveling network and conform to line mis-tie, is the important means of leveling network data validation.
For simply small-sized leveling network, can manually form closed hoop, conform to line, but in current prior art, for having the large-scale national level-control net of hundreds of routes or the complicated in disorder local leveling network of net type, if employing manual work, then workload is very large, and the closed hoop found out, conforms to whether line is independent completely again also cannot ensure.
Summary of the invention
Leveling work amount for leveling network in prior art is very large, quality cannot ensure and above-mentioned defect with high costs and problem, the object of the embodiment of the present invention is to provide a kind of better leveling network independence minimal closure ring, the shortlyest conforms to line generating algorithm, thinking is simple and clear, be easy to realize, result accurately and reliably, duty cycle can be shortened, no longer need a large amount of manual work, greatly reduce cost.
In order to achieve the above object, the embodiment of the present invention provides following technical scheme:
A kind of leveling network independence minimal closure ring, the shortlyest conform to line generating algorithm, it is characterized in that, step is as follows:
Q1: the end points at leveling line two ends is called node, is called transition point by other intermediate point of leveling line;
Q2: leveling line is stored into a two-dimensional array;
The same for two leafs, tired and distance different routes are too distinguished, to route spacing from adding a numerical value by Q3: do trial inspection and process to route;
Q4: to node Unified number in leveling network, is provided with M node, numbers from 1 to M; Then set up that M is capable, the array of M row, and give all array element assignment 9999; Finally route information is assigned to array, have observation route between two nodes being namely wherein numbered I, J, its length is S, then two elements (I, J), (J, I) all assignment S in array, when there being the route that many two leafs are the same, then getting distance reckling and participate in matrixing;
Q5: these routes are divided into the little net of independent connection one by one by the adjacent feature of node, less net is searched for one by one, find out its independent minimal closure ring and the shortest line that conforms to; The algorithm of region growing in Remote Sensing Image Segmentation is copied in the independent division being communicated with little net, get a route do not divided into little net is at random seed at every turn, the route that route two-end-point is connected therewith is incorporated to this little net, go to merge other adjacent paths with the route end points be newly incorporated to again, continuous expansion, until all adjacent paths are incorporated to a network; Reselect new seed again, repeat this operation, repeatedly carry out, until all routes are divided into each net from childhood;
Q6: closed hoop adjustment direction:
Q61: combing forms each closed hoop, conforms to the route direction of line, ensures that all route nodes of a composition closure condition are end to end, gives and needs reverse route wire size to add negative sign; The clockwise trend of utilization is moved towards with the contrary feature adjustment ring of area of a polygon sign moving towards to calculate counterclockwise, ensures that all rings of leveling network are clockwise or counterclockwise.
Preferred as technique scheme, the automatic generating calculation finding out the independent all least independent close loops be communicated with in leveling network in described Q5 step is that step is as follows:
Q511: search minimum spanning tree based on the matrix formed in above-mentioned steps Q4, composition is removed: the route of minimum spanning tree in all routes obtained in Q5 step, namely remaining route is redundant observation route, and a redundant observation route represents and can form a closed hoop;
Q512: generate a matrix G by minimum spanning tree, find the shortest path of all redundant observation route two-end-points in matrix G one by one, composition closed hoop, to wherein export by minimal closure ring, and redundant observation route is put back to matrix G, length by this redundant observation route is assigned to element corresponding with its node in matrix G, deletes from redundant observation route simultaneously; Repeatedly search for, put back to, delete, until redundant observation route becomes sky.
Preferred as technique scheme, finding out the independent the shortest automatic generating calculation conforming to line be communicated with in leveling network in described Q5 step is that step is as follows:
Q521: the length obtaining shortest path between often pair of node with Freud's algorithm,
Q522: take out separately Fixed Initial Point composition matrix, matrix element value is the length of the shortest path between corresponding two Fixed Initial Points,
Q523: then search for minimum spanning tree on this matrix basis, this minimum spanning tree is exactly that the shortest line that conforms to of total length combines,
Q524: obtain the shortest path in the figure that this minimum spanning tree every bar branch two-end-point formed at leveling line.
Preferred as technique scheme, when trial inspection being done with process to route in described Q3 step, ensure that different route spacings that two leafs are the same are from different, make node, distance uniquely can represent a route, notice that route does not distinguish direction, namely the route of starting point A terminal B is considered as the same route of node with the route of starting point B terminal A.
Preferred as technique scheme, described Q4 step application in special graph-theoretical algorithm search closed hoop, conform to line.
Preferred as technique scheme, the M in described Q4 step be greater than 1 natural number; I, J are the natural number between 1-M.
A kind of leveling network independence minimal closure ring that the embodiment of the present invention provides, the shortlyest conform to line generating algorithm, compared with traditional technology, structure is simple, algorithm clear thinking, program operation speed based on this algorithm development is fast, can ensure that closed hoop is minimum, it is the shortest and separate complete again to conform to line simultaneously, closure condition is not omitted not unnecessary, automatic generation leveling network independence minimal closure ring, the shortest line that conforms to, ensure that all closed hoops trend is consistent, be clockwise or counterclockwise, raise the efficiency, cost-saving, reach the object of synergy.
Accompanying drawing explanation
In order to be illustrated more clearly in the embodiment of the present invention or technical scheme of the prior art, be briefly described to the accompanying drawing used required in embodiment or description of the prior art below, apparently, accompanying drawing in the following describes is only some embodiments of the present invention, for those of ordinary skill in the art, under the prerequisite not paying creative work, other accompanying drawing can also be obtained according to these accompanying drawings.
Fig. 1 is a kind of leveling network independence minimal closure ring of the embodiment of the present invention 1, the shortest schematic diagram conforming to line generating algorithm.
Embodiment
Below in conjunction with accompanying drawing of the present invention, be clearly and completely described technical scheme of the present invention, obviously, described embodiment is only the present invention's part embodiment, instead of whole embodiments.Based on the embodiment in the present invention, those of ordinary skill in the art, not making the every other embodiment obtained under creative work prerequisite, belong to the scope of protection of the invention.
Minimum spanning tree: in a connected graph G, if get its whole summit and a part of limit forms a subgraph g, if the limit in g will being communicated with a little and not forming loop in figure G, then title subgraph g is a spanning tree of former figure G; If all limits weights sum in this spanning tree is minimum in spanning tree, then this spanning tree is claimed to be the minimum spanning tree of figure.
Shortest path: on the paths in figure between two inequality summits the limit weights sum of process be defined as the cum rights path in this path, and the more than paths of possibility between two summits, that the shortest for cum rights path paths is called shortest path.
Embodiment 1
The Graph Analysis of 1 leveling network
The end points at leveling line two ends is called node, other intermediate point of leveling line is called transition point.
The essence of figure is exactly a two-dimensional matrix, so leveling network " figure " is changed, namely changed by its " matrix ", and matrix stores with array form in a computer, so need leveling line to be stored into a two-dimensional array.
Before by route matrixing, need to do trial inspection and process to route, the same for two leafs, tired and distance different routes are too distinguished, to route spacing from adding a numerical value, ensure that different route spacings that two leafs are the same are from different, make node, distance uniquely can represent a route, notice that route does not distinguish direction, namely the route of starting point A terminal B is considered as the same route of node with the route of starting point B terminal A.
First by node Unified number in leveling network, suppose there be M node, number from 1 to M; Then set up that M is capable, the array of M row, and give all array element assignment 9999; Finally route information is assigned to array, such as, there is observation route between two nodes being numbered I, J, its length is S, then (I, J), (J, I) two element assignment S in array, if there is the route that many two leafs are the same, then get distance reckling and participate in matrixing. after a few like this step operation, leveling network has just been changed by " figure ", can apply special graph-theoretical algorithm search closed hoop, conform to line.
2 are independently communicated with sub-network division
Because the figure of an all leveling line composition of project is not sometimes a connected graph in actual job, cannot directly apply minimum spanning tree, shortest path first, so these routes must be divided into the little net of independent connection one by one by the adjacent feature of node, again little net is searched for one by one, find out its independent minimal closure ring and the shortlyest conform to line.The independent division being communicated with little net can copy the algorithm of region growing in Remote Sensing Image Segmentation, get a route do not divided into little net is at random seed at every turn, the route that route two-end-point is connected therewith is incorporated to this little net, go to merge other adjacent paths with the route end points be newly incorporated to again, constantly expand, until all adjacent paths are incorporated to a network, reselect new seed again, repeat operation above, repeatedly carry out, all routes are divided into each net from childhood.
The automatic generating calculation of 3 least independent close loops
So, how to find out the independent all least independent close loops be communicated with in leveling network? first matrix is converted it into, then minimum spanning tree is searched based on the matrix formed, the route of composition minimum spanning tree is removed in all routes, remaining route is exactly excess observation component, also all redundant observation routes can be called cotree, wherein each route is called remaining branch, and a redundant observation route represents and can form a closed hoop.
A matrix G is generated by minimum spanning tree, one by one find the shortest path of route two-end-point in matrix G of having a surplus, composition closed hoop, to wherein export by minimal closure ring, and corresponding remaining branch is put back to matrix G, length by this redundant observation route is assigned to element corresponding with its node in matrix G, deletes from cotree simultaneously; Repeatedly search for, put back to, delete, until cotree becomes sky.
The 4 the shortest automatic generating calculations conforming to line
First the length of shortest path between often pair of node is obtained with Freud's algorithm, then Fixed Initial Point composition matrix is taken out separately, matrix element value is the shortest path length between corresponding two Fixed Initial Points, then on this matrix basis, minimum spanning tree is searched for, this minimum spanning tree be exactly total length the shortest conform to line combination, the shortest path that last demand goes out in the figure that this minimum spanning tree every bar branch two-end-point formed at leveling line specifically forms just passable.
5 closed hoop adjustment direction
Combing forms each closed hoop, conforms to the route direction of line, ensures that all route nodes of a composition closure condition are end to end, gives and needs reverse route wire size to add negative sign.Data cases is analyzed for the ease of operator, need all closed hoops to be to move towards clockwise or counterclockwise, and ring trend is random before this, so how realize closed hoop and move towards consistent? arbitrary polygon areal calculation formula (with reference to Geographic Information System class of algorithms books) can be utilized to realize this target, clockwise trend is contrary with the area of a polygon sign moving towards to calculate counterclockwise, so can adjustment ring move towards according to this character, ensure that all rings of leveling network are clockwise or counterclockwise.
As shown in Figure 1, present embodiments provide program that certain true leveling network utilizes this algorithm to write and automatically can generate 13 closed hoops, 1 AIT conforming to line, wherein closed hoop trend is clockwise, closed hoop, conforms to line attribute information and sees the following form:
Ring number: represent the numbering conforming to line, closed hoop.
Starting point, stop: represent current and conform to line, the starting point of closed hoop and stop.If conform to line, then starting point, stop are different, and are Fixed Initial Point; If closed hoop, then starting point, stop are the same, for forming the end points of certain route in this ring.
Mis-tie: if conform to line is then that this conforms to the difference of line two ends Fixed Initial Point elevation, with this conform to line comprise the discrepancy in elevation of route tired and difference; If closed hoop, then for this closed hoop comprise the discrepancy in elevation of route tired and.
It is poor to limit: by the formula in specification calculate conform to line, closed hoop limit poor, wherein F is coefficient, and different brackets numerical value is different, and K is for conforming to line, closed hoop route total length.
Ring is long: form the current all path length sums conforming to line, closed hoop.
Closed hoop, conform to the composition route of line: represent the current route number conforming to line, closed hoop of composition, if route number has added negative sign, then when illustrating that this route participates in calculating mis-tie, the discrepancy in elevation needs opposite sign.
The above; be only the specific embodiment of the present invention, but protection scope of the present invention is not limited thereto, is anyly familiar with those skilled in the art in the technical scope that the present invention discloses; change can be expected easily or replace, all should be encompassed within protection scope of the present invention.Therefore, protection scope of the present invention should described be as the criterion with the protection domain of claim.

Claims (6)

1. leveling network independence minimal closure ring, the shortlyest conform to a line generating algorithm, it is characterized in that, step is as follows:
Q1: the end points at leveling line two ends is called node, is called transition point by other intermediate point of leveling line;
Q2: leveling line is stored into a two-dimensional array;
The same for two leafs, tired and distance different routes are too distinguished, to route spacing from adding a numerical value by Q3: do trial inspection and process to route;
Q4: to node Unified number in leveling network, is provided with M node, numbers from 1 to M; Then set up that M is capable, the array of M row, and give all array element assignment 9999; Finally route information is assigned to array, have observation route between two nodes being namely wherein numbered I, J, its length is S, then two elements (I, J), (J, I) all assignment S in array, when there being the route that many two leafs are the same, then getting distance reckling and participate in matrixing;
Q5: these routes are divided into the little net of independent connection one by one by the adjacent feature of node, less net is searched for one by one, find out its independent minimal closure ring and the shortest line that conforms to; The algorithm of region growing in Remote Sensing Image Segmentation is copied in the independent division being communicated with little net, get a route do not divided into little net is at random seed at every turn, the route that route two-end-point is connected therewith is incorporated to this little net, go to merge other adjacent paths with the route end points be newly incorporated to again, continuous expansion, until all adjacent paths are incorporated to a network; Reselect new seed again, repeat this operation, repeatedly carry out, until all routes are divided into each net from childhood;
Q6: closed hoop adjustment direction:
Q61: combing forms each closed hoop, conforms to the route direction of line, ensures that all route nodes of a composition closure condition are end to end, gives and needs reverse route wire size to add negative sign; The clockwise trend of utilization is moved towards with the contrary feature adjustment ring of area of a polygon sign moving towards to calculate counterclockwise, ensures that all rings of leveling network are clockwise or counterclockwise.
2. a kind of leveling network independence minimal closure ring according to claim 1, the shortlyest conform to line generating algorithm, it is characterized in that, the automatic generating calculation finding out the independent all least independent close loops be communicated with in leveling network in described Q5 step is that step is as follows:
Q511: search minimum spanning tree based on the matrix formed in above-mentioned steps Q4, composition is removed: the route of minimum spanning tree in all routes obtained in Q5 step, namely remaining route is redundant observation route, and a redundant observation route represents and can form a closed hoop;
Q512: generate a matrix G by minimum spanning tree, find the shortest path of all redundant observation route two-end-points in matrix G one by one, composition closed hoop, to wherein export by minimal closure ring, and redundant observation route is put back to matrix G, length by this redundant observation route is assigned to element corresponding with its node in matrix G, deletes from redundant observation route simultaneously; Repeatedly search for, put back to, delete, until redundant observation route becomes sky.
3. a kind of leveling network independence minimal closure ring according to claim 1, the shortlyest conform to line generating algorithm, it is characterized in that, finding out the independent the shortest automatic generating calculation conforming to line be communicated with in leveling network in described Q5 step is that step is as follows:
Q521: the length obtaining shortest path between often pair of node with Freud's algorithm,
Q522: take out separately Fixed Initial Point composition matrix, matrix element value is the length of the shortest path between corresponding two Fixed Initial Points,
Q523: then search for minimum spanning tree on this matrix basis, this minimum spanning tree is exactly that the shortest line that conforms to of total length combines,
Q524: obtain the shortest path in the figure that this minimum spanning tree every bar branch two-end-point formed at leveling line.
4. a kind of leveling network independence minimal closure ring according to claim 1, the shortlyest conform to line generating algorithm, it is characterized in that, when trial inspection being done with process to route in described Q3 step, ensure that different route spacings that two leafs are the same are from different, make node, distance uniquely can represent a route, notice that route does not distinguish direction, namely the route of starting point A terminal B is considered as the same route of node with the route of starting point B terminal A.
5. a kind of leveling network independence minimal closure ring according to claim 1, the shortlyest conform to line generating algorithm, it is characterized in that, described Q4 step application in special graph-theoretical algorithm search closed hoop, conform to line.
6. a kind of leveling network independence minimal closure ring according to claim 1, the shortlyest conform to line generating algorithm, it is characterized in that, the M in described Q4 step be greater than 1 natural number; I, J are the natural number between 1-M.
CN201510044832.8A 2015-01-27 2015-01-27 Generation algorithm of least independent closed loops and shortest annexed lines for leveling network Pending CN104573396A (en)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN201510044832.8A CN104573396A (en) 2015-01-27 2015-01-27 Generation algorithm of least independent closed loops and shortest annexed lines for leveling network

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN201510044832.8A CN104573396A (en) 2015-01-27 2015-01-27 Generation algorithm of least independent closed loops and shortest annexed lines for leveling network

Publications (1)

Publication Number Publication Date
CN104573396A true CN104573396A (en) 2015-04-29

Family

ID=53089442

Family Applications (1)

Application Number Title Priority Date Filing Date
CN201510044832.8A Pending CN104573396A (en) 2015-01-27 2015-01-27 Generation algorithm of least independent closed loops and shortest annexed lines for leveling network

Country Status (1)

Country Link
CN (1) CN104573396A (en)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109579859A (en) * 2018-05-10 2019-04-05 北京建筑大学 A kind of high-precision navigation map altitude data processing method and processing device

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN201327389Y (en) * 2008-12-15 2009-10-14 上海建浩工程顾问有限公司 Super high-rise building plane surveying control network vertical transmitting and segmenting system
CN103727920A (en) * 2013-12-27 2014-04-16 湖北省水利水电规划勘测设计院 Method of measuring level elevation difference based on geoid model

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN201327389Y (en) * 2008-12-15 2009-10-14 上海建浩工程顾问有限公司 Super high-rise building plane surveying control network vertical transmitting and segmenting system
CN103727920A (en) * 2013-12-27 2014-04-16 湖北省水利水电规划勘测设计院 Method of measuring level elevation difference based on geoid model

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
刘晓云 等: "水准网闭合环自动生成技术的研究", 《测绘技术装备》 *

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN109579859A (en) * 2018-05-10 2019-04-05 北京建筑大学 A kind of high-precision navigation map altitude data processing method and processing device

Similar Documents

Publication Publication Date Title
KR102067459B1 (en) Auto correcting system the error according to editting the reference position on digital map
CN111707238B (en) Method and system for generating aviation digital orthophoto map
CN109033538B (en) A method for calculating permeability tensor of fractured rock mass based on measured structural plane parameters
CN104050237B (en) A kind of road mapping method and system
KR101090925B1 (en) methodology of GIS based accurate centerline map drawing support system using digital maps for stream and road
CN109579859B (en) A high-precision navigation map elevation data processing method and device
CN106600661B (en) The method for accurately generating segmental arc geologic section
CN112084289B (en) Track fusion method and device
Molnár et al. Can the First Military Survey maps of the Habsburg Empire (1763–1790) be georeferenced by an accuracy of 200 meters
CN103196425A (en) Estimation method of extra-long tunnel horizontal through error
Gagliolo et al. 3D cultural heritage documentation: A comparison between different photogrammetric software and their products
CN103902343A (en) Tile map downloading and splicing method based on Delaunay triangulation network accuracy control
CN107369373B (en) A method of composite mapping is carried out using multi-scale line feature map
CN104573396A (en) Generation algorithm of least independent closed loops and shortest annexed lines for leveling network
Fenton et al. Transverse aeolian ridge growth mechanisms and pattern evolution in Scandia Cavi, Mars
CN102607513A (en) Method for carrying out quasigeoid refining on superlarge region on basis of seamless partitioning technology
CN111651711A (en) Geological exploration drilling geospatial data coordinate conversion method
CN105224748B (en) A kind of section preprocess method of non-uniform beam finite element model
CN104596443A (en) Light plane equation fitting locating calibration method based on inherent characteristics of three-line laser
Gösseln et al. Change detection and integration of topographic updates from ATKIS to geoscientific data sets
Wang et al. An integrated method for calculating DEM-based RUSLE LS
Barkund et al. Survey of shortest path algorithms
JP6902763B1 (en) Drone flight planning system and program
Hron et al. Automatic Generation of 3D building models from point clouds
Matrood et al. A simple gis based method for designing fiber-network

Legal Events

Date Code Title Description
C06 Publication
PB01 Publication
C10 Entry into substantive examination
SE01 Entry into force of request for substantive examination
RJ01 Rejection of invention patent application after publication
RJ01 Rejection of invention patent application after publication

Application publication date: 20150429