문제

시끄러운 x, y 포인트 목록이 분류되지 않은 목록이 있습니다. 그러나 그들은 세상을 통한 길을 형성합니다. 라인 세그먼트를 사용 하여이 데이터의 근사치를 그릴 수있는 알고리즘을 원합니다.

이는 선에 맞는 알고리즘을 사용하여 선형 데이터의 근사치를 선택하는 방법과 유사합니다. 경로가 전 세계에서 구부러지고 바람이 부는 것이기 때문에 내 문제는 더 어렵습니다.Alt Text http://www.praeclarum.org/so/pathfinder.png

누구든지이를 달성하기 위해 표준 / 강력한 / 이해하기 쉬운 알고리즘을 알고 있습니까?

Q & A:

Noisy라는 것은 무엇을 의미합니까? 경로를 이상적인 실현을 받았다면 X 및 Y 요소에 가우스 노이즈가 추가 된 이상적인 경로에서 내 포인트 세트가 샘플링됩니다. 나는 그 노이즈의 평균 또는 표준 편차를 모른다. STD 개발자를 추측 할 수 있습니다 ...

포인트가 근처에 있지만 근사하지 않습니까? 예.

그가 길의 형태에 대한 선험적 정보가 있습니까? 그러한 정보를 얻는 다른 방법이 있습니까? 불행히도.

도움이 되었습니까?

해결책

분류되지 않은 목록을 사용하면 각 세그먼트에 어떤 포인트를 포함 해야하는지 알 수 없으므로 가장 가까운 지점으로 갈 수 있다고 생각합니다.

한 가지 방법은 시작점을 무작위로 선택하고 각 단계에서 다음 지점으로 가장 가까운 지점을 선택하는 것입니다. 처음 두 지점을 세트 S에 추가하십시오.

RMS가 값을 초과 할 때까지 S의 점에 선을 맞추고 S를 지우고 새 라인을 시작하십시오.

연속 라인의 교차점은 세그먼트의 끝점이 될 것입니다.

다른 팁

베 지어 보간 문제에 맞을 수 있습니다.

Bezier Interpolation

그러나 이것은 포인트의 순서를 경로로 다루지 않습니다. 고려해야 할 여러 가지 방법이 있습니다.

  • "최적의"경로 유형 (예 : 경로의 각 지점에서 가장 작은 방향 변경, 모든 지점을 통한 가장 짧은 경로) NP 완료가 줄어 듭니다. 여행 세일즈맨 문제 (TSP).
  • "합리적인"경로는 노드를 클러스터링 한 다음 클러스터 사이와 클러스터 내에서 경로. 물론 클러스터가 클수록 클러스터 수가 많을수록이 작은 문제는 큰 N TSP처럼 보입니다.
  • 한축으로 점을 주문합니다. 2 개 이상의 축이 있으면 일부는 치수 감소 전략이 유용 할 수 있습니다. 예를 들어 독립적 인 구성 요소 분석.

포인트가 서로 가까이 있으면 정상적인 "직선"라인 (직교 라인)이 될 수 있습니다. 정상을 사용합니다 스무딩 알고리즘. 당신은 세상이 평평한 것으로 볼 수 있습니다.

그들이 멀리 떨어져 있다면, 당신은 사용하여 지구의 반올림을 보상해야합니다. 큰 원 지점에서 포인트로 이동합니다. 그렇지 않으면 직선이 더 긴 길을 만들 것입니다.

포인트가 직선을 만들기에는 너무 멀다면 그것은 당신의 선택입니다.

또한 각 지점을 "방문"해야하는지 또는 가까이 가야하는지, 근처가 얼마나 가까운 지 알아야합니다.

코스를 비행기, 선박 또는 다른 여행자에게 보내야하는 경우 각 지점을 방문해야 할 것입니다. 객체에서 GPS 데이터를 가져 오면 화면에 코스를 플로팅하고 노이즈를 제거하고 싶을 것입니다.


편집을 본 후 :이것이 플롯하려는 일부 궤적을 움직이는 물체 인 경우 x/y 값 대신 방향과 속도를 부드럽게 할 수 있습니다. (측정 된 값 (X)을 고정시키고 y-interVal을 증가시키는 것이 훨씬 쉬워집니다.)

다음은 데이터의 주문 문제를 해결할 수있는 휴리스틱 핵입니다.

  • 당신은 충분한 포인트가 있습니다
  • 점 사이의 평균 거리는 경로에서 예상되는 가장 작은 곡률 반경에 비해 작습니다.
  • 점 사이의 평균 거리는 STD에 비해 크지 않습니다. 데브. 소음의
  • 경로는 자체 교차가 아닙니다 (운이 좋을 수도 있지만 보장은 없습니다)

