उम्मीदवारों

Question

समस्या

मैं (X और Y में मान) उम्मीदवार पदों का एक सेट का उपयोग कर एक 2 डी ग्रिड का निर्माण करने की आवश्यकता है के संभावित अधूरा सूची में से एक 2 डी ग्रिड का निर्माण। हालांकि, ऐसे झूठे सकारात्मक उम्मीदवार हो सकते हैं जिन्हें फ़िल्टर किया जाना चाहिए, साथ ही झूठी नकारात्मक (जहां आसपास की स्थिति के मूल्यों को अपेक्षित स्थिति के लिए स्थिति बनाने की आवश्यकता है)। ग्रिड की पंक्तियों और स्तंभों को सीधे होने की उम्मीद की जा सकती है, और घूर्णन, यदि कोई छोटा हो।

आगे, मेरे पास विश्वसनीय जानकारी नहीं है कि (0, 0) ग्रिड स्थिति कहां है। हालांकि मैं नहीं पता है:

grid_size = (4, 4) 

expected_distance = 105 

(एक्सेप्टेड दूरी सिर्फ ग्रिड अंक के बीच अंतर का एक मोटा अनुमान है, और 10% की सीमा में भिन्न करने की अनुमति दी जानी चाहिए)।

उदाहरण डाटा

यह कोई गलत परिणामों की और कोई मिथ्या नकारात्मक के साथ आदर्श में डेटा है। एल्गोरिदम को कई डेटा-पॉइंट हटाने और झूठी जोड़ने के साथ सामना करने में सक्षम होना चाहिए।

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]) 

कोड

निम्नलिखित समारोह उम्मीदवारों का मूल्यांकन करता है और दो शब्दकोशों देता है।

पहले व्यक्ति में प्रत्येक उम्मीदवार की स्थिति (2-लंबाई की ट्यूपल के रूप में) होती है क्योंकि चाबियाँ और मान सही और नीचे पड़ोसी के पदों के 2-लंबाई ट्यूपल्स होते हैं (छवियों को प्रदर्शित करने के तरीके से तर्क का उपयोग करके)। वे पड़ोसी स्वयं या तो 2-लंबाई ट्यूपल समन्वय या None हैं।

दूसरा शब्दकोश पहला का रिवर्स लुकअप है, जैसे कि प्रत्येक उम्मीदवार (स्थिति) में अन्य उम्मीदवारों की स्थिति का समर्थन होता है।

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 

वह स्थान है जहां मैं अटक जाते हैं:

मैं इन शब्दकोशों और/या X और Y का उपयोग कैसे करूँ सबसे समर्थित ग्रिड के निर्माण के लिए?

मुझे 2 पड़ोसियों द्वारा समर्थित निचले, सही उम्मीदवार के साथ शुरू करने का विचार था और reverse_lookup शब्दकोश का उपयोग करके ग्रिड बनाएं। लेकिन उस डिजाइन में कई त्रुटियां हैं, सबसे स्पष्ट यह है कि मैं निचले, सही उम्मीदवार और उसके सहायक पड़ोसियों दोनों का पता लगाने पर भरोसा नहीं कर सकता।

