Arbitrary polygon intersection area calculation method based on probability statistics

Abstract

The invention discloses an arbitrary polygon intersection area calculation method based on probability statistics. The arbitrary polygon intersection area calculation method comprises steps that with help of a GPU, rasterization of arbitrary polygons is realized, and the polygons expressed by vertex coordinates are converted into polygon raster images expressed by rasters; the valuation and the correction of the position identifiers of the rasters are carried out according to the intersection condition of the raster images; the arbitrary rasters are selected from a raster field to simulate the whole raster area to improve time performance; the number of the intersection rasters in the arbitrary rasters is counted, and then the intersection area is calculated. The above mentioned calculation method is not restricted by the concavity and the convexity of the polygons, and the parallelism feature of the GPU is adopted, and by comparing with the calculation methods with the help of the GPU, a processing speed is greatly improved, a principle is simple, and realization is convenient. According to an experimental result, the calculation method is suitable for the arbitrary complicated polygons, and the singularity problems of the conventional calculation methods are prevented, and therefore good robustness is provided.

Description

technical field [0001] The invention relates to the area calculation field of computer graphics and image processing, in particular to a method for calculating the intersection area of ​​arbitrary polygons based on probability statistics. Background technique [0002] The intersection area of ​​plane polygons is widely used. In the fields of computer graphics, computational geometry and computational fluid dynamics, it is necessary to calculate the area of ​​the common coverage area of ​​intersecting polygons. [0003] The existing methods for calculating the intersection area of ​​polygons are generally implemented by a general-purpose processor (CPU) of a computer in a serial processing manner. In recent years, in the fields of computer animation, virtual reality, etc., in order to express richer details, the existing CPU-based serial processing method can no longer meet the fast and real-time requirements in the application of polygon intersection area calculation. [00...

AI Technical Summary

Problems solved by technology

However, in the prior art, for the calculation of the polygon intersection area, there is still a lack of an engineering implementation method based on GPU processing to complete the polygon intersection area

[0005] In addition, from the perspective of the shape of the intersecting polygons, most of the existing polygon intersection area calculation methods are calculated for the intersection area of ​​convex polygons, and for the intersection of concave polygons, most calculation methods need to triangulate or convexize the concave polygon first. Minute

Since the subdivision itself is more complex and will bring more edges to do intersection testing, this greatly increases the amount of calculation, especially for polygons with many concave points or a large number of intersection points

Therefore, in the prior art, the calculation of the intersection area of ​​concave polygons takes a lot of time, the workload is heavy, and the efficiency is low. Compared with the calculation of the intersection area of ​​convex polygons, the calculation of the intersection area of ​​concave polygons seems to be powerless.

Images