0

デカルト図のポイント座標を表す数値のリストが 2 つあります。

私の目標は、10 の範囲内の多くのポイントを 1 ポイントと見なすことです。

最初の例:

  • 最初の点 (1,2)
  • 2 点目 (2,3)
  • 3 番目の点 (3,4)
  • 4点目 (80,90)

座標リスト:

#(1)
x = [1,2,3, 80] 
Y = [2,3,4, 90 ]

10 の範囲 (x と y の両方) で最も近い点を削除したいと思います。最初の 3 つの数値を 1 つの数値と見なすことができます。

結果は次のとおりです。

x = [1, 80] and y = [2, 90]  or 
x = [2,80] and y = [3, 90] or 
x = [3,80] and y = [4, 90]

座標リストが次の場合:

#(2)
x = [1,2,3, 80] 
Y = [2,3,70, 90 ]

最初の 2 つの数字を 1 つと見なすことができます

結果は次のとおりです。

x = [1, 80] and y = [2, 90]  or 
x = [2,80] and y = [3, 90] or

それらが次の場合:

#(3)
x = [1,2, 75, 78 , 80, 101] 
Y = [2,3, 81, 86, 90 , 91]

結果：

x = [1,75, 101] and y = [2,81, 91] or
x = [1,78, 101] and y = [2,86, 91] or
x = [1,80, 101] and y = [2,90, 91] or
x = [2,75, 101] and y = [3,81, 91] or
x = [2,78, 101] and y = [3,86, 91] or
x = [2,80, 101] and y = [3,90, 91] or

この6つのソリューションのうち1つだけが必要です。x = [1,75]またはを持っているかどうかは重要ではありませんx = [1,78]。重要なことは、オンリーワンとして近い数を持つことです。

最後の例:

x = [ 95, 154, 161, 135, 138, 116]
y = [158, 166, 168, 170, 170, 171]

この場合、残るポイントは 3 つだけです。

171 - 170 = 1  =>  138 - 116 = 22   both results are in the range of 25 i choose to delete 116 and 171


170 - 170 = 0  => 138 - 135 = 3 both result are in the range of 25 i delete 170 and 138

170 - 168 = 2  =>  135 - 161 = 26  i cannot delete

168 - 166 = 2 =>  161 - 154 = 7  i delete 168 and 161

166 - 158 = 8 =>  154 - 95 = 59 i cannot delete

x = [95, 154, 161, 135]
Y = [158, 166, 168, 170]

操作を繰り返し、x の 161 と y の 168 を削除します。理由: 168 - 166 = 2 => 161 - 154 = 7

x = [95, 154, 135]
Y = [158, 166,  170]

yリストは昇順です。

それらを比較する最も速い方法は何ですか？

4

2 に答える 2

1

なぜ「操作を繰り返す」のか、またはいつ停止するのかがわからなかったので、ポイントが削除されなくなるまで操作が繰り返されるようにコーディングしました。中間点は、x と y の別々のリストではなく、(x, y) 座標の 2 要素タプルとしてリストに順番に表示されます。

def outrange(pts, rnge):
    partial = pts[::-1]  # current points in reverse order
    i, lastp = 0, []
    while lastp != partial:
        print('%i times around we have: %r' % (i, partial[::-1]))
        i, lastp, partial = (i+1, 
                            partial, 
                            [(pn1x, pn1y) 
                            for (pnx, pny), (pn1x, pn1y) in zip(partial[1:], partial) 
                            if abs(pn1x - pnx) > rnge or abs(pn1y - pny) > rnge
                            ] + partial[-1:])
    return partial[::-1]

if __name__ == '__main__':
    j = 0
    for rnge, x, y in [(10, [1, 2, 3, 80] , [2, 3, 4, 90 ]),
                        (10, [1, 2, 3, 80] , [2, 3, 70, 90 ]),
                        (10, [1,2, 75, 78 , 80, 101], [2,3, 81, 86, 90 , 91]),
                        (25, [ 95, 154, 161, 135, 138, 116], [158, 166, 168, 170, 170, 171])]:
        j += 1
        print('\n## Example %i: Points outside range %s of:' % (j, rnge))
        print('  x = %r\n  y = %r' % (x, y))
        pts = [(xx, yy) for xx, yy in zip(x,y)]
        ans_x, ans_y = [list(z) for z in zip(*outrange(pts, rnge))]
        print('  Answer: x = %r\n          y = %r' % (ans_x, ans_y))

出力は次のとおりです。

## Example 1: Points outside range 10 of:
  x = [1, 2, 3, 80]
  y = [2, 3, 4, 90]
0 times around we have: [(1, 2), (2, 3), (3, 4), (80, 90)]
1 times around we have: [(1, 2), (80, 90)]
  Answer: x = [1, 80]
          y = [2, 90]

## Example 2: Points outside range 10 of:
  x = [1, 2, 3, 80]
  y = [2, 3, 70, 90]
0 times around we have: [(1, 2), (2, 3), (3, 70), (80, 90)]
1 times around we have: [(1, 2), (3, 70), (80, 90)]
  Answer: x = [1, 3, 80]
          y = [2, 70, 90]

## Example 3: Points outside range 10 of:
  x = [1, 2, 75, 78, 80, 101]
  y = [2, 3, 81, 86, 90, 91]
0 times around we have: [(1, 2), (2, 3), (75, 81), (78, 86), (80, 90), (101, 91)]
1 times around we have: [(1, 2), (75, 81), (101, 91)]
  Answer: x = [1, 75, 101]
          y = [2, 81, 91]

## Example 4: Points outside range 25 of:
  x = [95, 154, 161, 135, 138, 116]
  y = [158, 166, 168, 170, 170, 171]
0 times around we have: [(95, 158), (154, 166), (161, 168), (135, 170), (138, 170), (116, 171)]
1 times around we have: [(95, 158), (154, 166), (135, 170)]
2 times around we have: [(95, 158), (154, 166)]
  Answer: x = [95, 154]
          y = [158, 166]

アルゴリズムは、例4の説明に記載されているとおりに実行しましたが、ポイントをドロップして中間ステップで表示すると、メインの質問へのコメントでロジックに質問しました。

私の結果とは異なる他の結果を計算した場合は、なぜ違いが得られたのか、つまり、あなたのアルゴリズムで私が行っていないのは何なのかを述べてください。または、間違いがないか注意深く答えを調べてください。

于 2013-05-09T15:58:01.800 に答える