WO2017157048A1 - Automated layout method and system for power grid system graph to overcome crossing, and storage medium - Google Patents

Abstract

Disclosed are an automated layout method and system for a power grid system graph to overcome crossing, and a storage medium. The method comprises: performing meshing division on a layout space; acquiring first coordinates of various elements in the layout space subjected to meshing division; according to the first coordinates, calculating a Manhattan distance between the various elements; respectively acquiring the number of crossed outgoing lines of various busbar containing elements; acquiring the total number of crossed connecting lines between the various elements; constructing an optimized model; and according to the optimized model, performing layout adjustment on elements in a power grid system graph.

Description

Power grid system diagram automation layout method and system for overcoming crossover, storage medium Technical field

The invention relates to the field of intelligent drawing, in particular to a method and system for overcoming the intersection of an automated layout of a power grid system diagram and a storage medium.

Background technique

With the continuous deepening of the national smart grid construction, a large number of drawings are needed to support the construction, operation and maintenance of the power grid. Due to the large amount of grid data, the electrical wiring is complicated and the dynamic changes are frequent. If it is drawn by hand, the workload is large. Moreover, it is more and more difficult to adapt to the needs of modern power grid production and development, and the automatic mapping function becomes more and more important.

Intelligent drawing requires the integration of manual drawing experience and computer intelligence technology. How to establish a computer-recognizable digital layout model based on subjective experience standards is a key part of intelligent drawing. The layout model of Graph Drawing in the world can be roughly divided into several types: trunk branch layout model, orthogonal layout model, tree layout model, force-oriented layout model, and so on. In several types of models, the orthogonal layout model and the tree layout model have graphical structural requirements that are applicable to specific scenarios. Although the force-oriented layout model has strong flexibility, its divergence tends to be inclined, and it is difficult to form horizontally aligned orthogonal images.

In the intelligent drawing of the power grid, domestic experts and scholars evaluate the layout effect from the aspects of total wiring length and crossover number, and form a multi-objective optimization method. In multi-objective optimization, the problem often encountered is that the number of layouts available for search is too large, and an optimized algorithm is needed to find a satisfactory layout in a short time. In addition, multiple outlets containing busbar components often have intersections that require correction.

In the patent publication No. 104361184A, a power grid automatic layout and system and method are provided, including a control module, a data analysis module, a layout module, and a wiring module. Blocking; the data parsing module, the layout module, and the wiring module are respectively connected to the control module; the data parsing module is configured to read and parse information of the power station and/or the substation from the database; The station and/or substation information setting node is arranged according to the node position according to the established rules; the wiring module is used for wiring according to the power station and/or substation information and the layout situation. However, the solution mainly solves the problem that the interaction between the power grids is difficult, and the geographical position of the nodes cannot be solved, which may lead to inevitable crossover of the subsequent wiring of the drawings.

Summary of the invention

The technical problem to be solved by the present invention is to provide a method and system for overcoming the intersection of the automatic layout of the grid system diagram, the storage medium, optimizing the layout of the grid system diagram, reducing the number of intersections, and improving the layout effect.

In order to solve the above technical problem, the technical solution adopted by the embodiment of the present invention is:

An automated layout of a grid system diagram to overcome crossover methods, including

Meshing the layout space;

Obtaining a first coordinate (x, y) of each component in the layout space after the meshing is divided;

Calculating a Manhattan distance L between the respective elements according to the first coordinate (x, y);

Obtaining the number of outgoing intersections C1 of each busbar component separately;

Obtaining a total number of connection intersections S2 between the respective components;

Constructing an optimization model according to the Manhattan distance L, the number of intersections S1, the total number of connection intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

Where m is the number of busbar components;

According to the optimization model, layout adjustment is performed on components in the grid system diagram.

Embodiments of the present invention also relate to a system for automatically scheduling layout of a power grid system to overcome crossover, including

Dividing a module, configured to mesh the layout space;

a first acquiring module configured to obtain a first coordinate (x, y) of each component in the gridded partitioned layout space;

a first calculating module, configured to calculate a Manhattan distance L between the respective elements according to the first coordinate (x, y);

The second obtaining module is configured to respectively acquire the number of outgoing intersections C1 of each busbar component;

a third obtaining module, configured to obtain a total number of connection intersections S2 between the respective components;

Constructing a module configured to construct an optimization model according to the Manhattan distance L, the number of outgoing intersections S1, the total number of connected intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

Where m is the number of busbar components;

The optimization module is configured to perform layout adjustment on components in the grid system map according to the optimization model.

Embodiments of the present invention are also directed to a storage medium storing a computer program for performing the above-described method of automated layout of a power grid system diagram to overcome intersection.

The beneficial effects of the embodiments of the present invention are: comprehensively considering the total length of the line between the components, the number of intersections of the busbar components, and the total number of crossovers between the components, constructing an optimization model, by minimizing the value of the optimization model, Automatically search for the ideal layout, which can greatly save human resources, improve work efficiency, and can reduce the number of intersections, improve the aesthetic appearance of the grid system map, and improve the layout effect; at the same time, the space layout utilization of the optimization model is high. The weight of each parameter can be set according to the needs of the user, and the versatility is strong, which increases the flexibility of the optimization model application.

DRAWINGS

1 is a flow chart of a method for overcoming an intersection of an automated layout of a grid system diagram according to an embodiment of the present invention;

2 is a flowchart of a method according to Embodiment 1 of the present invention;

3 is a schematic diagram of an effect of optimizing a model layout according to Embodiment 1 of the present invention;

