最快的方法來檢查列表中的任何點是否在bwteen兩個固定點A和B

Question

我有兩個大的點集L1和L2和一個固定點B.我需要一個有效的方法來過濾L1並刪除所有點它們到B的路徑（直線）被L2中的任何點阻塞。

我試過如下：

# Measure distance between two points 
def distance (p1, p2): 
    return ((p2[1] - p1[1])**2 + (p2[0] - p1[0])**2)**0.5 

# Check if point c is on same line between points a and b 
def inBetween (a, b, c): 
    return distance (a, b) == distance (a, c) + distance (b, c) 

def isPathBlocked (L1, L2, B): 
    for A in L1: 
     for C in L2: 
      if inBetween (A, B, C): 
       print "path blocked" 

雖然它的工作原理，但它是非常CPU密集型考慮到L1和L2可以在每個有超過50,000點，併爲此嵌套循環將執行50000 * 50000次。有沒有更好的方法來做到這一點，或有什麼好的算法，我可以在這裏使用？

注：

我應該早點提及，但在L1和L2的所有點COORDS是整數。

注2：

B具有整數COORDS和在L1和L2的所有點從乙一定半徑範圍內（半徑爲約10至10000）。

解決方案：

感謝偉大的答案在下面，我在這裏加入如何與詳盡的解釋使用提供了主要的兩種方法（散列和比較，排序和合並比較）對於那些誰是新的一個例子到算法，它可能會發現它有用：

l1 = [(x,y) for x in range (10) for y in range(10)] 
l2 = [(5,3), (5,1), (8,2), (4,3), (1,5), (3,5), (7,7), (3,7)] 
b = (5,5) 

# instead of using atan2 to calculate polar angles, to improve performance we only 
# calculate (y/x, x>0) which has a unique value for different angles 
# if x == 0 (angle is eigher 90 or -90 degrees) then we use (None, y>0) instead 
def toPolar (p1, p2): 
    if p2[0] != p1[0]: 
     return (float (p2[1] - p1[1])/float (p2[0] - p1[0]), p2[0] < p1[0]) 
    if p2[1] != p1[1]: 
     return (None, p2[1] < p1[1]) 

# Check if b is between a and c, we don't need to check if they 
# are cllinear because they are already when they have same polar angle 
def inBetween (a, b, c): 
    if a[0] <= b[0] <= c[0] or c[0] <= b[0] <= a[0]: 
     return a[1] <= b[1] <= c[1] or c[1] <= b[1] <= a[1] 
    return False 

# b stationary point, l1 the points of interest, l2 blockers 
def hashFilter (b, l1, l2): 
    hashTable = {} 
    # create a hash table of l2 points using polar angles as keys, 
    # if two points have the same polar angle keep only the one that 
    # is closer to b 
    for blocker in l2: 
     key = toPolar (b, blocker) 
     prev = hashTable.get (key) 
     if prev == None or inBetween (b, blocker, prev): 
      hashTable[key] = blocker 
    unBlocked = [] 
    blocked = [] 
    # Remove the points from l1 if they are blocked by any point from l2 
    for point in l1: 
     key = toPolar (b, point) 
     blocker = hashTable.get (key) 
     if blocker == None or not inBetween (b, blocker, point): 
      unBlocked.append (point) 
     else: blocked.append (point) 
    return sorted (blocked) 

