점을 둘러싸는 다각형을 찾는 알고리즘 - 선만 정의 됨

Question

많은 직선이있는 2D 도면이 있습니다. 모든 행은 수학적으로 알려져 있습니다. 그리고 그들은 다른 사람들과 독립적입니다.

각 줄의 시작점과 끝점을 알면 모든 교차점을 찾기 위해 교차되도록 할 수 있습니다. (자세한 내용은 Autocad에 있지만 코드를 통해서만 작업 할 수 있습니다.) 따라서 Algorythm은 AutoCAD 솔루션보다 더 많이 사용하고 싶지만 AutoCAD 솔루션도 환영합니다.

문제는 다음과 같습니다. 주어진 점 (어느 곳에서나)을 포함하는 작은 폴리곤을 찾고 싶습니다. 그 다각형은 가장 가까운 선에 의해 형성됩니다.

---

상세 사항 :

나는 더 선언 다각형이 없습니다. 그냥 줄. 줄 수, 크기, 위치. 그리고 주어진 지점.

이러한 선은 하나 또는 여러 개의 다각형을 형성 할 수 있습니다. 폴리곤이 어떻게 생겼는지에 대한 규칙은 없습니다. 측면 수에 관계없이 규칙 성이 없습니다. (폴리곤을 형성하는 점은 선들을 교차 시켜서 찾을 수 있고 선들은 유한합니다. 교차하지 않으면 폴리곤을 형성하지 않습니다.)

내 대답은 주어진 폴리곤을 포함하여 가능한 가장 작은 폴리곤입니다 포인트.

Answer 1

나는 다음과 같은 알고리즘이 작동합니다 생각 :

미만 3 선이있는 경우

1. , 종료합니다. 해결책이 없습니다.
2. 목표 지점에 가장 가까운 행을 결정하십시오. 이 라인은 솔루션의 일부로 보장됩니다.
3. P1을 L1에 대한 목표 지점의 수직 투영이라고합시다.
4. P1에 가장 가깝고 반대쪽에있는 L1이있는 다른 선의 두 교차점을 찾습니다. 이 두 지점은 솔루션의 일부로 보장됩니다.
   • 가 이러한 포인트가 없다면 라인 L2와 L3
   • 이러한 점 P2 P3 & 및 통화하자, 해결책은 없다.
각각 & P2 P3에 가장 가까운 상기 목표 지점으로 L1의 동일 측에 있는지 L2 및 L3 각각에 가장 근접한 지점을 찾는다.
6. 반복 4 단계와 5 단계까지 :
   • 두 방향에서 오는 발견 된 라인은
   • 교차점은 두 방향에서오고있는 것과 같은 라인을 찾을 수 할 점은 없습니다 동일한 지점
   • 입니다 기준과 일치하는 이는 솔루션이 없음을 의미합니다.

Answer 2

좋아, 나는 잠시 동안 숙고하고 있었고, 난 작동 믿는 backtracking 알고리즘을 공식화했다. 아이디어는 반 시계 방향으로 다각형을 만들려고 시도한다는 것입니다. 그리고 발견 된 첫 번째 다각형이 가장 작아 지도록 문제를 설정합니다.그렇게하면 우리 모두를 찾을 필요가 없습니다.

알고리즘 :

1. 정렬가 대상 점에 얼마나 가까운 순 선분.
   • 는 이제부터이 정렬 된 순서
   • 목표 지점으로부터의 거리를 계산할 때 무한 선으로 선분을 치료에, 라인을 통해 루프에 돌이 필요할 때마다.
2. 는 방향 "시계 반대 방향"의 선을 따라 2 교차점을 사용하여 가장 가까운 선분와 3 단계를 수행
   • 방향을 의미하는 "반 시계 방향으로"받아 대상 지점을 선의 왼쪽에 놓습니다.
   • 참고 : 1 교차점은 ... 희망
     우리가 목표 지점 새로 발견 줄에

3. 주위에 우리의 방법을 작업 한 후 우리가 끝날 장소입니다

   가. 이미 건설중인 도형의 일부가 아닌 다른 모든 선을 반복하면서이 선과의 교차점을 찾습니다.
   B. 교차점을 대상 점에 대해 시계 반대 방향으로 정렬합니다.
   

4. 현재 줄에서 시계 반대 방향으로 다음 교차점을 찾습니다. 이것이 우리가이 선을 검사하는 첫 번째 점이라면, "다음"점은 우리를이 선으로 데려 오는 교차점 뒤의 점입니다.

   그러한 점 (이것은 우리가 이미 현재 행의 모든 ​​사항을 점검 한 것을 의미 할 수 있습니다), 현재 후보 솔루션은 불가능하다이없는 경우

   A. ...

   • 인 뒤로을 이전 행에 입력하고 4 단계을 그 행의 다음 행과 반복하십시오.
   • 더 이전 라인이없는 경우 (즉, 당신이 모양을 시작 라인에있어), 뒤로를하고 새로운 모양을 시작, 다음 - 가장 가까운 라인 2 단계을한다. 이 왼쪽 (반 시계 방향)의 상 대상 점을 갖지 않는 교점을 형성하는 라인은, 그 때 형성 할 다각형 대상 점을 둘러싸 지 않는 B. 경우

   . 다음 포인트가있는 현재 행에 대해 4 단계을 반복하십시오.
   C. 교차점을 형성하는 선이 처음 시작한 선인 경우
   D를 찾았습니다. 위에 해당하지 않으면 단계 3 교착 점을 형성 한 선분에 대해을 입력하십시오. .

최적화 : 3 개 라인보다 더 적은 경우

1. 는 해결책이 없습니다. 어떤 일도하지 마십시오.
2. 당신은 당신이 그들을 찾을 때, 나는 2 차원 배열을
3. I를 사용하는 것이 좋습니다 이렇게 선택하면 당신이 그 (것)들에게
   • 를 다시 계산하지 않도록 교차점을 캐시 할 수 있습니다 솔루션의 일부가 아님을 알 때 줄을 버리는 것이 좋습니다.
     • 예 : 이미 목표 지점에 가장 가까운 라인을 시도하지만,이 솔루션으로 이어질하지 않은 경우, 그것은 다른 라인에 교차점을 찾을 때 그 라인을 포함하는 이해가되지 않습니다.

비고 :

• 이 알고리즘은 재귀 적으로 구현하는 것이 가장 쉬운 방법 일 것이다.
• 당신은 목표 지점이 선 다각형을 정의 무엇