4 is a schematic diagram of a layout effect of an orthogonal layout model;

Figure 5 is a schematic diagram of the layout effect of the tree layout model;

Figure 6 is a schematic diagram of the layout effect of the force-oriented layout model;

7 is a flowchart of a method according to Embodiment 2 of the present invention;

Figure 8 is a schematic view of a busbar-containing component according to a second embodiment of the present invention;

9 is a schematic diagram of polar coordinates according to Embodiment 2 of the present invention;

Figure 10 is a cross-sectional view showing two sets of components of the third embodiment of the present invention;

11 is a flowchart of a method according to Embodiment 3 of the present invention;

12 is a schematic diagram of determining the intersection of two groups of components in the third embodiment of the present invention;

FIG. 13 is a schematic structural diagram of a system for over-interleaving an automatic layout of a power grid system diagram according to an embodiment of the present invention; FIG.

FIG. 14 is a schematic structural diagram of a system according to Embodiment 4 of the present invention.

Label description:

1. Dividing module; 2. First acquiring module; 3. First calculating module; 4. Second acquiring module; 5. Third acquiring module; 6. Constructing module; 7. Optimizing module;

401, establishing unit; 402, first calculating unit; 403, first obtaining unit; 404, second obtaining unit;

501, a first obtaining unit; 502, a third obtaining unit; 503, a second calculating unit; 504, a first determining unit; 505, a third calculating unit; 506, a second determining unit; 507, a first determining unit; a second determining unit 509, a third determining unit 510, a third determining unit 511, a fourth determining unit, 512, and a fourth calculating unit.

detailed description

The detailed description of the technical content, the objects and the effects of the embodiments of the present invention will be described in detail below with reference to the accompanying drawings.

The most critical idea of an embodiment of the present invention is to search for a multi-objective based optimization model. The optimal value optimizes the layout of the grid system map.

Referring to FIG. 1, a method for overcoming the intersection of an automated layout of a grid system diagram includes

Meshing the layout space;

Obtaining a first coordinate (x, y) of each component in the layout space after the meshing is divided;

Calculating a Manhattan distance L between the respective elements according to the first coordinate (x, y);

Obtaining the number of outgoing intersections C1 of each busbar component separately;

Obtaining a total number of connection intersections S2 between the respective components;

Constructing an optimization model according to the Manhattan distance L, the number of intersections S1, the total number of connection intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

Where m is the number of busbar components;

According to the optimization model, layout adjustment is performed on components in the grid system diagram.

It can be seen from the above description that the beneficial effects of the present invention are: by minimizing the value of the optimization model, shortening the length of the line, reducing the number of intersections in the grid system diagram, and searching for an ideal layout, the appearance of the grid system map can be improved. , improve the layout effect.

In the embodiment of the present invention, the “calcifying the Manhattan distance L between the respective components according to the first coordinate” is specifically: according to a formula

Calculating the Manhattan distance L between the various elements, where δ(i,j) is a delta function, when there is a line between element i and element j, δ(i,j)=1, and δ(i, j) = 0.

It can be seen from the above description that the Manhattan distance is used as a model to measure the length of the connection between the nodes of the power grid, which is consistent with the vertical and vertical alignment of the grid system diagram, and the Manhattan distance model is effective and practical.

In the embodiment of the present invention, the “receiving the number of outgoing intersections C1 of each busbar component separately” is specifically:

Taking the bus bar component i as an origin, the vertical direction is 0 direction, and the counterclockwise direction is positive direction. Vertical polar coordinate system;

According to the formula

Calculating an angle of the kth element having a direct topological connection with the busbar element i in a polar coordinate system, wherein (x _i , y _i ) and (x _{i, k} , y _{i, k} ) are the bus bars a first coordinate of the component i and the component k;

Comparing the angles of the respective components having direct topological connection with the busbar component i, obtaining a reverse order number;

According to the reverse order number, the number of outgoing intersections C1 of the busbar-containing component is obtained.

It can be seen from the above description that by establishing a polar coordinate system, the angles of the respective components having direct topological connection with the busbar components are calculated and compared, and the reverse order number is obtained, and the number of intersections existing after the wiring of the shortest path can be derived.

In the embodiment of the present invention, the “total number of connection intersections S2 between acquisition elements” is specifically:

Obtaining two sets of components, one of which is a first component P1 and a second component P2 having a connection relationship, and the other is a third component Q1 and a fourth component Q2 having a connection relationship;

According to the first coordinates of the first component P1, the second component P2, the third component Q1, and the fourth component Q2, a first vector Q1P2, a second vector Q1P1, a third vector P1Q1, a fourth vector P1Q2, and a fifth are obtained. Vector Q2P1, sixth vector Q2P2, seventh vector P2Q2, eighth vector P2Q1;

Calculating the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross according to the formula ε1=Q1P2×Q1P1, ε2=P1Q1×P1Q2, ε3=Q2P1×Q2P2, ε4=P2Q2×P2Q1 Multiply the result ε4;

Determining whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0;

If the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0, then according to the formula κ1=Q1P2·Q1P1, κ2=P1Q1·P1Q2, κ3 =Q2P1·Q2P2, κ4=P2Q2·P2Q1 calculates the first point multiplication result κ1, the second point multiplication result κ2 The third point is multiplied by the result κ3 and the fourth point is multiplied by the result κ4;

If the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are both greater than 0, it is determined that the two sets of components do not intersect, and the two groups are determined The number of connection crossings of the component C2=0;

If the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are not more than 0, it is determined that the two sets of elements intersect, and the two groups are The number of connection crossings of the component C2=1;

