복잡한 다각형 (오목한 모양 일 수도 있음)과 입구/출구 지점으로 표시된 가장자리가 몇 개 있습니다. 이 다각형 안에는 임의의 형태의 하나 이상의 봉쇄가있을 가능성이 있습니다. 특정 너비의 경로가 입구/출구 엣지 쌍 사이에 존재하는지 판단하기 위해 어떤 접근법을 사용할 수 있습니까?모양이 무난한지 확인하는 방법
질문을 통해 읽은 것은 숙제 유형처럼 보입니다 - 그렇지 않습니다. 나는 적어도 내가 추구 할 수있는 몇 가지 리드를 갖고 싶다. 이것은 나에게 새로운 것이기 때문이다.
Motion Planning을 살펴보세요. 풍부한 정보가 있습니다.
경로가 너비가 필요한지 여부에 따라 다릅니다. 이동해야하는 객체의 크기가 유한 한 경우 도메인 다각형과 Minkowski의 차이점을 이동 객체의 다각형으로 가져와야합니다.
경로를 정확하게 계산하는 한 가지 방법은 다각형의 가시성 그래프를 계산하는 것입니다. 가시성 그래프에는 도메인 다각형의 꼭지점 (장애물이있는 구멍이있을 수 있음)에 해당하는 꼭지점이 있으며 두 꼭지점은 서로를 볼 수있는 경우 가장자리로 연결됩니다. 입구에 출구를 연결하는 모서리 집합이있는 경우 모양을 무시할 수 없습니다. 최단 경로와 같은 것을 계산할 수도 있습니다. 순진한 방식으로 가시성 그래프를 계산하는 것은 어렵지 않지만 느립니다. 매우 진보 된 알고리즘이 있지만 AFAIK는 구현되지 않았습니다. 나는 몇 년 전, 단지 평범한 결과만으로 몇 가지 구현을 시도했다. 대부분의 경우 정확한 산술 연산을 사용하여 일반 위치에 버텍스를 가정하고 실용적인 응용 프로그램에서는 부동 소수점 숫자를 사용합니다.
네, 개체가 실제로 유한 크기입니다. Minkowski의 차이점을 이끌어 내 주셔서 감사합니다. 전에는 들어 본 적이 없었습니다. –
흥미로운 점은 고마워요! –
나는 이것이 일반적으로 연구 문제라고 생각한다. 그래서 나는 더 구체적인 것을주지 않았다. 당신은 정말로 당신의 제약이 무엇인지 알 필요가 있습니다. – Larry