JPH05120430A - Crossing judgment and intersection calculation system for polygon and straight line - Google Patents

Abstract

PURPOSE:To provide a crossing decision and intersection calculation system of a polygon with a straight line by which a processing time can be shortened. CONSTITUTION:Polygon data are received by a polygon data storage part 1, a coordinate area to which a crossing decision and an intersection calculation are operated is divided plural virtual grids, and a grid number is applied to each virtual grid. Then, a virtual grid and vertex number corresponding chart which stores the vertex number of the polygon positioned within the virtual grid at each grid number is prepared by a virtual grid and vertex number corresponding chart preparing part 2. Next, the virtual grid and vertex number corresponding chart is stored in a virtual grid and vertex number corresponding chart storage part 3, straight line data specifying a straight line to which the crossing decision and the intersection calculation with the polygon are operated are inputted, and the grid number of the virtual grid through which the straight line passes is retrieved by a virtual grid retrieving part 4. Then, the crossing decision and the intersection calculation of the side of the polygon in which at least the vertexes of the polygon positioned within the virtual grid of the grid number retrieved by the virtual grid retrieving part 4 are used as one edge, with the straight line are operated by a crossing decision and intersection calculating part 5, and the presence or absence of the crossing and the coordinate value of the intersection are outputted.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for determining intersections and intersections between polygons and straight lines, and particularly for a polygon having a complicated shape with a large number of sides or a set of a large number of polygons, the total number of sides is The present invention relates to a method for determining intersections and calculating intersections between polygons including many shapes and straight lines.

[0002]

2. Description of the Related Art The conventional method of determining intersections and intersections between polygons and straight lines is based on contour line data used for maps and the like.
This is applied when creating a cross-sectional view, and as shown in the block diagram of Fig. 2, the polygon numbers of all polygons that calculate intersection determination and intersections, and the side numbers of each side that makes up this polygon. And a polygon data storage unit 11 for storing polygon data composed of vertex numbers at both ends of each side and coordinate values of the vertices, and data defining a straight line for performing intersection determination with the polygon and calculation of an intersection. An intersection determination / intersection calculation unit 12 that receives data input from the rectangular data storage unit 11 and performs intersection determination and intersection calculation. As an operation, first, coordinate values of arbitrary two points on the straight line are input to the intersection determination / intersection calculation unit 12 as data defining a straight line for performing intersection determination with a polygon and intersection calculation. Next, for all sides forming the polygon, the coordinate values of the vertices at both ends of the side are input from the polygon data storage unit 11, and subsequently, the intersection determination and the intersection calculation with the already input straight line are calculated for all the sides. Is calculated and the presence or absence of the intersection and the coordinate value of the intersection are output.

[0003]

In the above-described conventional method for determining intersection and intersection between a polygon and a straight line, the intersection is determined and the intersection is calculated with respect to the straight line for all sides forming the polygon. When a polygon with a complicated shape and a large number of sides or a large number of sides due to a set of polygons is used as a target, the intersection judgment with a straight line and the calculation of intersection points are performed for a large number of sides. Therefore, there is a problem that the processing takes time.

An object of the present invention is to provide a method of determining intersections and intersections between polygons and straight lines, which can shorten the processing time.

[0005]

According to the intersection determination / intersection calculation method of a polygon and a straight line of the present invention, polygon numbers of all polygons for which intersection determination and intersection are calculated and each side forming the polygon. A polygon data storage unit for storing polygon data consisting of the side number of each side and the numbers of the vertices at both ends of each side and the coordinate values of the vertices; In the intersection determination / intersection calculation method between a polygon and a straight line, which includes the intersection determination / intersection calculation unit that performs intersection determination and intersection calculation and outputs the intersection presence / absence and coordinate values of the intersection, A virtual grid is set which divides the coordinate area for receiving intersection data and performing intersection determination and intersection calculation on the polygon into a plurality of polygons, and assigns a grid number to each virtual grid. Virtual grid to create a virtual lattice-vertex number correspondence table that stores the number of vertices of the polygon location,
A vertex number correspondence table creation unit, a virtual grid / vertex number correspondence table storage unit that stores the virtual grid / vertex number correspondence table created by the virtual grid / vertex number correspondence table creation unit, and an intersection determination between the polygon and A virtual grid search unit for inputting straight line data defining a straight line for calculating an intersection and searching for a grid number of the virtual grid through which the straight line passes, and a position within the virtual grid of the grid number searched by this virtual grid search unit. The intersection determination / intersection calculation unit is configured to perform intersection determination and intersection calculation with the above-described straight line on at least one side of the polygon having at least one apex of the polygon, and output the intersection presence / absence and the coordinate value of the intersection. ..

[0006]

Embodiments of the present invention will now be described with reference to the drawings.

FIG. 1 is a block diagram of an embodiment of the present invention.