If the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both greater than or equal to 0 or less than or equal to 0, it is determined that the two sets of components intersect, and Having the number of intersections of the two sets of components C2=1;

If the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are not equal to or greater than 0 or the unevenness is less than or equal to 0, it is determined that the two sets of components are not Intersect, and make the number of intersections of the two sets of components C2=0;

According to the formula

The total number of connection crossings S2 is calculated, where t is the number of elements of any two sets of connected elements and there are no common elements in the two sets of elements.

It can be seen from the above description that it is simple and efficient to judge whether two sets of components intersect by the cross-multiplication result of the vector and the dot multiplication result.

Referring to FIG. 13, an embodiment of the present invention further provides a system for over-interleaving an automatic layout of a power grid system diagram, including:

Dividing a module, configured to mesh the layout space;

a first acquiring module configured to obtain a first coordinate (x, y) of each component in the gridded partitioned layout space;

a first calculating module, configured to calculate a Manhattan distance L between the respective elements according to the first coordinate (x, y);

The second obtaining module is configured to respectively acquire the number of outgoing intersections C1 of each busbar component;

a third obtaining module, configured to obtain a total number of connection intersections S2 between the respective components;

Constructing a module configured to construct an optimization model according to the Manhattan distance L, the number of outgoing intersections S1, the total number of connected intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

Where m is the number of busbar components;

The optimization module is configured to perform layout adjustment on components in the grid system map according to the optimization model.

In the embodiment of the present invention, the first calculating module is further configured according to a formula

Calculating the Manhattan distance L between the various elements, where δ(i,j) is a delta function, when there is a line between element i and element j, δ(i,j)=1, and δ(i, j) = 0.

In the embodiment of the present invention, the second obtaining module includes

Establishing a unit, configured to use the bus bar component i as an origin, a vertical direction of 0 direction, and a counterclockwise direction, to establish a polar coordinate system;

First calculation unit configured to be based on a formula

Mod 2π calculates the angle of the kth element having a direct topological connection with the busbar element i in a polar coordinate system, wherein (x _i , y _i ) and (x _{i, k} , y _{i, k} ) are a first coordinate comprising the busbar component i and the component k;

a first obtaining unit configured to compare angles of respective elements having direct topological connection with the bus bar element i to obtain a reverse order number;

The second obtaining unit is configured to obtain the number of outgoing intersections C1 of the busbar-containing component according to the reverse order number.

In the embodiment of the present invention, the third obtaining module includes

The first obtaining unit is configured to acquire two sets of components, one of which is a first component P1 and a second component P2 having a connection relationship, and the other is a third component Q1 and a fourth component Q2 having a connection relationship;

a third obtaining unit configured to obtain, according to the first coordinates of the first component P1, the second component P2, the third component Q1, and the fourth component Q2, a first vector Q1P2, a second vector Q1P1, and a third vector P1Q1 Fourth vector P1Q2, fifth vector Q2P1, sixth vector Q2P2, seventh vector P2Q2, eighth vector P2Q1;

a second calculating unit configured to calculate a first cross result ε1, a second cross result ε2, a third cross according to a formula ε1=Q1P2×Q1P1, ε2=P1Q1×P1Q2, ε3=Q2P1×Q2P2, ε4=P2Q2×P2Q1 Multiply the result ε3 and the fourth cross result ε4;

a first determining unit, configured to determine whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0;

a third calculating unit configured to: if the first cross result ε1, the second cross result ε2, the third cross result ε3, and the fourth cross result ε4 are both 0, according to the formula κ1=Q1P2·Q1P1 Κ2=P1Q1·P1Q2, κ3=Q2P1·Q2P2, κ4=P2Q2·P2Q1 calculate the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4;

The first determining unit is configured to determine that the two sets of components do not intersect if the first multiplication result κ1, the second multiplication result κ2, the third multiplication result κ3, and the fourth multiplication result κ4 are both greater than 0 And let the number of connection crossings of the two sets of components C2=0;

a second determining unit configured to determine that the two sets of components intersect if the first multiplication result κ1, the second multiplication result κ2, the third multiplication result κ3, and the fourth multiplication result κ4 are not greater than 0 And let the number of connection crossings of the two sets of components C2=1;

a third determining unit configured to determine that the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both greater than or equal to 0 or less than or equal to 0 The two sets of components intersect, and the number of intersections of the two sets of components is C2=1;

a fourth determining unit configured to: if the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are not equal to or greater than 0, or the unevenness is less than or equal to 0, Determining that the two sets of components do not intersect, and causing the number of crossovers of the two sets of components to be C2=0;

Fourth calculation unit, configured to be based on a formula

The total number of connection crossings S2 is calculated, where t is the number of elements of any two sets of connected elements and there are no common elements in the two sets of elements.

Embodiment 1

Referring to FIG. 2, a first embodiment of the present invention is a method for overcoming the intersection of an automated layout of a power grid system diagram, including the following steps:

S1: meshing the layout space;

A sparse grid will limit the layout effect and affect the flexibility of the model. If the grid is too dense, it will increase the calculation cost, and also affect the layout aesthetic requirements. Balance the system performance and model flexibility, and the cell size and layout space. The division is as follows: Use the same size of cells to divide the layout area, each component is only one row, not allowed to be placed across rows, components can occupy multiple cells in a row, and there is at most one component in each cell. The components are placed in the center of the cell, leaving a space around the component; that is, assuming that the layout space is a rectangular area, a mesh is established according to a certain horizontal spacing W _unit and the longitudinal spacing H _unit , W _unit =min(w _i )+W _space i=1...n, H _unit =max(h _i )+H _space i=1...n, where W _unit and H _unit are cell widths, w _i and h _i are The width of i components, n is the number of components, and W _space and H _space are the widths of the routing channels reserved around the components.

