펜 플로터 또는 유사한 장치에서 펜 리프트 최소화

Question

기계식 펜 플로터에서 플로팅 알고리즘에 대한 참조를 찾고 있습니다.

특히 직선 벡터 목록이 있는데, 각 직선 벡터는 플롯 될 줄을 나타냅니다. 먼저 중복 된 벡터를 제거하여 각 라인을 한 번만 그려 봅니다. 그렇게 쉬운 일입니다.

둘째, 종종 끝점에서 교차하는 많은 벡터가 있지만 항상 그런 것은 아닙니다. 그것들은 어떤 순서로도 그려 질 수 있지만, 계산할 수 있다면 계산하는데 오랜 시간이 걸린다는 것을 이해할지라도, 펜을 들어야하는 횟수를 줄이기위한 명령을 찾고 싶습니다. 교차하는 벡터는 도움이되는 경우 작은 벡터로 분리 할 수 ​​있습니다. 그러나 일반적으로 펜이 직선으로 움직이는 경우 최대한 길게 움직이는 것이 가장 좋습니다. 따라서, 끝에서 끝까지 연결된 두 개의 평행 벡터를 단일 벡터 등으로 결합 할 수 있습니다.

그래프 이론 문제는 다소 다양하지만이 점에 대해서는 많이 알지 못합니다. 누구든지 내가 참고해야 할 참조 또는 알고리즘을 가르쳐 줄 수 있습니까? 아니면 예제 코드일까요?

감사합니다,

닐

Answer 1

이 문제는 NP 완전 문제이다 Chinese postman problem의 예입니다. 가장 잘 알려진 NP 완전 문제는 Travelling Salesman입니다. 모든 NP 완전 문제에 공통적 인 점은 모두가 서로 서로 번역 될 수 있다는 것입니다. 입력에서 노드 수의 다항식 종속 인 시간에 이들 중 임의의 것을 해결하기위한 알려진 알고리즘은 없으며 비 다항식 (NP)입니다.

귀하의 경우에는 몇 가지 간단한 경험적 방법을 제안합니다. 그것을 과장하지 말고 가능한 한 직선으로가는 것과 같은 간단한 것을 선택하고 가장 가까운 시작점으로 펜을 들고 거기에서 계속 진행하십시오.