平面上の点列をあらわす(x,y)のリストがあり、ランダムな新たな1点を考えます。
その点から上下左右8方向にある最近と最遠の交点を効率よく探したいです。
補足にあるのが効率が悪いプログラムです。
最も効率が良いスクリプトには、少ないですが500ポイントを差し上げます。
説明に解りにくい部分があれば質問してください。
よろしくお願いいたします。
参考コード（一部直しました）
3
2
@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
No.1
814
232
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)
4
2
2
コメント（0件)