The polygon data storage unit 1 stores the polygon numbers of all polygons for which intersection determination and intersection calculation are performed, the side numbers constituting the polygons, the vertex numbers at both ends thereof, and the coordinate values of the vertices. The virtual grid / vertex number correspondence table creation unit 2 receives the polygon data from the polygon data storage unit 1 and sets a virtual grid that divides the coordinate area for intersection determination and intersection calculation on the polygon into a plurality of areas. Then, a grid number is given to each of the virtual grids, and a virtual grid-vertex number correspondence table that stores the numbers of the vertices of polygons located in the corresponding virtual grid for each grid number is created. The table is stored in the virtual lattice / vertex number correspondence table storage unit 3. The virtual lattice search unit 4 receives the data of the virtual lattice from the virtual lattice / vertex number correspondence table storage unit 3, inputs straight line data defining a straight line for performing intersection determination with a polygon and calculation of an intersection point, and the straight line passes through. Search the grid number of the virtual grid.
The intersection determination / intersection calculation unit 5 determines the position within the virtual lattice from the lattice number searched by the virtual lattice search unit and the virtual lattice / vertex number correspondence table stored in the virtual lattice / vertex number correspondence table storage unit 3. The intersection of the sides of the polygon having at least one of the vertices of the polygon to be intersected with the straight line is determined and the intersection is calculated, and the presence or absence of the intersection and the coordinate value of the intersection are output.

FIG. 3 is an explanatory diagram showing an example of a memory pattern of the virtual lattice / vertex number correspondence table storage unit.

For each grid number 21 of the virtual grid, virtual polygon data 22 consisting of the polygon number located in the corresponding virtual grid and the vertex number of the polygon is stored.

FIG. 4 is an explanatory diagram for explaining the principle of the virtual lattice.

The virtual grid means the grid lines 3 at appropriate intervals on the coordinate area 31 for judging intersections and calculating intersections on a polygon.
2 is set, and the grid number IJ is set for each minimum area surrounded by the grid lines 32, and the coordinate area in which intersection determination and intersection calculation on the polygon are performed is divided into small areas for each grid number. Is a virtual one for.

When the line segment AB is superposed on the coordinate area 31, the area for which intersection determination is required is only the area shaded in the drawing, and the contour line or the like which is the other party for the intersection determination is also required. If the area where the intersection determination needs to be performed is obtained again, the area that truly needs the intersection determination and the intersection calculation is determined.

Next, the function of each unit will be described in more detail.

The virtual grid / vertex number correspondence table creation unit 2 first creates a virtual grid on the coordinate area for polygon intersection determination and intersection calculation and sets the grid number. Next, a virtual lattice / vertex number correspondence table is created in the virtual lattice / vertex number correspondence table storage unit 3. As a virtual lattice / vertex number correspondence table,
A storage area is secured in the virtual lattice / vertex number correspondence table storage unit 3 for each lattice number of the virtual lattice. If the coordinate value (XN, YN) of the vertex of the vertex number N of the polygon P is located in the virtual lattice of the lattice number IJ, the polygon number P is set in the area of the lattice number IJ of the virtual lattice / vertex number correspondence table. The vertex number N is stored. A virtual lattice / vertex number correspondence table is set in the virtual lattice / vertex number correspondence table storage unit 3 for all vertices of all polygons stored in the polygon data storage unit 1.

The virtual grid search unit 4 inputs, for example, the coordinate values of two arbitrary points on the straight line L as data defining the straight line L for performing intersection determination and intersection calculation with a polygon, and the virtual grid / vertex number correspondence The virtual grid created by the table creation unit 2 is searched for the grid number of the virtual grid through which the straight line L passes or contacts and is output to the intersection determination / intersection calculation unit 5.

The intersection determination / intersection calculation unit 5 is, for example, a straight line as data defining a polygon data storage unit 1, a virtual lattice / vertex number correspondence table storage unit 3, and a straight line L for performing intersection determination with a polygon and intersection calculation. The coordinate values of arbitrary two points on L and the lattice number of the virtual lattice searched by the virtual lattice search unit 4 are input, and at least one end of all the vertices located in the virtual lattice is searched for all the searched virtual lattices. The intersection of all the sides of the polygon and the straight line L is determined and the intersection is calculated.

If the virtual lattice with the lattice number IJ is first searched by the virtual lattice retrieval unit 4, the region with the lattice number IJ is input from the virtual lattice / vertex number correspondence table storage unit 3. If the polygon number P and the vertex number N are stored at the beginning of the area of the lattice number IJ, from the polygon data storage unit 1,
The coordinate value of the vertex with the polygon number P and the vertex number N, and the coordinate value of the vertex of the M point of the vertex numbers M1, M2, ... Enter. Then, a straight line L defined by the coordinate values of the two input points and two points (N, M1) and (N, M2) and ...
.. (N, MM) The intersection determination with the M sides of the polygon P determined by (N, MM) and the intersection calculation are performed.