def sortFilter (b, l1, l2): 
    # Convert cartesian to polar (sort of) 
    points = [(toPolar(b, x), x) for x in l1] 
    # Sort using polar angle as key 
    points = sorted (points, key = lambda x: x[0]) 
    # Convert cartesian to polar (sort of) 
    blockers = [(toPolar(b, x), x) for x in l2] 
    # Sort using polar angle as key 
    blockers = sorted (blockers, key = lambda x: x[0]) 
    unBlocked = [] 
    blocked = [] 
    ind = 0 
    length = len (blockers) 
    for point in points: 
     if ind >= length: break 
     isBlocked = False 
     subInd = None 
     # Increase index of blockers until we reach a matching polar angle 
     while ind < length and blockers[ind][0] <= point[0]: 
      if blockers[ind][0] == point[0]: 
       # we need to check every point in points(l1) for being blocked 
       # by comparing it to all points in blockers(l2) with 
       # identical polar angle. 
       # However because there could be multiple points and multiple 
       # blockers with the same polar angle, we store the ind of the 
       # first identical polar angle that appears in the blockers list, 
       # so that the next item in points list can loop again over 
       # this group of blockers 
       if subInd == None: subInd = ind 
       if inBetween (b, blockers[ind][1], point[1]): 
        blocked.append (point[1]) 
        isBlocked = True 
        # If we found out that the point is blocked then we break 
        # out of the loop to test the next item in points 
        break 
      ind += 1 
     if not isBlocked: unBlocked.append (point[1]) 
     # Move the index back to the first item in the blockers group with 
     # same polar angle to the last point checked 
     if subInd != None: ind = subInd 
    return sorted (blocked) 

print hashFilter (b, l1, l2) 
print sortFilter (b, l1, l2) 

Answer 1

給定約束（小整數座標），我們可以散列斜坡而不是排序。這取決於以下事實：（1）浮分正確舍入（2）以10000爲界的分母之間的最小差距至少約爲1/10000^2，這是安全的超過1 ulp。

def key(b, p): 
    if p[0] != b[0]: 
     return (float(p[1] - b[1])/float(p[0] - b[0]), p[0] < b[0]) 
    if p[1] != b[1]: 
     return (None, p[1] < b[1]) 
    return None 


def between1(b, p, q): 
    return b <= p <= q or q <= p <= b 


def between2_assume_collinear(b, p, q): 
    return between1(b[0], p[0], q[0]) and between1(b[1], p[1], q[1]) 


def unblocked(b, l1, l2): 
    inner = {} 
    for p in l2: 
     k = key(b, p) 
     if k is None: 
      return 
     q = inner.get(k) 
     if q is None or between2_assume_collinear(b, p, q): 
      inner[k] = p 
    for q in l1: 
     p = inner.get(key(b, q)) 
     if p is None or not between2_assume_collinear(b, p, q): 
      yield q 

這是一些測試代碼。

def demo(b, l2): 
    n = 10 
    l1 = [(x, y) for x in range(n) for y in range(n)] 
    grid = [[' ' for x in range(n)] for y in range(n)] 
    for q in unblocked(b, l1, l2): 
     grid[q[1]][q[0]] = '*' 
    grid[b[1]][b[0]] = '@' 
    for p in l2: 
     grid[p[1]][p[0]] = '2' 
    for row in grid: 
     print(''.join(row)) 


demo((5, 5), [(5, 3), (5, 1), (8, 2), (4, 3), (1, 5), (3, 5)]) 

替代key功能是速度較慢，但​​適用於所有的整數：

import fractions 


