예 이미지로 설정 라인에서 라인의 윤곽을 상쇄 만들기 루프를 형성하는 등고선 (얇은 파란색 선 참조)? 오프셋은 모든 선에서 일정하며 윤곽선은 항상 관련 선과 평행합니다.는 임의의 토폴로지
입력 라인 토폴로지는 임의적입니다. 즉, 사이클을 포함 할 수 있습니다. 윤곽 루프의 수는 사이클 수에 1을 더한 것과 같습니다. 트리 토폴로지 만 처리하는 솔루션 (주기 없음)도 관심의 대상이 될 수 있습니다.
이 문제를 해결할 수있는 논문이나 관련 알고리즘은 있습니까?
기본 방법은 각도의 bissectrix (오른쪽)를 작성하고 원하는 오프셋 (삼각법의 약간)을 달성 할 수있는 길이를 그리는 것입니다. 그리고 루프 트래버 설 순서로 링크를 연결합니다. 자유로운 종단점에서 다른 캡핑 규칙을 사용할 수 있습니다.
이 작업을 수행하려면 형상 그래프를 평면 그래프 (예 : 쿼드 에지)로 표현해야합니다. 어쩌면 여기보세요 : https://mathoverflow.net/q/23811.
어쨌든,이 방법은 발생할 수있는 중복을 피할 수 없으며, 자기 교차 오프셋하지 않습니다. 이것은 글로벌 접근법을 필요로하는 훨씬 더 어려운 문제이며, 다각형 조합 문제와 유사합니다.
답장을 보내 주셔서 감사합니다. Yves. bisectrix를 따라 점을 배치하는 것이 좋습니다. 그러나 일단 포인트가 끝나는 지점을 알게되면 연결하기 위해 어떤 순서로 계산해야합니다. 순회 (traversal) 주문은 그럴듯하게 들리지만, 각 입력 가장자리의 양쪽에 여러 루프를 동시에 생성해야하기 때문에 복잡하다고 생각합니다. 입력 라인 당 부분 폴리곤 (제안 된 bisectrix 메쏘리를 사용)을 생성하는 것이 더 쉽고 두 폴리곤이 공유하는 모서리를 버려서 함께 융합시킬 수 있습니다. 결과적으로 경계 모서리 만 남게됩니다. – drtommertens
"외부"루프를 포함하여 평면 그래프의 모든 단순 사이클을 정확히 한 번 열거해야합니다. –
"윤곽 루프 수는주기 수에 1을 더한 수와 같습니다. 항상 그렇지는 않습니다. 오프셋 너비보다 작은 내부 루프는 사라집니다. –
맞습니다. 고려하지 않았습니다. – drtommertens
[연결된 일부 줄의 개요 그리기] (https://stackoverflow.com/a/22068534/2521214) – Spektre