S2: obtaining a first coordinate (x, y) of each component in the layout space after the meshing division;

Optionally, for the convenience of computer processing, the upper left corner of the layout space is set as the origin, the horizontal right is the positive direction of the x-axis, and the vertical direction is the positive direction of the y-axis.

S3: judging whether there is a connection between the respective components, that is, determining whether there is a connection between any two components i and j in the layout space, and if so, executing step S4, and if not, executing step S5.

S4: Let the delta function δ(i,j)=1.

S5: Let the delta function δ(i,j)=0.

S6: According to the first coordinates and formula of each component

The Manhattan distance L between the various elements is calculated, where (x _i , y _i ) is the first coordinate of element i, (x _j , y _j ) is the first coordinate of element j, and n is the number of elements in the layout space.

S7: Obtain the busbar components in the grid system diagram.

S8: respectively obtaining the number of outgoing intersections C1 of each busbar component; normally, the busbar outlet connectors are discharged at the lower end of the component, and are numbered in order from left to right, and the connected components are easily cross-lined due to improper placement, and the intersection is crossed. The number is the number of intersections of the outgoing lines containing the bus components.

S9: obtaining the total number of connection intersections S2 between the respective components; first, taking four components connected by two wires, and judging whether there are intersections of the two wires connecting the four components, and if there is a cross, it is connected The number of line crossings is 1, and vice versa is 0. The number of crossings of all the two connecting lines is obtained, and the summation is the total number of connecting lines.

S10: Constructing an optimization model according to the Manhattan distance L, the number of intersections S1, the total number of connection intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

Where m is the number of busbar components.

The first weight ω1, the second weight ω2, and the third weight ω3 can be directly set manually, that is, a set of weights is directly given by the related user of the system diagram, which reflects each person's aversion to the line length and the two types of intersections. The higher the degree, the greater the weight given. By giving the average of the weights to multiple people, the average preference of the users related to the system map can be determined; it can also be set by statistical calculation, based on the order distribution model in statistics. According to the system diagram of the existing artificial layout, the line length and the values of the two intersection numbers are respectively calculated, and the order distribution of the three values is obtained, thereby determining the proportional relationship between the three values, and multiplying by the normalization coefficient to obtain the weight. It is also possible to average the values of the three weights manually set and the values of the three weights obtained by the statistical calculation by the average method as the values of the final three weights.

S11: Perform layout adjustment on components in the grid system diagram according to the optimization model; optimize The smaller the value of the model, the better the layout effect. In the process of seeking the optimal solution of the optimization model, the position of the exchange component and the way of placing the component to the blank position are used to reduce the value F of the optimization model. Search in the direction and finally search for the ideal layout. Preferably, in the optimization process, all generated layouts are excluded from repetition, as long as the value of the optimized model corresponding to the generated layout is better than the currently accessed layout, the other layouts are suspended, and the more optimized layout is preferentially accessed to improve the search efficiency.

The line direction in the grid system diagram is usually determined by the shortest path algorithm. The common shortest path algorithms are depth-first search, breadth-first search, A ^* algorithm and Djisktra algorithm. Alternatively, the calculation of the inter-component wiring in the grid system diagram can be done using the Djisktra algorithm on the weighted grid.

In order to verify the layout effect of the optimization model, three common layout models are selected for comparison, including tree layout model, orthogonal layout model, force-oriented layout model, and 100 simulated grid topology data are used as examples to directly present The results of the mapping are compared to the aesthetics and legibility of the map, and the interest rate of the model to the space is compared by calculating the number of grids and the aspect ratio of the graph.

Figure 3 is a schematic diagram of the layout effect of the optimized model, Figure 4 is a schematic diagram of the layout effect of the orthogonal layout model, Figure 5 is a schematic diagram of the layout effect of the tree layout model, Figure 6 is a schematic diagram of the layout effect of the force-oriented layout model; Table 1 contains the above four models Space utilization, Table 2 contains the above four models for the control space aspect ratio and specific area control ability.

	Layout space	Space utilization
Optimization model	121 units	24.8%
Orthogonal layout	567 units	5.3%
Tree layout	234 units	12.8%
Force-oriented layout	391 units	7.7%

Table 1

	Can control area	Can control the aspect ratio?
Multi-objective optimization model	Yes	Yes

Orthogonal layout	No	No
Tree layout	No	No
Force-oriented layout	Yes	Yes

Table 2

Comparing Figure 3-6 with Table 1-2, the results show that the optimization model has significant advantages in controlling the layout space aspect ratio and optimizing the layout space utilization, and the models are reduced in the reduction of line crossings. The effect of the cross.

Embodiment 2

Referring to FIG. 7, the embodiment is a specific implementation manner of step S8, which includes the following steps:

S801: taking the bus bar component i as the origin, the vertical direction is 0 direction, the counterclockwise direction is the positive direction, the polar coordinate system is established, the angle unit is set to radians, and the component i node degree is d _j .

S802: calculating an angle of each component having a direct topological connection with the busbar component in a polar coordinate system;

Calculating an angle of the kth element having a direct topological connection with the busbar element i in a polar coordinate system, wherein (x _i , y _i ) and (x _{i, k} , y _{i, k} ) are the bus bars The first coordinate of element i and the element k, k=1...d _j .

