Xây dựng một mạng lưới 2D từ danh sách tiềm năng đầy đủ của ứng viên

Question

Vấn đề

tôi cần phải xây dựng một mạng lưới 2D sử dụng một tập hợp các vị trí ứng cử viên (giá trị trong X và Y). Tuy nhiên, có thể có các ứng cử viên dương tính giả cần được lọc ra, cũng như các âm bản sai (vị trí cần được tạo cho vị trí dự kiến ​​cho các giá trị vị trí xung quanh). Các hàng và cột của lưới có thể được mong đợi là thẳng, và quay, nếu có nhỏ.

Hơn nữa, tôi không có thông tin đáng tin cậy về vị trí lưới (0, 0). Tuy nhiên, tôi biết:

grid_size = (4, 4) 

expected_distance = 105 

(Khoảng cách ngoại lệ chỉ là ước tính sơ bộ về khoảng cách giữa các điểm lưới và phải được phép thay đổi trong phạm vi 10%).

Ví dụ dữ liệu

Đây là dữ liệu lý tưởng, không có dương tính giả và âm tính giả không. Thuật toán cần có khả năng đối phó với việc loại bỏ một số điểm dữ liệu và thêm các điểm dữ liệu sai.

X = np.array([61.43283582, 61.56626506, 62.5026738, 65.4028777, 167.03030303, 167.93965517, 170.82191781, 171.37974684, 272.02884615, 272.91089109, 274.1031746, 274.22891566, 378.81553398, 379.39534884, 380.68181818, 382.67164179]) 

Y = np.array([55.14427861, 160.30120482, 368.80213904, 263.12230216, 55.1030303, 263.64655172, 162.67123288, 371.36708861, 55.59615385, 264.64356436, 368.20634921, 158.37349398, 54.33980583, 160.55813953, 371.72727273, 266.68656716]) 

Mã

Chức năng sau đây để đánh giá các ứng viên và trả về hai bộ từ điển.

Vị trí đầu tiên có mỗi vị trí ứng cử viên (dưới dạng bộ 2 chiều) vì khóa và giá trị là các bộ 2 chiều của các vị trí bên phải và bên dưới (sử dụng logic từ cách hiển thị hình ảnh). Những người hàng xóm đó là chính họ hoặc là một phối hợp tuple 2 chiều hoặc None.

Từ điển thứ hai là lần tra cứu ngược lại đầu tiên, sao cho mỗi ứng viên (vị trí) có danh sách các vị trí ứng viên khác hỗ trợ nó.

import numpy as np 
from collections import defaultdict 

def get_neighbour_grid(X, Y, expect_dist=(105, 105)): 

    t1 = (expect_dist[0] + expect_dist[1])/2.0 * 0.9 
    t2 = t1 * 1.222 

    def neighbours(x, y): 

     nRight = None 
     ideal = x + expect_dist[0] 
     D = np.sqrt((X - ideal)**2 + (Y - y)**2) 
     candidate = (X[D.argmin()], Y[D.argmin()]) 
     if candidate != (x, y) and x + t2 > candidate[0] > x + t1: 
      nRight = candidate 

     nBelow = None 
     ideal = y + expect_dist[0] 
     D = np.sqrt((X - x)**2 + (Y - ideal)**2) 
     candidate = (X[D.argmin()], Y[D.argmin()]) 
     if candidate != (x, y) and y + t2 > candidate[1] > y + t1: 
      nBelow = candidate 

     return nRight, nBelow 

    right_below_neighbours = dict() 
    def _default_val(*args): 
     return list() 
    reverse_lookup = defaultdict(_default_val) 

    for pos in np.arange(X.size): 

     pos_tuple = (X[pos], Y[pos]) 
     n = neighbours(*pos_tuple) 
     right_below_neighbours[pos_tuple] = n 
     reverse_lookup[n[0]].append(pos_tuple) 
     reverse_lookup[n[1]].append(pos_tuple) 

    return right_below_neighbours, reverse_lookup 

Đây là nơi tôi gặp khó khăn:

Làm thế nào để sử dụng những từ điển và/hoặc X và Y để xây dựng lưới điện được hỗ trợ nhiều nhất?

Tôi đã có ý tưởng bắt đầu với ứng cử viên dưới cùng bên phải, bên phải được hỗ trợ bởi 2 người hàng xóm và lặp lại tạo lưới bằng cách sử dụng từ điển reverse_lookup. Nhưng thiết kế đó có một số sai sót, rõ ràng nhất là tôi không thể tin vào việc phát hiện ra ứng cử viên thấp hơn, ngoài cùng bên phải và cả những người hàng xóm hỗ trợ của nó.

