4

ポイントに対するポリゴンの巻き数を計算するアルゴリズムを実装する方法を考えようとしています。現在の実装は次のとおりです: (コードが機能するように更新されていることに注意してください)

(defn winding-num
  "Return winding number of polygon
  see Alciatore "
  [poly point]
        ; translate poly such that point is at origin
  (let [translated-poly (map #(vec-f - % point) poly)]
    ; w is wind-num
    (loop [vertices translated-poly w 0]
      (cond
        (= (count vertices) 1)
        w

        :else
        (let [x1 (first (first vertices))
              x2 (first (second vertices))
              y1 (second (first vertices))
              y2 (second (second vertices))]
          (cond 
            (and (< (* y1 y2) 0)
                 (> (+ x1 (/ (* y1 (- x2 x1))
                         (- y1 y2)))
                    0))
            (if (< y1 0)
                (recur (rest vertices) (inc w))
                (recur (rest vertices) (dec w)))

            (and (zero? y1)
                 (> x1 0))
            (if (> y2 0)
                (recur (rest vertices) (+ w 0.5))
                (recur (rest vertices) (- w 0.5)))

            (and (zero? y2)
                 (> x2 0))
            (if (< y1 0)
                 (recur (rest vertices) (+ w 0.5))
                 (recur (rest vertices) (- w 0.5)))

            :else
            (recur (rest vertices) w)))))))

これに関する私の問題は

  • 可能であれば、明示的な再帰よりも高いレベルで動作するループ構造を使用することが望ましいと人々は言います。たとえばmap、、、forなどreduce。
  • rest 関数はベクトルをリストに変換します

やインデックスを使った実装も考えられますが、forインデックスを使わないほうがいいとも聞きます。

各反復で連続する値にアクセスする必要があるベクトル アルゴリズムを処理する慣用的な方法はありますか?

4

3 に答える 3

4

一般に、シーケンスの連続する値に一度に 2 つずつアクセスする場合は、パーティション関数を使用できます。Partition を使用すると、グループ サイズとステップ サイズを指定できます。

user> (partition 2 1 (range 10))
((0 1) (1 2) (2 3) (3 4) (4 5) (5 6) (6 7) (7 8) (8 9))
于 2013-04-30T04:04:19.960 に答える
1

それは本当にアルゴリズムの形状に依存します。一般的に言えば、高レベルの構造は明示的な再帰よりも理解しやすいですが、問題の形によってはこれがわかりにくい場合があります。

その他の注意事項:

restリストではなくシーケンスを返します。ここは関係ないはずです。

破壊を利用する必要があります。例えば：

    (let [x1 (first (first vertices))
          x2 (first (second vertices))
          y1 (second (first vertices))
          y2 (second (second vertices))

これは次のように置き換えることができます:

(let [[x1 y1] [x2 y2]] vertices] ... )

ただし、これを実装するのはそれほど難しいアルゴリズムではありませんreduce。

(defn inc-dec 
  "Convenience function for incrementing and decrementing"
  ([condition i] (if condition (inc i) (dec i)))
  ([condition i amount] (if condition (+ i amount) (- i amount))))

(defn winding-num
  [poly point]
  (let [translated-poly (map #(map - % point) poly)
        winding-reducer
          (fn winding-reducer [w [[x1 y1] [x2 y2]]]
            (cond 
              (and (< (* y1 y2) 0)
                      ; r
                   (> (+ x1 (/ (* y1 (- x2 x1))
                           (- y1 y2)))
                      0))
               (inc-dec (< y1 0) w)

              (and (zero? y1) (> x1 0))
               (inc-dec (> y2 0) w 0.5)

              (and (zero? y2) (> x2 0))
               (inc-dec (< y1 0) w 0.5)

              :else w))
        ]
    (reduce winding-reducer 0 (partition 2 1 translated-poly))))
于 2013-04-30T03:15:09.327 に答える