S803: Comparing the angles of the respective components having direct topological connection with the busbar component i, and obtaining a reverse order number; the inverse ordinal number is defined as: if the number of the n numbers in 1, 2, 3...n is a full arrangement p ₁ , p ₂ , p ₃ ... p _n , when p _i >p _j , i<j, it is called a reverse order, and the order of p ₁ , p ₂ , p ₃ ... p _n is reversed The total number is called the inverse number of the permutation.

S804: Obtain an intersection number C1 of the bus-line-containing component according to the reverse order number; that is, the number of outgoing intersections C1 is equal to a reverse-order number.

For example, as shown in FIG. 8, a schematic diagram of a component A, B, C, and D having a busbar component directly connected to it, in order to avoid overlapping angles of multiple components in a horizontal connection when calculating an angle, Can not distinguish whether the intersection, such as component C and component D, can shift the origin slightly to the outgoing direction, as shown in Figure 9; optionally, the offset distance is 0.1 cells or 0.01 cells; according to step S802 The formula calculates that the angles of the A, B, C, and D components relative to the busbar components are 116°, 68°, 279°, and 272°, respectively, and the resulting order is 116°<68°<279°<272°, which exists. The reverse order is: 116°<68° and 279°<272°, that is, the reverse order number is 2, and there are two intersections after the wiring according to the shortest path is pushed out, that is, the number of intersections of the bus-line-containing elements is C1=2.

Since the reverse direction is the positive direction of the polar coordinate system, it is preferable that the angles of the four elements can be directly obtained as B<A<D<C, and the comparison order A<B<C<D, there are two reverse orders, That is, if the number of reverse order is 2, it is easy to obtain the number of outgoing intersections C1=2 of the busbar-containing component.

Embodiment 3

This embodiment is based on the first embodiment, in a specific implementation manner of step S9, in the actual layout, there are multiple intersections of two wires connected to four components, as shown in the cross on the left side of FIG. The four corners in the middle of Fig. 10, as well as the more random situation, such as the right side of Fig. 10. Although there are various situations in the relative position of the components, the detection of such intersections in the layout is found to be uniformly handled by the two-line cross-judgment.

Usually, the two line segments intersect, and the inner angle of the enclosed quadrilateral is equal to 180°; the two line segments do not intersect, and the inner angle is greater than 180°. Since the calculation of the inner angle is cumbersome, it is judged by the four vector cross-multiplication results ε1, ε2, ε3, and ε4. Once it is found that it is greater than 0 and less than 0, the corresponding quadrilateral has an internal angle greater than 180° and less than 180°. In this case, you can quickly return the results of the disjoint two-segment. In special cases, the four vector cross-multiplication results are all equal to 0, corresponding to the two line segments on the same line. Four vector point multiplication results κ1, κ2, κ3, and κ4 are calculated. If all are greater than 0, they do not intersect, otherwise the two line segments intersect. .

Referring to FIG. 11, step S9 in this embodiment may specifically include the following steps:

S901: Acquire two sets of components, one of which is a first component P1 and a second component P2 having a connection relationship, and the other is a third component Q1 and a fourth component Q2 having a connection relationship.

S902: According to the first coordinates of the first component P1, the second component P2, the third component Q1, and the fourth component Q2, obtain a first vector Q1P2, a second vector Q1P1, a third vector P1Q1, and a fourth vector P1Q2. The fifth vector Q2P1, the sixth vector Q2P2, the seventh vector P2Q2, and the eighth vector P2Q1.

S903: Calculate the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the first according to the formula ε1=Q1P2×Q1P1, ε2=P1Q1×P1Q2, ε3=Q2P1×Q2P2, ε4=P2Q2×P2Q1 Quadruple multiplication results ε4.

S904: determining whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are all 0. If yes, step S905 is performed, and if not, executing steps S909.

S905: Calculate the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the first according to the formula κ1=Q1P2·Q1P1, κ2=P1Q1·P1Q2, κ3=Q2P1·Q2P2, κ4=P2Q2·P2Q1 Four-point multiplication results κ4.

S906: determining whether the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are both greater than 0. If yes, step S907 is performed, and if no, the step is performed. S908.

S907: It is determined that the two sets of components do not intersect, that is, there is no intersection, and the number of intersections of the two sets of components is C2=0.

S908: It is determined that the two sets of components intersect, that is, there is an intersection, and the number of connection crossings of the two sets of components is C2=1.

S909: determining whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both greater than or equal to 0 or less than or equal to 0, and if yes, executing S910, if Otherwise, step S911 is performed.

S910: Determine that the two sets of components intersect, and make the number of connection crossings of the two sets of components C2=1.

S911: determining that the two sets of components do not intersect, and causing the number of intersections of the two sets of components C2=0.

S912: Acquire a number of connection intersections C2 of any two groups of components in the layout space, according to the formula

Calculating the total number of connection intersections S2, where t is the number of elements of any two connected components and there is no common component in the two sets of components, that is, any two wires are taken out in all the wires and both meet The number of root connections that are not connected to the common component.