Mã cho rằng, mặc dù nó sẽ không chạy kể từ khi tôi bị bỏ rơi nó khi tôi nhận ra đó là cách có vấn đề (pre_grid = right_below_neighbours):

def build_grid(pre_grid, reverse_lookup, grid_shape=(4, 4)): 

    def _default_val(*args): 
     return 0 

    grid_pos_support = defaultdict(_default_val) 
    unsupported = 0 

    for l, b in pre_grid.values(): 

     if l is not None: 
      grid_pos_support[l] += 1 
     else: 
      unsupported += 1 
     if b is not None: 
      grid_pos_support[b] += 1 
     else: 
      unsupported += 1 

    well_supported = list() 
    for pos in grid_pos_support: 
     if grid_pos_support[pos] >= 2: 
      well_supported.append(pos) 

    well_A = np.asarray(well_supported) 
    ur_pos = well_A[well_A.sum(axis=1).argmax()] 

    grid = np.zeros(grid_shape + (2,), dtype=np.float) 
    grid[-1,-1,:] = ur_pos 

    def _iter_build_grid(pos, ref_pos=None): 

     isX = pre_grid[tuple(pos)][0] == ref_pos 
     if ref_pos is not None: 
      oldCoord = map(lambda x: x[0], np.where(grid == ref_pos)[:-1]) 
      myCoord = (oldCoord[0] - int(isX), oldCoord[1] - int(not isiX)) 

     for p in reverse_lookup[tuple(pos)]: 

      _iter_build_grid(p, pos) 

    _iter_build_grid(ur_pos) 

    return grid 

Phần thứ nhất có thể hữu ích mặc dù, vì nó nói lên sự ủng hộ cho mỗi vị trí. Nó cũng cho thấy những gì tôi sẽ cần như là một sản phẩm cuối cùng (grid):

Một mảng 3D với kích thước thứ nhất là lưới và thứ 3 với chiều dài 2 (cho toạ độ x và tọa độ y cho mỗi vị trí).

Tóm tắt

Vì vậy, tôi nhận ra như thế nào nỗ lực của tôi là vô dụng, nhưng tôi đang ở mất mát như thế nào làm cho một đánh giá toàn cầu của tất cả các ứng cử viên và đặt lưới hỗ trợ hầu hết sử dụng x và y giá trị của các ứng cử viên bất cứ nơi nào phù hợp. Vì đây là một câu hỏi khá phức tạp, tôi không thực sự mong đợi bất cứ ai đưa ra một giải pháp hoàn chỉnh (mặc dù nó sẽ là tuyệt vời), nhưng bất kỳ gợi ý nào về loại thuật toán hoặc các chức năng có thể được sử dụng sẽ được nhiều đánh giá cao.

Cuối cùng, xin lỗi vì đây là câu hỏi hơi dài.

Sửa

Vẽ những gì tôi muốn xảy ra:

Các ngôi sao/chấm là X và Y âm mưu với hai thay đổi, tôi loại bỏ các vị trí đầu tiên và thêm một giả để làm cho một ví dụ đầy đủ của thuật toán tìm kiếm.

Điều tôi muốn, nói cách khác, ánh xạ các giá trị toạ độ mới của các vị trí được khoanh tròn màu đỏ (các giá trị được viết bên cạnh) để tôi có thể lấy toạ độ cũ từ mới (ví dụ: (1, 1) -> (170.82191781, 162.67123288)). Tôi cũng muốn các điểm không gần đúng với lưới lý tưởng mà các điểm thật mô tả bị loại bỏ (như được hiển thị) và cuối cùng là vị trí lưới trống lý tưởng (vòng tròn màu xanh) được 'lấp đầy' bằng các tham số lưới lý tưởng (khoảng (0, 0) -> (55, 55)) .

Giải pháp

tôi đã sử dụng mã @skymandr cung cấp để có được các thông số lý tưởng và sau đó đã làm như sau (không mã đẹp, nhưng nó hoạt động). Điều đó có nghĩa tôi không sử dụng các get_neighbour_grid -function nữa .:

