摘要 |
PROBLEM TO BE SOLVED: To obtain inner point decision algorithm which does not require a large calculation quantity and to decide an inner point in a short time by deciding whether a regarding point is present in a polygonal graphic formed of vertexes. SOLUTION: Inner points of a polygon A and the convex polygons B1, B2,..., BM constituting it divisionally are decided. After an inner point decision on a point P is made as to the convex polygon B1, it is evident that the point P is an inner point of the polygon A on condition that the point P is an inner point of the convex polygon B1, and the calculation is finished. When the point P is not an inner point of the convex polygon B1, an inner point decision based upon similar algorithm is made for the next convex polygon B2. When it is decided that the point P is an inner point of the convex polygon B2, it is decided that the point P is an inner point of the polygon A. When not, an inner point decision based upon improved algorithm is made for the next convex polygon B3. When it is decided that the point P is an inner point of none of all the convex polygons, it is judged that the point P is outside the polygon A.
|