폴리곤의 부울 연산
Boolean operations on polygons폴리곤의 부울 연산은 컴퓨터 그래픽스의 하나 이상의 폴리곤 세트에서 작동하는 부울 연산(AND, OR, NOT, XOR, ...) 세트입니다.이러한 조작 세트는 컴퓨터 그래픽스, CAD 및 EDA(집적회로 물리 설계 및 검증 소프트웨어)에서 널리 사용됩니다.
알고리즘
- 그리너호만 클리핑 알고리즘
- Vatti 클리핑 알고리즘
- 서덜랜드-Hodgman 알고리즘(특례 알고리즘)
- Weiler-Atherton 클리핑알고리즘(특례 알고리즘)
소프트웨어에서의 사용
폴리곤의 부울 연산을 위한 초기 알고리즘은 비트맵 사용을 기반으로 했습니다.폴리곤 도형을 모델링할 때 비트맵을 사용하면 많은 단점이 있습니다.단점 중 하나는 폴리곤의 해상도가 폴리곤을 나타내기 위해 사용되는 비트 수에 비례하기 때문에 메모리 사용량이 매우 클 수 있다는 것입니다.해상도가 높을수록 더 많은 비트 수가 필요합니다.
폴리곤의 부울 연산을 위한 최신 구현에서는 평면 스위프 알고리즘(또는 스위프 선 알고리즘)을 사용하는 경향이 있습니다.폴리곤의 부울 연산에 평면 스위프 알고리즘을 사용한 논문 목록은 아래 참조에서 찾을 수 있습니다.
같은 방향의 볼록 폴리곤 및 모노톤 폴리곤에 대한 부울 연산을 선형 [1]시간에 실행할 수 있다.
「 」를 참조해 주세요.
- 부울 대수
- 계산기하학
- 유사한 연산 집합을 사용하여 3차원 형상을 정의하는 방법인 건설적인 솔리드 지오메트리
- 지오메트리 처리
- General Polygon Clipper(일반 폴리곤 클리퍼), 클리핑 작업 결과를 계산하는 C 라이브러리
메모들
- ^ 를 클릭합니다Katz, Matthew J.; Overmars, Mark H.; Sharir, Micha (1992), "Efficient hidden surface removal for objects with small union size", Computational Geometry: Theory and Applications, 2 (4): 223–234, doi:10.1016/0925-7721(92)90024-M.
참고 문헌
- Mark de Berg, Marc van Kreveld, Mark Overmars 및 Ottfried Schwarzkopf, 컴퓨터 기하학 - 알고리즘과 응용 프로그램, 제2판, 2000년
- 존 루이스 벤틀리와 토마스 A.Ottmann, 기하학적 교차로 보고 및 계산을 위한 알고리즘, 컴퓨터의 IEEE 트랜잭션, Vol. C-28, No., 1979년 9월, 643-647 페이지
- Jon Louis Bentley와 Derick Wood, 직사각형 교차로 보고를 위한 최적의 최악의 경우 알고리즘, IEEE Transactions on Computers, Vol.C-29. No.7, 1980년 7월, 571-577페이지
- Ulrich Lauther, 부울 마스크 연산을 위한 O(N log N) 알고리즘, 제18회 설계 자동화 컨퍼런스, 1981, 페이지 555-562
- 제임스 A.Wilmore, IC 마스크에 대한 효율적인 부울 운영, 제18회 설계 자동화 컨퍼런스, 1981, 페이지 571–579
- Nievergelt, J.; Preparata, F. P. (October 1982). "Plane-Sweep Algorithms for Intersecting Geometric Figures". Communications of the ACM. 25 (10): 739–747. CiteSeerX 10.1.1.83.3275. doi:10.1145/358656.358681.
- Thomas Ottmann, Peter Widmayer 및 Derick Wood, "부울 마스킹 문제를 위한 빠른 알고리즘", 컴퓨터 비전, 그래픽스 및 이미지 처리, 30, 1985, 페이지 249–268
외부 링크
- UIUC 계산 지오메트리 페이지
- 데이브 에버리가 쓴 건설적인 평면 기하학.
- 소프트웨어
- 마이클 레오노프는 폴리곤 클리퍼의 비교를 정리했다.
- Angus Johnson은 또한 세 개의 클리핑 라이브러리를 비교했습니다.
- SINED GmbH는 3개의 폴리곤 클리퍼의 퍼포먼스와 메모리 사용률을 비교했습니다.
- rogue-modron.blogspot.com에서 5개의 클리핑 라이브러리 비교
- 3D 부울 작업을 위한 상용 라이브러리: sgCore C++/C# 라이브러리.
- comp.graphics.algorithms FAQ, 2D 및 3D 폴리곤의 수학적 문제에 대한 해결 방법.
- Matthias Kramm의 gfxpoly, 2D 폴리곤용 무료 C 라이브러리(BSD 라이선스).
- Klaas Holwerda의 Boolean(2D 폴리곤용 C++ 라이브러리).
- David Kennison의 Polypack은 Vatti 알고리즘을 기반으로 한 FORTRAN 라이브러리입니다.
- C++로 쓰여진 폴리곤 클리퍼 클레이머 슈트의 클리퍼.
- Michael Leonov의 poly_Boolean, C++ 라이브러리, Schutte 알고리즘을 확장합니다.
- Angus Johnson's Clipper는 Vatti 알고리즘을 기반으로 한 오픈 소스 프리웨어 라이브러리(Delphi, C++ 및 C#)입니다.
- GeoLib, C++ 및 C#에서 이용 가능한 상용 라이브러리.
- 앨런 머타의 GPC General Polygon Clipper 라이브러리입니다.
- 2D 폴리곤용 PolygonLib, C++ 및 COM 라이브러리(대형 폴리곤 세트, 빌트인 공간 인덱스에 최적화됨).