def build_grid(X, Y, x_offset, y_offset, dx, dy, grid_shape=(16,24), 
    square_distance_threshold=None): 

    if square_distance_threshold is None: 
     square_distance_threshold = ((dx + dy)/2.0 * 0.05) ** 2 

    grid = np.zeros(grid_shape + (2,), dtype=np.float) 

    D = np.zeros(grid_shape) 
    for i in range(grid_shape[0]): 
     for j in range(grid_shape[1]): 
      D[i,j] = i * (1 + 1.0/(grid_shape[0] + 1)) + j 

    rD = D.ravel().copy() 
    rD.sort() 

    def find_valid(x, y): 

     d = (X - x) ** 2 + (Y - y) ** 2 
     valid = d < square_distance_threshold 
     if valid.any(): 
      pos = d == d[valid].min() 
      if pos.sum() == 1: 
       return X[pos], Y[pos] 

     return x, y 

    x = x_offset 
    y = y_offset 
    first_loop = True 

    for v in rD: 
     #get new position 
     coord = np.where(D == v) 

     #generate a reference position already passed 
     if coord[0][0] > 0: 
      old_coord = (coord[0] - 1, coord[1]) 
     elif coord[1][0] > 0: 
      old_coord = (coord[0], coord[1] - 1) 

     if not first_loop: 
      #calculate ideal step 
      x, y = grid[old_coord].ravel() 
      x += (coord[0] - old_coord[0]) * dx 
      y += (coord[1] - old_coord[1]) * dy 

     #modify with observed point close to ideal if exists 
     x, y = find_valid(x, y) 

     #put in grid 
     #print coord, grid[coord].shape 
     grid[coord] = np.array((x, y)).reshape(grid[coord].shape) 

     first_loop = False 


    return grid 

Nó đặt ra một câu hỏi: làm thế nào để độc đáo lặp dọc theo đường chéo của một 2D-mảng, nhưng tôi cho rằng đó là xứng đáng với một câu hỏi của mình riêng: More numpy way of iterating through the 'orthogonal' diagonals of a 2D array

Sửa

Cập nhật mã giải pháp để đối phó tốt hơn với lưới kích thước lớn hơn để nó sử dụng một vị trí lưới láng giềng đã trôi qua như tài liệu tham khảo cho các lý tưởng phối hợp cho tất cả các vị trí. Vẫn phải tìm cách để thực hiện cách lặp lại tốt hơn thông qua lưới từ câu hỏi được liên kết.

Answer 1

Đây là một giải pháp khá đơn giản và rẻ tiền, mặc dù tôi không biết nó mạnh như thế nào.

Trước hết, đây là một cách để nhận được một ước tính tốt hơn cho khoảng cách:

leeway = 1.10 

XX = X.reshape((1, X.size)) 
dX = np.abs(XX - XX.T).reshape((1, X.size ** 2)) 
dxs = dX[np.where(np.logical_and(dX > expected_distance/leeway, 
           dX < expected_distance * leeway))] 
dx = dxs.mean() 

YY = Y.reshape((1, Y.size)) 
dY = np.abs(YY - YY.T).reshape((1, Y.size ** 2)) 
dys = dY[np.where(np.logical_and(dY > expected_distance/leeway, 
           dY < expected_distance * leeway))] 
dy = dys.mean() 

Mã này tính khác biệt nội bộ trong X và Y, và mất giá trị trung bình của những người nằm trong 10% khoảng cách mong muốn.

Đối với phần thứ hai, tìm bù đắp của lưới điện, một phương pháp tương tự có thể được sử dụng:

Ndx = np.array([np.arange(grid_size[0])]) * dx 
x_offsets = XX - Ndx.T 
x_offset = np.median(x_offsets) 

Ndy = np.array([np.arange(grid_size[1])]) * dy 
y_offsets = YY - Ndy.T 
y_offset = np.median(y_offsets) 

Về cơ bản, điều này không được để cho mỗi vị trí trong X "bỏ phiếu" cho NX = grid_size[0] vị trí nơi điểm dưới bên trái có thể, dựa trên X - n * dx nơi n = 0 là một cuộc bỏ phiếu cho các điểm bản thân, n = 1 là một cuộc bỏ phiếu cho một điểm một dx đến vv Bằng cách này trái, các điểm gần nguồn gốc thực sự sẽ nhận được nhiều phiếu bầu nhất, và bù đắp có thể được tìm thấy bằng cách sử dụng trung bình.

Tôi nghĩ rằng phương pháp này là đủ đối xứng xung quanh nguồn gốc mong muốn, rằng trung bình có thể được sử dụng trong hầu hết (nếu không phải tất cả) trường hợp. Tuy nhiên, nếu có nhiều xác thực sai, khiến cho trung vị không hoạt động vì một lý do nào đó, có thể tìm thấy nguồn gốc "thực sự" bằng cách sử dụng ví dụ: một phương pháp biểu đồ.