For example, the cross-multiplication results calculated by the two sets of elements shown in (a) of FIG. 12 are ε1>0, ε2>0, ε3>0, ε4>0, and the four cross-multiplication results are all greater than 0, thus determining The intersection is C2=1; the cross-multiplication results calculated by the two sets of components shown in (b) of Figure 12 are ε1<0, ε2<0, ε3<0, ε4<0, and the four cross-multiplication results are It is less than 0, so it is judged that it intersects, C2=1; the cross-multiplication results calculated by the two sets of components shown in (b) of Figure 12 are ε1<0, ε2>0, respectively, because there are more than 0 and less than 0 at the same time. In the case, the third cross-multiplication result ε3 and the fourth cross-multiplication result ε4 may not be calculated, and it is directly determined that the two sets of components do not intersect, C2=0; the fork calculated by the two sets of components shown in (e) of FIG. The multiplication results are ε1=0, ε2>0, ε3>0, ε4>0, and the four cross-multiplication results are all greater than or equal to 0, so the intersection is judged, C2=1; for (e) and (f) in Fig. 12 The calculated four cross-multiplication results are all 0, so the four-point multiplication result is calculated. For the two sets of components shown in (e), the calculated point multiplication results are κ1>0, κ2, respectively. >0, κ3>0, κ4>0, the four point multiplication results are all greater than 0, so It is determined that the two sets of elements do not intersect, C2=0; for the two sets of elements shown in (f), the calculated point multiplication results are κ1>0, κ2<0, κ3<0, κ4>0, respectively. The four point multiplication results are not more than 0, so it is determined that the two sets of elements intersect, C2=1.

Embodiment 4

Referring to FIG. 14, the embodiment is a system for over-intersecting the automatic layout of the power grid system diagram based on the first embodiment, the second embodiment, and the third embodiment, including

Dividing module 1 configured to mesh the layout space;

The first obtaining module 2 is configured to obtain a first coordinate (x, y) of each component in the gridded partitioned layout space;

a first calculating module 3, configured to calculate a Manhattan distance L between the respective elements according to the first coordinate (x, y); further configured according to a formula

Calculating the Manhattan distance L between the various elements, where δ(i,j) is a delta function, when there is a line between element i and element j, δ(i,j)=1, and δ(i, j) = 0;

The second obtaining module 4 is configured to respectively acquire the number of outgoing intersections C1 of each busbar component;

The third obtaining module 5 is configured to acquire the total number of connection intersections S2 between the respective components;

The constructing module 6 is configured to construct an optimization model according to the Manhattan distance L, the number of outgoing intersections S1, the total number of connected intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3.

Where m is the number of busbar components;

The optimization module 7 is configured to perform layout adjustment on components in the grid system map according to the optimization model.

The second obtaining module 4 includes

The establishing unit 41 is configured to use the bus bar component i as an origin, the vertical direction is 0 direction, and the counterclockwise direction is positive direction, and a polar coordinate system is established;

The first calculating unit 42 is configured to be based on a formula

Calculating an angle of the kth element having a direct topological connection with the busbar element i in a polar coordinate system, wherein (x _i , y _i ) and (x _{i, k} , y _{i, k} ) are the bus bars a first coordinate of the component i and the component k;

a first obtaining unit 43 configured to compare angles of respective elements having direct topological connection with the bus bar element i to obtain a reverse order number;

The second obtaining unit 44 is configured to obtain the number of outgoing intersections C1 of the busbar-containing component according to the reverse order number.

The third obtaining module 5 includes

The first obtaining unit 501 is configured to acquire two sets of components, one of which is a first component P1 and a second component P2 having a connection relationship, and the other is a third component Q1 and a fourth component Q2 having a connection relationship ;

The third obtaining unit 502 is configured to obtain the first vector Q1P2, the second vector Q1P1, and the third vector P1Q1 according to the first coordinates of the first component P1, the second component P2, the third component Q1, and the fourth component Q2. a fourth vector P1Q2, a fifth vector Q2P1, a sixth vector Q2P2, a seventh vector P2Q2, an eighth vector P2Q1;

The second calculating unit 503 is configured to calculate the first cross result ε1, the second cross result ε2, and the third according to the formula ε1=Q1P2×Q1P1, ε2=P1Q1×P1Q2, ε3=Q2P1×Q2P2, ε4=P2Q2×P2Q1 Cross-multiply result ε3 and fourth cross-multiplication result ε4;

The first determining unit 504 is configured to determine whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0;

The third calculating unit 505 is configured to: if the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0, according to the formula κ1=Q1P2·Q1P1 Κ2=P1Q1·P1Q2, κ3=Q2P1·Q2P2, κ4=P2Q2·P2Q1 calculate the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4;

The second determining unit 506 is configured to determine whether the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are both greater than 0;

The first determining unit 507 is configured to determine that the two sets of components are not determined if the first multiplication result κ1, the second multiplication result κ2, the third multiplication result κ3, and the fourth multiplication result κ4 are both greater than 0 Intersect, and make the number of intersections of the two sets of components C2=0;

The second determining unit 508 is configured to determine the two groups of components if the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are not more than 0 Intersect, and make the number of intersections of the two sets of components C2=1;

The third determining unit 509 is configured to determine the first cross result ε1 and the second cross result ε2 Whether the third cross-multiplication result ε3 and the fourth cross-multiplication result ε4 are both greater than 0 or both are less than 0;

The third determining unit 510 is configured to determine that the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both greater than or equal to 0 or less than or equal to 0. The two sets of elements intersect, and the number of intersections of the two sets of elements is C2=1;

The fourth determining unit 511 is configured to: if the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are not equal to or greater than 0, or the unevenness is less than or equal to 0, Then determining that the two sets of components do not intersect, and the number of intersections of the two sets of components C2 = 0;

The fourth calculating unit 512 is configured to be according to a formula

The total number of connection crossings S2 is calculated, where t is the number of elements of any two sets of connected elements and there are no common elements in the two sets of elements.

