라인에서 최적의 위치 지점을 찾는 방법은 무엇입니까?

-5

줄이 주어지고 한 무리의 줄이 주어집니다. 나는 주어진 점으로부터의 거리의 합이 최소가되는 점을 찾아야 만한다. 에 구현할 알고리즘을 찾을 수 없습니다. 미리 감사드립니다.라인에서 최적의 위치 지점을 찾는 방법은 무엇입니까?

고전적인 최소화 문제 *입니다. 그것에 대해 배워야합니다. –

모든 점을 둘러싸는 직사각형을 찾아서 시작하십시오. 그러면 X와 Y에 대한 대략적인 검색 범위가 생깁니다. – user3386109

@ user3386109이 직사각형에는 반드시 선이 포함되지 않습니다. –

일반성의 손실없이 선은 X 축 (그렇지 않으면 전체 지오메트리를 회전)입니다. 그럼 당신은 당신이 불행하게도

Sum (X - Xk)/√[(X - Xk)² + Yk²] = 0

첫 번째 파생

을 취소하여 할 수있는

Sum √[(X - Xk)² + Yk²]

을 최소화하려면,이 수치 방법이 필요합니다 비선형 방정식이다. 단순히 X* 평균 가로축 인 점 (X*, 0)을 제공

Sum (X - Xk) = 0

를 해결하여 당신은 제곱 거리의 합의 최소화 부를 사용할 수있는 시작 근사치로

Sum [(X - Xk)² + Yk²]

2016-11-02 19:17:34

주어진 포인트 중 어느 것도 라인에 없다면 Newton-Raphson을 사용하면 잘 작동하는 것 같습니다. 그러나 포인트 중 일부가 라인에 있다면 목표는 (이 시점에서) 차별화되지 않으며 모든 것이 그렇게 좋지 않습니다. – dmuir

답변