CROSSING JUDGMENT AND INTERSECTION CALCULATION SYSTEM FOR POLYGON AND STRAIGHT LINE

摘要

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.;COPYRIGHT: (C)1993,JPO&Japio