In practical applications, the grid system map automation layout overcomes the functions implemented by the various unit modules in the crossover system, and the central processing unit (CPU) in the system that overcomes the crossover in the grid system map automation layout can be used. Or a microprocessor (Micro Processor Unit, MPU), or a digital signal processor (DSP), or a Field Programmable Gate Array (FPGA).

Embodiments of the Invention The above-described grid system diagram automation layout overcomes the crossover system. If implemented in the form of a software function module and sold or used as a standalone product, it can also be stored in a computer readable storage medium. Based on such understanding, the technical solution of the embodiments of the present invention may be embodied in the form of a software product in essence or in the form of a software product stored in a storage medium, including a plurality of instructions. A computer device (which may be a personal computer, server, or network device, etc.) is caused to perform all or part of the methods described in various embodiments of the present invention. Correspondingly, the embodiment of the present invention further provides a storage medium, wherein a computer program is stored, and the computer program is used to execute the method for automatically intersecting the layout of the grid system diagram of the embodiment of the present invention.

In summary, the present invention provides a grid system diagram automatic layout to overcome the intersection method And the system and storage medium, using Manhattan distance as the model to measure the length of the connection between the grid nodes, in line with the horizontal and vertical characteristics of the grid system map, and the Manhattan distance model is effective and practical; through the establishment of the polar coordinate system, Calculate and compare the angles of the various components that have a direct topological connection with the busbar components, obtain the inverse order number, and push out the number of intersections after the wiring according to the shortest path; determine whether the two components are present by the cross-multiplication result of the vector and the dot multiplication result Crossover, simple and efficient; comprehensively consider the total length of the line between components, the number of intersections of busbar components and the total number of crossovers between components, construct an optimization model, and automatically search for the ideal by minimizing the value of the optimization model. The layout can greatly save human resources, improve work efficiency, and improve the aesthetic appearance of the grid system map and improve the layout effect. At the same time, the space layout of the optimized model is highly utilized, and various parameters can be set according to the needs of the user. Weight and versatility increase the flexibility of the optimization model application.

The above is only the embodiment of the present invention, and is not intended to limit the scope of the invention, and equivalent transformations made by the description of the present invention and the contents of the drawings, or directly or indirectly applied in the related technical field, are included in the same. Within the scope of patent protection of the present invention.

Industrial applicability

The invention comprehensively considers the total length of the line between the components, the number of intersections of the busbar components and the total number of intersections between the components, constructs an optimization model, and automatically searches for an ideal layout by minimizing the value of the optimization model. It can greatly save human resources, improve work efficiency, and can reduce the number of intersections, improve the aesthetic appearance of the grid system map, and improve the layout effect; at the same time, the space layout utilization of the optimization model is high, and can be set according to the needs of users. The weight of each parameter is highly versatile, which increases the flexibility of the optimization model application.

Claims (9)

1. An automated layout of a grid system diagram to overcome crossover methods, including

   Meshing the layout space;

   Obtaining a first coordinate (x, y) of each component in the layout space after the meshing is divided;

   Calculating a Manhattan distance L between the respective elements according to the first coordinate (x, y);

   Obtaining the number of outgoing intersections C1 of each busbar component separately;

   Obtaining a total number of connection intersections S2 between the respective components;

   Constructing an optimization model according to the Manhattan distance L, the number of intersections S1, the total number of connection intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

   

   Where m is the number of busbar components;

   According to the optimization model, layout adjustment is performed on components in the grid system diagram.
2. The method of claim 1, wherein the calculating a Manhattan distance L between the respective elements according to the first coordinate is specifically: according to a formula

   

   Calculating the Manhattan distance L between the various elements, where δ(i,j) is a delta function, when there is a line between element i and element j, δ(i,j)=1, and δ(i, j) = 0.
3. The method for overcoming the intersection of the automatic layout of the grid system diagram according to claim 1, wherein the “acquiring the number of outgoing intersections C1 of each busbar component separately” is specifically:

   Taking the bus bar component i as an origin, the vertical direction is 0 direction, and the counterclockwise direction is positive direction, and a polar coordinate system is established;

   According to the formula

   

   Calculating an angle of the kth element having a direct topological connection with the busbar element i in a polar coordinate system, wherein (x _i , y _i ) and (x _{i, k} , y _{i, k} ) are the bus bars a first coordinate of the component i and the component k;

   Comparing the angles of the respective components having direct topological connection with the busbar component i, obtaining a reverse order number;

   According to the reverse order number, the number of outgoing intersections C1 of the busbar-containing component is obtained.
4. The method for overcoming the intersection of the grid system map automation layout according to claim 1, wherein the "acquiring the total number of connection intersections S2 between components" is specifically:

   Obtaining two sets of components, one of which is a first component P1 and a second component P2 having a connection relationship, and the other is a third component Q1 and a fourth component Q2 having a connection relationship;

   According to the first coordinates of the first component P1, the second component P2, the third component Q1, and the fourth component Q2, a first vector Q1P2, a second vector Q1P1, a third vector P1Q1, a fourth vector P1Q2, and a fifth are obtained. Vector Q2P1, sixth vector Q2P2, seventh vector P2Q2, eighth vector P2Q1;

   Calculating the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross according to the formula ε1=Q1P2×Q1P1, ε2=P1Q1×P1Q2, ε3=Q2P1×Q2P2, ε4=P2Q2×P2Q1 Multiply the result ε4;

   Determining whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0;

   If the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0, then according to the formula κ1=Q1P2·Q1P1, κ2=P1Q1·P1Q2, κ3 =Q2P1·Q2P2, κ4=P2Q2·P2Q1 calculates the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4;

   If the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are both greater than 0, it is determined that the two sets of components do not intersect, and the two groups are determined The number of connection crossings of the component C2=0;

   If the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4 are not more than 0, it is determined that the two sets of elements intersect, and the two groups are Component The number of connection crossings C2=1;

   If the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both greater than or equal to 0 or less than or equal to 0, it is determined that the two sets of components intersect, and Having the number of intersections of the two sets of components C2=1;

   If the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are not equal to or greater than 0 or the unevenness is less than or equal to 0, it is determined that the two sets of components are not Intersect, and make the number of intersections of the two sets of components C2=0;

   According to the formula

   

   The total number of connection crossings S2 is calculated, where t is the number of elements of any two sets of connected elements and there are no common elements in the two sets of elements.