다음과 같이 진행하십시오.

  1. 시작점을 선택하십시오 (임의의 수단보다는 의미있는) 출발점, P1.
  2. 일부 클러스터링 거리 내에있는 모든 지점을 찾으십시오. R_CP1. 선택하다 R_C 예상 회전 반경에 비해 작지만 산란에 비해 큽니다.
  3. 이 클러스터를 호출하십시오 C1.
  4. 포인트를 찾으십시오 Q1 위치의 평균 C1.
  5. 포인트에 줄을 맞추십시오 C1 클러스터의 가장자리로 (또는 그 이상) 프로젝트를 진행하고 원래 데이터에서 가장 가까운 지점을 찾으십시오. 그 지점을 레이블을 지정합니다 P2.
  6. 데이터가 부족할 때까지 2-5 단계를 반복하십시오.

이제 새로운 포인트 목록이 있습니다 Q1..QN 주문됩니다.

내 머리 꼭대기에서 매우 거칠고 꽤 좋은 조건에서만 작동합니다 ...


자체 교차 행동은 (5) 단계에서 새로운 예상 선이 이전의 최대 각도 내에 있다는 것을 요구함으로써 개선 될 수 있습니다.

Bezier 곡선의 문제점은 실제로 샘플링 한 포인트와 점 샘플이 약간 왜곡 되었음에도 불구하고 실제로 진행되지 않는다는 것입니다. Bezier 곡선은 실제로 몇 마일 떨어져있을 수 있습니다.

더 나은 근사치와 원본 이미지와 더 유사한 것처럼 보이는 솔루션은 Catmull-ROM 스플라인 곡선의 모든 지점이지만 실행되기 때문입니다.

내 접근 방식은 먼저 포인트 목록을 정렬 한 다음 Bezier 곡선을 사용하는 것입니다.

트릭은 물론 분류입니다. 하나의 임의의 지점으로 시작하여 가장 가까운 지점을 찾으십시오. 이 두 가지가 연결되어 있다고 가정합니다. 이 두 가지 엔드 포인트를 사용하면 가장 가까운 지점을 찾으십시오. 엔드 포인트까지의 거리가 작은 것이 그 지점에 연결되어 있다고 가정하십시오. 모든 지점이 연결될 때까지 반복하십시오.

나는이 접근법에 여전히 문제가 있다고 가정하지만, 아마도 그것을 시작점으로 사용할 수있을 것입니다 (의도의 의도).

편집하다: 출발점이 다르면 여러 번 수행 한 다음 결과가 다른 위치를 확인할 수 있습니다. 그것은 적어도 당신에게 약간의 자신감을 주며, 어떤 포인트가 서로 연결되어 있습니다.

완전히 다른 접근법은 다른 제약이 필요하지 않지만 세부 사항은 응용 프로그램에 따라 다를 수 있습니다. 길 주위에 "밀도가 높은 포인트 구름"이 있다면 가장 잘 작동합니다.

곡선과 포인트 클라우드의 차이를 정의하는 "비용"함수를 사용하십시오. 매개 변수화 된 곡선과 표준 최적화 알고리즘을 사용하십시오. - 또는 - 시작부터 끝까지 직선 곡선으로 시작한 다음 유전자 알고리즘을 사용하여 수정하십시오.

일반적인 비용 기능은 각 지점과 곡선 사이의 가장 작은 거리를 취하고 제곱을 합치는 것입니다.

최적화 또는 유전자 알고리즘을 제안 할 경험이 충분하지 않지만 수행 할 수 있다고 확신합니다. :)

다음과 같이 유전자 알고리즘을 상상할 수 있습니다. 경로는 Waypoints에서 구축 될 것입니다. N Waypoints를 Straigt 라인에 처음부터 끝까지 넣으십시오. (문제에 따라 n을 선택할 수 있습니다). 돌연변이는 다음과 같습니다.

  1. 각 세그먼트에 대해 rnd () <x 인 경우 새로운 웨이 포인트가 중간에 도입됩니다.
  2. 각 웨이 포인트에 대해 x 및 y 좌표는 약간 다양합니다.

비용 기능에 총 길이를 포함해야합니다. 분할이 필요하지 않을 수도 있고 X ( "분할 기회")가 더 많은 웨이 포인트가 도입 될 때 감소해야 할 수도 있습니다. (2) 시작 및 엔드 포인트에 (2) 적용하고 싶지 않을 수도 있습니다.

그것을 시도하는 것이 재미있을 것입니다 ...

나는 "소멸되지 않은 목록"이 당신의 포인트 세트가 완료되지만 그들이 어떤 순서를 여행했는지 모른다는 것을 의미합니다.

가우스 소음은 기본적으로 무시되어야합니다. 우리는 원래의 비 노스 경로를 재구성하려는 시도를 할 수있는 정보가 전혀 없습니다. 그래서 우리가 할 수있는 최선은 포인트가 정확하다고 가정하는 것입니다.