उस के लिए कोड है, हालांकि यह अभ्यस्त चलाने के बाद से मैं इसे छोड़ दिया जब मुझे एहसास हुआ कि यह कैसे समस्याग्रस्त था (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 

पहले भाग हालांकि उपयोगी हो सकता है, क्योंकि यह करने के लिए समर्थन का सार प्रत्येक स्थिति। यह भी दिखाता है कि मुझे अंतिम आउटपुट (grid) के रूप में क्या चाहिए,

2 पहले आयामों के साथ एक 3 डी सरणी ग्रिड के आकार और 3 लंबाई के साथ 3 (प्रत्येक स्थिति के लिए एक्स-समन्वय और वाई-समन्वय के लिए)।

संक्षिप्त

तो मुझे लगता है कि मेरे प्रयास बेकार था, लेकिन मैं कैसे सभी उम्मीदवारों की एक वैश्विक मूल्यांकन करते हैं और उम्मीदवारों की x और y मानों का उपयोग सबसे समर्थित ग्रिड जगह के रूप में नुकसान में हूँ जहां भी फिट हो। जैसा कि, मैं उम्मीद करता हूं, एक जटिल सवाल है, मैं वास्तव में किसी को भी एक पूर्ण समाधान देने की उम्मीद नहीं करता (हालांकि यह बहुत अच्छा होगा), लेकिन इस बात का कोई संकेत नहीं कि किस प्रकार के एल्गोरिदम या numpy/scipy कार्यों का उपयोग किया जा सकता है बहुत सराहना कीजिए।

अंत में, यह कुछ हद तक लंबा सवाल होने के लिए खेद है।

संपादित

मैं क्या चाहते हो की ड्राइंग:

सितारों/बिंदु हैं X और Y दो संशोधनों के साथ साजिश रची, मैं पहले स्थान पर हटा दिया और एक जोड़ा यह मांगने वाले एल्गोरिदम का एक पूर्ण उदाहरण बनाने के लिए झूठा है।

जो मैं चाहता हूं, दूसरे शब्दों में, लाल-चक्र वाली स्थितियों के नए समन्वय मूल्यों (उनके बगल में लिखे गए) को मानचित्र करें ताकि मैं नए से पुराने समन्वय प्राप्त कर सकूं (उदा। (1, 1) -> (170.82191781, 162.67123288))। मैं उन बिंदुओं को भी अनुमानित करता हूं जो आदर्श ग्रिड का अनुमान नहीं लगाते हैं कि वास्तविक बिंदुओं को त्यागने के रूप में वर्णित किया गया है (और दिखाया गया है), और आखिरकार आदर्श ग्रिड पैरामीटर (लगभग (0, 0) -> (55, 55)) का उपयोग करके खाली आदर्श ग्रिड पोजीशन (ब्लू सर्कल) 'भरे' होने के लिए ।

समाधान

मैं कोड @skymandr आदर्श मानकों पाने के लिए आपूर्ति की और उसके बाद निम्न किया इस्तेमाल किया (नहीं सबसे सुंदर कोड है, लेकिन यह काम करता है)। इसका मतलब है कि मैं अब और get_neighbour_grid समारोह का उपयोग नहीं .:

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 

यह एक और सवाल बन गया है: कैसे अच्छी तरह से एक 2 डी सरणी के विकर्ण साथ पुनरावृत्ति करने के लिए है, लेकिन मुझे लगता है कि का सवाल के योग्य है अपनी खुद: More numpy way of iterating through the 'orthogonal' diagonals of a 2D array

संपादित

इतना है कि यह पहले से ही आदर्श के लिए संदर्भ के रूप में पारित कर दिया सभी पदों के लिए समन्वय एक पड़ोसी ग्रिड स्थिति का उपयोग करता है बड़ा ग्रिड आकार बेहतर तरीके से निपटने का हल कोड अपडेट किया गया। अभी भी लिंक किए गए प्रश्न से ग्रिड के माध्यम से पुनरावृत्ति के बेहतर तरीके को लागू करने का एक तरीका ढूंढना है।

Answer 1

यहां एक काफी सरल और सस्ता समाधान है, हालांकि मुझे नहीं पता कि यह कितना मजबूत है।

सबसे पहले, यहाँ रिक्ति के लिए एक बेहतर अनुमान होने का तरीका बताया गया है:

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() 

कोड एक्स और वाई में आंतरिक मतभेद की गणना करता है, और जो लोग का 10% के भीतर हैं की औसत लेता है वांछित दूरी।

दूसरे भाग के लिए, ग्रिड की भरपाई खोजने, एक ऐसी ही विधि का इस्तेमाल किया जा सकता है:

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) 

अनिवार्य रूप से, क्या करता है NX = grid_size[0] पदों के लिए X "वोट" में प्रत्येक स्थिति बताने के लिए जहां नीचे बाएं बिंदु X - n * dx पर आधारित हो सकता है, जहां n = 0 बिंदु के लिए एक वोट है, n = 1 बाईं ओर एक dx बिंदु के लिए एक वोट है। इस तरह, वास्तविक उत्पत्ति के पास के बिंदु सबसे अधिक वोट प्राप्त करेंगे, और ऑफसेट का उपयोग माध्यम से किया जा सकता है।

मुझे लगता है कि यह विधि वांछित उत्पत्ति के आसपास पर्याप्त सममित है, कि औसत का उपयोग अधिकांश (यदि सभी नहीं) मामलों में किया जा सकता है। यदि, हालांकि, कई झूठे सकारात्मक हैं, जो मध्यस्थ को किसी कारण से काम नहीं करते हैं, तो "सत्य" उत्पत्ति का उपयोग करके पाया जा सकता है। एक हिस्टोग्राम-विधि।