平面上の点列との交点を探すpythonのスクリプトを作っていただけないでしょうか。

平面上の点列をあらわす(x,y)のリストがあり、ランダムな新たな1点を考えます。
その点から上下左右8方向にある最近と最遠の交点を効率よく探したいです。

補足にあるのが効率が悪いプログラムです。
最も効率が良いスクリプトには、少ないですが500ポイントを差し上げます。

説明に解りにくい部分があれば質問してください。
よろしくお願いいたします。

回答の条件
  • 1人1回まで
  • 13歳以上
  • 登録:2019/01/12 13:06:32
  • 終了:2019/01/19 13:10:04
id:nobu007t

参考コード(一部直しました)

@staticmethod
    def check_simple(xy, xy_list):
        vect = [(1, 0), (0, -1), (-1, 0), (0, 1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        min_count = 1000
        min_v = vect[0]
        max_count = 0
        max_v = vect[0]
        for v in vect:
            count = 0
            x = xy[0]
            y = xy[1]
            for i in range(1000):
                if (x, y) in xy_list:
                    logger.error("INFO: found count: %d, min_count: %d", count, min_count)
                    if count < min_count:
                        min_count = count
                        min_v = v
                    if count > max_count:
                        max_count = count
                        max_v = v
                    break
                count += 1
                x += v[0]
                y += v[1]
        logger.error("INFO: min_count: %d, max_count: %d", min_count, max_count)
        return min_v, max_v

回答(1件)

id:nobu007t

質問文を編集しました。詳細はこちら

id:Lhankor_Mhy No.1

Lhankor_Mhy回答回数804ベストアンサー獲得回数2322019/01/15 19:26:46

ポイント500pt

O(n)なので大した効率ではないですが、最大と最小を求めるとなると、これ以上の効率化は私の手に余ります。
なお、距離の求め方は、ご提示のコードからチェビシェフ距離だと判断しました。違うようでしたらお知らせください。

import random

xy_list = [ ( random.randint(0,100), random.randint(0,100) ) for i in range(100) ]
xy = ( random.randint(0,100), random.randint(0,100) )

min_v = 100
max_v = 0
for x, y in xy_list:
    temp = None
    dx = abs( x - xy[0] )
    dy = abs( y - xy[1] )
    if dx == 0:
        temp = dy
    if dy == 0:
        temp = dx
    if dx == dy:
        temp = dx
    if temp != None:
        min_v = min( min_v, temp )
        max_v = max( max_v, temp )

print(min_v,max_v,xy,xy_list)
id:nobu007t

Lhankor_Mhy様ありがとうございます。
10000回で20秒→11秒と約2倍早くなりました。

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません