- 구 볼록 다각형들의 최대 교차를 찾기 위한 효율적인 구 분할 방식
- ㆍ 저자명
- 하종성
- ㆍ 간행물명
- 한국CAD/CAM학회논문집
- ㆍ 권/호정보
- 2001년|6권 2호|pp.101-110 (10 pages)
- ㆍ 발행정보
- 한국CAD/CAM학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
The maximum intersection of spherical convex polygons are to find spherical regions owned by the maximum number of the polygons, which is applicable for determining the feasibility in manufacturing problems such mould design and numerical controlled machining. In this paper, an efficient method for partitioning a sphere with the polygons into faces is presented for the maximum intersection. The maximum intersection is determined by examining the ownerships of partitioned faces, which represent how many polygons contain the faces. We take the approach of edge-based partition, in which, rather than the ownerships of faces, those of their edges are manipulated as the sphere is partitioned incrementally by each of the polygons. Finally, gathering the split edges with the maximum number of ownerships as the form of discrete data, we approximately obtain the centroids of all solution faces without constructing their boundaries. Our approach is analyzed to have an efficient time complexity Ο(nv), where n and v, respectively, are the numbers of polygons and all vertices. Futhermore, it is practical from the view of implementation since it can compute numerical values robustly and deal with all degenerate cases.