All the vertices stored in the area of the lattice number IJ of the virtual lattice / vertex number correspondence table storage section 3 are processed in the same manner as the vertex of the polygon number P and the vertex number N. further,
All virtual lattices searched by the virtual lattice search unit 4 are processed in the same manner as the virtual lattice with the lattice number IJ. Finally, as a processing result in the intersection determination / intersection calculation unit 5, the presence / absence of intersection with the straight line L for each polygon number and the coordinate value of the intersection are output.

Next, a case will be described in which after performing intersection determination and intersection calculation between a certain polygon data and the straight line L, intersection determination and intersection calculation between the same polygon data and a straight line L1 different from the straight line L are performed. To do.

When the intersection is determined with the straight line L1 and the intersection is calculated, the processing in the polygon data storage unit 1 and the virtual lattice / vertex number correspondence table preparation unit 2 is the same as when the intersection is determined with the straight line L and the intersection is calculated. They are the same and do not need to be processed again, and the contents stored in the virtual lattice / vertex number correspondence table storage unit 3 may be the same.

The processes in the virtual grid search unit 4 and the intersection determination / intersection calculation unit 5 use the data defining the straight line L1 instead of the data defining the straight line L to determine the intersection with the straight line L and calculate the intersection. Do the same as you would. Finally, as the processing result in the intersection determination / intersection calculation unit 5, the presence / absence of intersection with the straight line L1 for each polygon number and the coordinate value of the intersection are output.

[0023]

As described above, according to the present invention, a virtual grid is set that divides a coordinate area that receives polygon data from the polygon data storage unit and performs intersection determination and intersection calculation on the polygon into a plurality of coordinate areas. The virtual lattice / vertex number correspondence table storing unit assigns a lattice number to each of the virtual lattices, and stores a virtual lattice / vertex number correspondence table storing the numbers of the vertices of polygons located in the virtual lattice for each lattice number. The virtual lattice / vertex number correspondence table is created and stored in the virtual lattice / vertex number correspondence table storage unit, and straight line data defining a straight line for performing intersection determination with a polygon and calculation of an intersection is input and the straight line passes. The lattice number of the virtual lattice is searched by the virtual lattice search unit, and the intersection determination / intersection calculation unit calculates a polygon with at least one apex of the polygon located in the virtual lattice of the lattice number searched by the virtual lattice search unit. On the side Therefore, by performing the intersection determination with the straight line and the intersection calculation, and outputting the presence / absence of the intersection and the coordinate value of the intersection, it is possible to shorten the processing time for the intersection determination and the intersection calculation.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of the present invention.

FIG. 2 is a block diagram showing a conventional intersection determination / intersection point calculation method between a polygon and a straight line.

FIG. 3 is an explanatory diagram showing an example of a memory pattern of a virtual lattice / vertex number correspondence table storage unit.

FIG. 4 is an explanatory diagram for explaining the principle of a virtual lattice.

[Explanation of symbols]

 1 polygon data storage unit 2 virtual lattice / vertex number correspondence table creation unit 3 virtual lattice / vertex number correspondence table storage unit 4 virtual lattice search unit 5 intersection determination / intersection calculation unit 21 lattice number 22 virtual polygon data 31 coordinate area 32 Grid line

Claims (1)

[Claims] 1. From the polygon numbers of all polygons for which intersection determination and intersections are calculated, the side numbers of each side forming the polygon, the vertex numbers at both ends of each side, and the vertex coordinate values. And a polygon data storage unit that stores polygon data, and input straight line data that defines a straight line to determine the intersection with the polygon and calculate the intersection, and determine whether there is an intersection and output the coordinate value of the intersection. In an intersection determination / intersection calculation method of a polygon and a straight line including an intersection calculation unit, a plurality of coordinate areas for receiving the polygon data from the polygon data storage unit and performing intersection determination and intersection calculation on the polygon A virtual lattice to be divided into is set, a lattice number is given to each virtual lattice, and a virtual lattice-vertex number correspondence table storing the numbers of the vertices of the polygons located in the corresponding virtual lattice for each lattice number is created. A virtual grid / vertex number correspondence table creation unit to create, a virtual grid / vertex number correspondence table storage unit to store the virtual grid / vertex number correspondence table created by the virtual grid / vertex number correspondence table creation unit, and the polygon A virtual lattice search unit for inputting straight line data defining a straight line for performing intersection determination and calculation of an intersection and searching for a lattice number of the virtual lattice through which the straight line passes, and a lattice number searched by the virtual lattice search unit. An intersection determination / intersection calculation unit that outputs an intersection determination and intersection calculation with the straight line with respect to a side of the polygon having at least one apex of the polygon located in the virtual lattice, and outputs the coordinate value of the intersection; An intersection determination / intersection calculation method between a polygon and a straight line, which includes