이 시점 에서이 작업은 "가장 좋은"모호한 모호한 "포인트 세트를 통한 최고의 경로 찾기"로 구성됩니다. 나는 유클리드 공간에서 포인트 세트를 주문하려고 시도하는 코드를 채찍질하여 순서를 선호하는 순서를 선호합니다. 메트릭은 구현하기 쉬웠지만,이를 기반으로 순서를 향상시키는 좋은 방법을 생각할 수 없었기 때문에 더 나은 배열을 찾고있는 포인트를 무작위로 바꾸는 것입니다.

따라서 다음은 PLT 체계 코드가 있습니다.

#lang scheme

(require (only-in srfi/1 iota))

; a bunch of trig
(define (deg->rad d)
  (* pi (/ d 180)))

(define (rad->deg r)
  (* 180 (/ r pi)))

(define (euclidean-length v)
  (sqrt (apply + (map (lambda (x) (expt x 2)) v))))

(define (dot a b)
  (apply + (map * a b)))

(define (angle-ratio a b)
  (/ (dot a b)
     (* (euclidean-length a) (euclidean-length b))))

; given a list of 3 points, calculate the likelihood of the
; angle they represent. straight is better.
(define (probability-triple a b c)
  (let ([av (map - a b)]
        [bv (map - c b)])
    (cos (/ (- pi (abs (acos (angle-ratio av bv)))) 2))))

; makes a random 2d point. uncomment the bit for a 3d point
(define (random-point . x)
  (list (/ (random 1000) 100)
        (/ (random 1000) 100)
        #;(/ (random 1000) 100)))

; calculate the likelihood of an entire list of points
(define (point-order-likelihood lst)
  (if (null? (cdddr lst))
      1
      (* (probability-triple (car lst)
                             (cadr lst)
                             (caddr lst))
         (point-order-likelihood (cdr lst)))))

; just print a list of points
(define (print-points lst)
  (for ([p (in-list lst)])
    (printf "~a~n"
            (string-join (map number->string
                              (map exact->inexact p))
                         " "))))

; attempts to improve upon a list
(define (find-better-arrangement start
                                 ; by default, try only 10 times to find something better
                                 [tries 10]
                                 ; if we find an arrangement that is as good as one where
                                 ; every segment bends by 22.5 degrees (which would be
                                 ; reasonably gentle) then call it good enough. higher
                                 ; cut offs are more demanding.
                                 [cut-off (expt (cos (/ pi 8))
                                                (- (length start) 2))])
  (let ([vec (list->vector start)]
        ; evaluate what we've started with
        [eval (point-order-likelihood start)])
    (let/ec done
      ; if the current list exceeds the cut off, we're done
      (when (> eval cut-off)
        (done start))
      ; otherwise, try no more than 'tries' times...
      (for ([x (in-range tries)])
        ; pick two random points in the list
        (let ([ai (random (vector-length vec))]
              [bi (random (vector-length vec))])
          ; if they're the same...
          (when (= ai bi)
            ; increment the second by 1, wrapping around the list if necessary
            (set! bi (modulo (add1 bi) (vector-length vec))))
          ; take the values from the two positions...
          (let ([a  (vector-ref vec ai)]
                [b  (vector-ref vec bi)])
            ; swap them
            (vector-set! vec bi a)
            (vector-set! vec ai b)
            ; make a list out of the vector
            (let ([new (vector->list vec)])
              ; if it evaluates to better
              (when (> (point-order-likelihood new) eval)
                ; start over with it
                (done (find-better-arrangement new tries cut-off)))))))
      ; we fell out the bottom of the search. just give back what we started with
      start)))

; evaluate, display, and improve a list of points, five times
(define points (map random-point (iota 10)))
(define tmp points)
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 100))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 1000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)
(set! tmp (find-better-arrangement tmp 10000))
(printf "~a~n" (point-order-likelihood tmp))
(print-points tmp)

질문에 대한 답변에서 '황금 곡선'을 알고있는 것 같습니다. @jamesh가 제안한대로 '황금 곡선'의 베 지어 곡선을 찾는 것이 좋습니다.

몇 포인트가 있습니까?
언급 한 바와 같이 베 지어 곡선은 비교 한 포인트가 거의 없다면 좋은 아이디어입니다. 포인트가 많으면 DMCKEE가 제안한대로 클러스터를 부수합니다.

그러나 당신 또한 포인트 순서를 정의하기위한 또 다른 제약이 필요합니다. 포인트를 선택하는 방법에 대한 좋은 제안이 많이 있었지만 다른 제약을 도입하지 않으면 가능한 해결책을 제공합니다.

내가 생각할 수있는 가능한 제약 조건 :

  • 가장 짧은 경로
  • 대부분의 직선 세그먼트
  • 최소 총 절대 회전
  • 방향 선호도 (즉, 수평 / 수직은 십자형보다 더 가능성이 높습니다)

모든 경우에 제약 조건을 충족시키기 위해서는 시퀀스의 모든 순열을 테스트해야 할 것입니다. "좋은 추측"으로 시작하면 Cayn은 다른 사람들을 신속하게 종료합니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top