Wie überprüft man, ob ausgewählte Zellen auf einem Gitter einen "Tunnel" bilden?

Gegeben eine Rasterkarte, wo jede Zelle durch ein Paar (x, y) beschrieben werden kann, und einen Vektor solcher Zellen, wie kann ich (schön) überprüfen, ob die Zellen in diesem Vektor einen "Tunnel" bilden, dh. sie sind alle aufgereiht entweder vertikal oder horizontal? Aber was, wenn ich nur sehen möchte, wenn die meisten von ihnen aufgereiht sind (und nicht alle)?Wie überprüft man, ob ausgewählte Zellen auf einem Gitter einen "Tunnel" bilden?

All are lines up    Most are lined up  Not lined up 

          C      C C C 
C C C C C C C C    C C C C C C C C   C C C C 
           C     C C C C 
                 C C

Quelle

2012-04-13 Paul Manta

definieren "am meisten". Kannst du auch eine Beispieleingabe von nicht-aufgereiht geben? Obwohl es offensichtlich erscheint, könnte ein visuelles Beispiel den Antwortern helfen, das vorliegende Problem besser zu verstehen. – amit

Sie könnten die standard deviation der X- und Y-Koordinaten berechnen. Je mehr ‚getunnelt‘ Ihre Zellen sind, desto geringer ist die Standardabweichung für entweder X oder Y sein

Zum Beispiel in Python:

import numpy 

def is_tunnelled(cells): 
    # given cells=[(x,y), (x,y),...] 
    x_values, y_values = zip(*cells) 
    lowest_std_dev = min(numpy.std(x_values), numpy.std(y_values)) 
    return lowest_std_dev < STD_DEVIATION_THRESHOLD

Es liegt an Ihnen, zu bestimmen, was der Wert von STD_DEVIATION_THRESHOLD sollte sein.

Quelle

2012-04-13 19:05:36

Dies könnte die beste Lösung sein. Ich werde es mir ansehen. –

können Sie überprüfen, ob sie, indem man zuerst einen horizontalen Tunnel machen überprüfen, ob ihre y Koordinaten sind alle gleich, dann sortieren durch die x koordinieren und von links nach rechts durchquert auf Lücken zu überprüfen. Verwenden Sie die entgegengesetzten Koordinaten, um nach vertikalen Tunneln zu suchen.

Für die ungefähre Überprüfung müssen Sie klären, was Sie mit "am meisten" meinen.

Quelle

2012-04-13 18:58:47 hammar

Ich denke, ich könnte den Prozentsatz der Zellen bestimmen, die aufgereiht sind, dann muss der Benutzer entscheiden, was eine akzeptable Toleranz wäre (wie viele dürfen vom "Haupttunnel" abweichen und immer noch sagen, dass die meisten aufgereiht sind) . –

Sie könnten ein Histogramm der X- und Y-Koordinaten der Zellen erstellen. Wenn alle Zellen horizontal ausgerichtet sind, erhalten Sie nur einen y-Wert in Ihrem Histogramm und viele aufeinander folgende x-Werte, die alle nur einmal vorkommen. Vertikal ist das Gleiche mit x und y umgedreht.

Wenn Sie überprüfen möchten, ob die meisten in einer Reihe liegen, suchen Sie nach dem Wert im Histogramm, der die meisten Vorkommen hat (längster möglicher Tunnel) und überprüfen Sie die Zellen mit dieser X- oder Y-Koordinate sind aneinander gereiht (das heißt: ihre y- oder x-Koordinaten (abhängig davon, ob x oder y im vorherigen Schritt verwendet wurde) sind ohne Lücke hintereinander (vielleicht sortieren sie zuerst)) Wenn nicht, suchen Sie nach der zweithöchsten Vorkommenswert, ...

Quelle

2012-04-13 19:01:25 ingofreyer

"Wenn Sie überprüfen möchten, ob die meisten in einer Linie stehen, suchen Sie nach dem Wert im Histogramm, der am häufigsten vorkommt ..." Ah, natürlich. Vielen Dank! –

Wie überprüft man, ob ausgewählte Zellen auf einem Gitter einen "Tunnel" bilden?

Antwort

Verwandte Themen