5. An automated layout of a grid system diagram to overcome crossover systems, including

   Dividing a module, configured to mesh the layout space;

   a first acquiring module configured to obtain a first coordinate (x, y) of each component in the gridded partitioned layout space;

   a first calculating module, configured to calculate a Manhattan distance L between the respective elements according to the first coordinate (x, y);

   The second obtaining module is configured to respectively acquire the number of outgoing intersections C1 of each busbar component;

   a third obtaining module, configured to obtain a total number of connection intersections S2 between the respective components;

   Constructing a module configured to construct an optimization model according to the Manhattan distance L, the number of outgoing intersections S1, the total number of connected intersections S2, and the preset first weight ω1, the second weight ω2, and the third weight ω3

   

   Where m is the number of busbar components;

   The optimization module is configured to perform layout adjustment on components in the grid system map according to the optimization model.
6. The system of claim 5, wherein the first computing module is further configured to be based on a formula

   

   Calculating the Manhattan distance L between the various elements, where δ(i,j) is a delta function, when there is a line between element i and element j, δ(i,j)=1, and δ(i, j) = 0.
7. The grid system diagram of claim 5, wherein the second acquisition module comprises an automated layout that overcomes the intersection

   Establishing a unit, configured to use the bus bar component i as an origin, a vertical direction of 0 direction, and a counterclockwise direction, to establish a polar coordinate system;

   First calculation unit configured to be based on a formula

   

   Calculating an angle of the kth element having a direct topological connection with the busbar element i in a polar coordinate system, wherein (x _i , y _i ) and (x _{i, k} , y _{i, k} ) are the bus bars a first coordinate of the component i and the component k;

   a first obtaining unit configured to compare angles of respective elements having direct topological connection with the bus bar element i to obtain a reverse order number;

   The second obtaining unit is configured to obtain the number of outgoing intersections C1 of the busbar-containing component according to the reverse order number.
8. The grid system map automation layout of claim 5, wherein the third acquisition module comprises

   The first obtaining unit is configured to acquire two sets of components, one of which is a first component P1 and a second component P2 having a connection relationship, and the other is a third component Q1 and a fourth component Q2 having a connection relationship;

   a third obtaining unit configured to obtain, according to the first coordinates of the first component P1, the second component P2, the third component Q1, and the fourth component Q2, a first vector Q1P2, a second vector Q1P1, and a third vector P1Q1 Fourth vector P1Q2, fifth vector Q2P1, sixth vector Q2P2, seventh vector P2Q2, eighth vector P2Q1;

   a second calculating unit configured to calculate a first cross result ε1, a second cross result ε2, a third cross according to a formula ε1=Q1P2×Q1P1, ε2=P1Q1×P1Q2, ε3=Q2P1×Q2P2, ε4=P2Q2×P2Q1 Multiply the result ε3 and the fourth cross result ε4;

   a first determining unit, configured to determine whether the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both 0;

   a third calculating unit configured to: if the first cross result ε1, the second cross result ε2, the third cross result ε3, and the fourth cross result ε4 are both 0, according to the formula κ1=Q1P2·Q1P1 Κ2=P1Q1·P1Q2, κ3=Q2P1·Q2P2, κ4=P2Q2·P2Q1 calculate the first point multiplication result κ1, the second point multiplication result κ2, the third point multiplication result κ3, and the fourth point multiplication result κ4;

   The first determining unit is configured to determine that the two sets of components do not intersect if the first multiplication result κ1, the second multiplication result κ2, the third multiplication result κ3, and the fourth multiplication result κ4 are both greater than 0 And let the number of connection crossings of the two sets of components C2=0;

   a second determining unit configured to determine that the two sets of components intersect if the first multiplication result κ1, the second multiplication result κ2, the third multiplication result κ3, and the fourth multiplication result κ4 are not greater than 0 And let the number of connection crossings of the two sets of components C2=1;

   a third determining unit configured to determine that the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are both greater than or equal to 0 or less than or equal to 0 The two sets of components intersect, and the number of intersections of the two sets of components is C2=1;

   a fourth determining unit configured to: if the first cross-multiplication result ε1, the second cross-multiplication result ε2, the third cross-multiplication result ε3, and the fourth cross-multiplication result ε4 are not equal to or greater than 0, or the unevenness is less than or equal to 0, Determining that the two sets of components do not intersect, and causing the number of crossovers of the two sets of components to be C2=0;

   Fourth calculation unit, configured to be based on a formula

   

   The total number of connection crossings S2 is calculated, where t is the number of elements of any two sets of connected elements and there are no common elements in the two sets of elements.
9. A storage medium storing computer executable instructions in the storage medium The machine executable instructions are configured to perform the grid system map automation layout of any of claims 1-4 to overcome the intersection.

Images