关键词: 射线法, 点包含, 点圆投影, 增量筛选法, 径向分界点

Abstract: According to the problem that 2D/3D point inclusion test approach is complex and low-efficient, we propose a new method based on point circle theory. Projections of different types of singular points and their overlay properties on point circle are geometrically analyzed, and their determinations are proposed. 3D point inclusion test is transformed to 2D point inclusion test, except for the calculation of the plane equation coefficients. Based on the filter and accumulation of edges intersecting with and lying above or below the ray shooting from the test point, the point inclusion can be determined according to the odd/even property of the edges. Common geometric characteristics of the consecutive edges of a polygon lying above or below the 2D ray are recognized, i.e., their y-coordinate values either collectively larger or smaller than that of the test point. A high efficient 2D point inclusion algorithm named increment filter crossing number (IFCN) method is thus established. The experiment results show that the proposed 2D/3D point inclusion algorithms are highly reliable and efficient. They are capable of treating any singularities and suitable for any polyhedrons (manifold, non-manifold, planar-faced or curved-faced surface, etc.) or any polygons.

Key words: ray-crossing, point inclusion, point circle projection, increment filter algorithm, radial dividing point