def key(b, p): 
    d0 = p[0] - b[0] 
    d1 = p[1] - b[1] 
    g = fractions.gcd(d0, d1) 
    if g == 0: 
     return None 
    g = abs(g) 
    return (d0 // g, d1 // g) 

Answer 2

1. 有更有效的方法來確定點是否在兩個另一點之間 - 使用跨產品

2. 對於這個問題確實存在有複雜度爲O（NlogN）更快的算法方法（而你的蠻力是O（N^2））

   • 排序兩個點集由極角對B點
   • 步行雖然兩組在合併方式和比較的角度

Answer 3

這是一個小型的實現我的意思（這是一樣的想法＃2 MBo's答案）：

import random 
import math 
from collections import namedtuple 


Cartesian = namedtuple('Cartesian', ('x', 'y', 'sample')) 
Polar = namedtuple('Polar', ('r', 'phi', 'sample')) 


def to_polar(cartesian, origin): 

    x_diff = cartesian.x - origin.x 
    y_diff = cartesian.y - origin.y 
    r = math.hypot(x_diff, y_diff) 
    phi = math.atan2(y_diff, x_diff) 

    return Polar(r=r, phi=phi, sample=cartesian.sample) 


def to_cartesian(polar, origin): 

    x = polar.r*math.cos(polar.phi) + origin.x 
    y = polar.r*math.sin(polar.phi) + origin.y 

    return Cartesian(x=x, y=y, sample=polar.sample) 


random.seed(45432) # get reproducibe results 

SCALE = 100 
N_SAMPLES = 5 

B = Cartesian(x=SCALE*random.random(), y=SCALE*random.random(), sample='B') 

L1_cartesian = [Cartesian(x=SCALE*random.random(), 
          y=SCALE*random.random(), 
          sample='L1') 
       for _ in range(N_SAMPLES)] 
L1_polar = [to_polar(cartesian=l1, origin=B) for l1 in L1_cartesian] 

L2_cartesian = [Cartesian(x=SCALE*random.random(), 
          y=SCALE*random.random(), 
          sample='L2') 
       for _ in range(N_SAMPLES)] 
L2_polar = [to_polar(cartesian=l2, origin=B) for l2 in L2_cartesian] 

all_polar = L1_polar + L2_polar 
all_polar = sorted(all_polar, key=lambda x: x.phi) 

print(all_polar) 

你得到的到底是什麼（原籍樣本被保存在all_polar.sample）中所有點的列表，通過它們B角度分別進行排序。你只需巧妙地遍歷該列表;只檢查「接近」的角度（以及來自不同樣本集的點）。

類似（或等角）然後仍然不意味着一個點在'中間';您仍然必須將距離與B（即all_polar.r）進行比較。

不需要將兩個樣本加入到一個列表中;您也可以遍歷一個列表併產生與另一個列表「關閉」的元素。

這一切都沒有經過全面測試！並且比較部分缺失。

---

爲您添加您的積分是在整數座標，我建議你做什麼David Eisenstat's answer建議（這是他的想法加入到我的代碼;信貸應該去他的回答）：不是計算的極座標，做一個字典包含這個結果

from fractions import Fraction 

def get_slope(cartesian, origin): 
    x_diff = cartesian.x - origin.x 
    y_diff = cartesian.y - origin.y 

    slope = Fraction(y_diff, x_diff) 
    x_sign = x_diff > 0 

    return (slope, x_sign) 

然後創建一個字典例如像這樣：

from collections import defaultdict 

dct = defaultdict(list) 
# add all the points in your sets (both) 
dct[get_slope(cartesian, origin)].append(cartesian) 

然後它是微不足道的比較點給定的斜率。

Answer 4

我所得到的是：我們必須超過迭代L1的所有點，我們要檢查，如果直線從L1集合到固定點B的每個點都被集合L2的任何點阻塞或者不被鎖定。如果它被阻塞，那麼該點必須從L1集中移除，否則不能。假設L1 = {（x1，y1），（x2，y2），...}和L2 = {（a1，b1），（a2，b2），...}和固定點B是（m，n）。因此，儘管檢查，如果（X1，Y1）點必須從L1集中刪除與否，我們可以檢查 -

if (x1 <= a1 and a1 <= m) and (y1 <= b1 and b1 <= n): 
    Cartesian Product/Euclidean Distance 
else: 
    {L1 - (x1, y1)} // remove from L1 

像笛卡爾乘積或兩個點之間的距離發現這些重操作的計算之前，這個條件對於所有可以檢查L2的點數。因爲一個點（a1，b1）可以在（x1，y1）和（m，n）之間進入，只有當這個條件成立時，這兩個點纔會進入。理論上這仍然是O（N^2）），但實際上覆雜度將比O（N^2）小）。