Der beste Weg, um alle Punkte des Gitters in der Kugel zu finden

Question

Angesichts einer Reihe von willkürlichen Vektoren (in einer Matrix A gespeichert) und einem Radius r, würde ich gerne alle ganzzahlige lineare Kombinationen der Vektoren finden, die in a landen Kugel mit Radius r. Die notwendigen Koordinaten Ich würde dann speichern Sie in einer Matrix V. So zum Beispiel, wenn die lineare Kombination

K=[0; 1; 0] 

landet in meinem Bereich, also so etwas wie

if norm(A*K) <= r then 
    V(:,1)=K 
end 

usw.

Die Vektoren in A sind sicher die einfachste mögliche Basis für das gegebene Gitter und der größte Vektor wird die Länge 1 haben. Nicht sicher, ob das die Vektoren in irgendeiner nützlichen Weise einschränkt, aber ich vermute, dass dies der Fall sein könnte. - Sie werden nicht so ähnliche Richtungen haben, wie eine weniger ideale Basis hätte.

Ich habe schon ein paar Ansätze versucht, aber keiner von ihnen scheint besonders befriedigend. Ich finde kein schönes Muster, um das Gitter zu durchqueren.

Mein aktueller Ansatz besteht darin, in der Mitte zu beginnen (d. H. Mit der Linearkombination aller 0) und die notwendigen Koordinaten nacheinander durchzugehen. Es beinhaltet das Speichern einer Menge zusätzlicher Vektoren, um zu verfolgen, so dass ich alle Oktanten (im Fall 3D) der Koordinaten durchgehen und sie einzeln finden kann. Diese Implementierung scheint furchtbar komplex und nicht sehr flexibel zu sein (insbesondere scheint sie nicht leicht auf beliebig viele Dimensionen zu verallgemeinern - obwohl das für den aktuellen Zweck nicht unbedingt notwendig ist, wäre es ein nice-to-have)

Gibt es eine nette * Möglichkeit, alle erforderlichen Punkte zu finden?

(* Idealerweise sowohl effizient als auch elegant **. Wenn es wirklich nötig wäre, wäre es nicht wichtig, ein paar Extrapunkte außerhalb der Sphäre zu haben, aber vorzugsweise nicht viel mehr. Ich brauche definitiv alle Vektoren innerhalb der Kugel - wenn es einen großen Unterschied macht, ich bin am meisten interessiert in dem 3D-Fall

** ich bin mir ziemlich sicher, dass meine aktuelle Implementierung ist weder)

---

ähnliche Fragen, die ich gefunden...:

Find all points in sphere of radius r around arbitrary coordinate - das ist eigentlich ein viel allgemeinerer Fall als das, wonach ich suche. Ich habe es nur mit periodischen Gittern zu tun, und meine Sphäre ist immer bei 0 zentriert und fällt mit einem Punkt auf dem Gitter zusammen. Aber ich habe keine Liste von Punkten, sondern eine Matrix von Vektoren, mit denen ich alle Punkte generieren kann.

How to efficiently enumerate all points of sphere in n-dimensional grid - der Fall für ein völlig normales hyperkubisches Gitter und die Manhattan-Distanz. Ich suche nach völlig willkürlichen Gittern und euklidischen Entfernungen (oder, aus Gründen der Effizienz, natürlich das Quadrat davon).

Answer 1

Lassen Sie uns repräsentieren K wie X.

Das Problem kann wie folgt dargestellt werden:

(a11x1 + a12x2 ..)^2 + (a21x1 + a22x2 ..)^2 ... < r^2

(x1, x2, ...) wird keine Kugel bilden.

Answer 2

Ich fand eine Methode, die mich jetzt viel glücklicher macht.Es kann immer noch zu möglichen Verbesserungen kommen. Wenn Sie also eine bessere Methode haben oder einen Fehler in diesem Code finden, teilen Sie uns das bitte mit. Obwohl hier ist, was ich habe jetzt: (alle in SciLab geschrieben)

---

Schritt 1: Finde heraus, die maximalen Bereiche aus. Vielen Dank für vageen Vorschlag des ElKamina sowie diese Antwort auf ein meine Fragen über auf math.se von Chappers: https://math.stackexchange.com/a/1230160/49989

function I=findMaxComponents(A,r) //returns matrix I, takes matrix A, scalar r 
    [dims,vecs]=size(A); //figure out how many vectors there are in A (and, unnecessarily, how long they are) 
    U=eye(vecs,vecs); //builds matching unit matrix 
    iATA=pinv(A'*A); //finds the (pseudo-)inverse of A^T A 
    iAT=pinv(A'); //finds the (pseudo-)inverse of A^T 
    I=[]; //initializes I as an empty vector 
    for i=1:vecs 
     t=r*(iATA*U(:,i))/norm(iAT*U(:,i)) //put it all together as per above link 
     I=[I,t(i)]; //take only the maximized component and store it in I. 
    end 
    I=[-I;I]; //I want to go from minimum to maximum value. 
endfunction 

In meiner Frage, die ich nur für eine allgemeine Grundlage gefragt, dh für n Dimensionen, eine Reihe von n beliebigen aber linear unabhängigen Vektoren. Der obige Code arbeitet aufgrund der Verwendung der Pseudoinverse für Matrizen beliebiger Formen, und in ähnlicher Weise liefert Scilabs "A" die konjugierte Transponierte anstatt nur die Transponierte von A, so dass sie gleichermaßen für komplexe Matrizen funktionieren sollte.

Im letzten Schritt habe ich die entsprechenden Minimalkomponenten gesetzt.

Für einen solchen als Beispiel ergibt dies mir folgendes in Scilab Konsole:

A = 

    0.9701425 - 0.2425356 0. 
    0.2425356 0.4850713 0.7276069 
    0.2425356 0.7276069 - 0.2425356 

r=3; 

I=findMaxComponents(A,r) 

I = 

    - 2.9494438 - 3.4186986 - 4.0826424 
    2.9494438 3.4186986 4.0826424 

I=int(I) 

I = 

    - 2. - 3. - 4. 
    2. 3. 4. 

Für jede Komponente, die obigen Werte die maximalen diejenigen sind, die auf die Kugel landen noch so kann ich sicher fallen der Teil nach dem Dezimalpunkt, um die maximalen Ganzzahlbereiche zu erhalten. Also für die gegebene Matrix A muss ich in der ersten Komponente von -2 auf 2 wechseln, in der zweiten von -3 auf 3 und in der dritten von -4 auf 4, und ich bin mir sicher, dass ich auf allen landen werde Punkte innerhalb der Kugel. Weiter oben:

---

Schritt 2: Verwenden Sie die obigen Informationen, finden Sie alle Kombinationen.

function K=findAllCombinations(I) //takes a matrix of the form produced by findMaxComponents() and returns a matrix which lists all the integer linear combinations in the respective ranges. 
    v=I(1,:); //starting from the minimal vector 
    K=[]; 
    next=1; //keeps track of what component to advance next 
    changed=%F; //keeps track of whether to add the vector to the output 

    while or(v~=I(2,:)) //as long as not all components of v match all components of the maximum vector 
     if v <= I(2,:) then //if each current component is smaller than each largest possible component 
      if ~changed then 
       K=[K;v]; //store the vector and 
      end 
      v(next)=v(next)+1; //advance the component by 1 
      next=1; //also reset next to 1 
      changed=%F; 
     else 
      v(1:next)=I(1,1:next); //reset all components smaller than or equal to the current one and 
      next=next+1; //advance the next larger component next time 
      changed=%T; 
     end 
    end 
    K=[K;I(2,:)]'; //while loop ends a single iteration early so add the maximal vector too 
        //also transpose K to fit better with the other functions 
endfunction 

So, jetzt, dass ich, dass alles, was, ob eine bestimmte Kombination innerhalb oder außerhalb der Sphäre tatsächlich zu prüfen bleibt, ist liegt. Alles, was ich tun dafür muss ist:

---

Schritt 3: Erzeugen Sie die tatsächlichen Punkte

function points=generatePoints(A,K,r) 
    possiblePoints=A*K; //explicitly generates all the possible points 
    points=[]; 
    for i=possiblePoints 
     if i'*i<=r*r then //filter those that are too far from the origin 
      points=[points i]; 
     end 
    end 
endfunction 

Und ich alle Kombinationen erhalten, die im Inneren der Kugel mit dem Radius r passen.

Für das obige Beispiel ist die Ausgabe ziemlich lang: Von ursprünglich 315 möglichen Punkten für eine Kugel mit Radius 3 bekomme ich 163 verbleibende Punkte.

Die erste 4 sind: (jede Spalte eines)

- 0.2425356 0.2425356 1.2126781 - 0.9701425 
    - 2.4253563 - 2.6678919 - 2.4253563 - 2.4253563 
    1.6977494 0.   0.2425356 0.4850713 

so dass der Rest der Werkoptimierung ist. Vermutlich könnten einige dieser Schleifen schneller gemacht werden und insbesondere, wenn die Anzahl der Dimensionen steigt, muss ich eine Menge Punkte erzeugen, die ich verwerfen muss, also gibt es vielleicht einen besseren Weg als die (in der gegebenen Koordinate verzerrt) Rahmen) begrenzende Hyperbox der n-Kugel als Ausgangspunkt.

Answer 3

Ohne zu beweisen, Behauptungen, ich denke, dass 1) wenn die Menge der Vektoren nicht von maximalem Rang ist dann ist die Anzahl der Lösungen unendlich; 2) wenn der Satz von maximalem Rang ist, dann ist das Bild der linearen Transformation, die durch die Vektoren erzeugt wird, ein Unterraum (z., Ebene) des Zielraums, der die Kugel in einer niederdimensionalen Kugel schneidet; 3) Daraus folgt, dass Sie das Problem auf eine 1-1 lineare Transformation (kxk-Matrix auf einem k-dimensionalen Raum) reduzieren können; 4) Da die Matrix invertierbar ist, können Sie die Kugel zu einem Ellipsoid in dem Raum zurückziehen, der die Gitterpunkte enthält, und als Bonus erhalten Sie eine schöne geometrische Beschreibung des Ellipsoids (Hauptachsensatz); 5) Ihr Problem besteht jetzt genau darin, die Gitterpunkte innerhalb des Ellipsoids zu bestimmen.

Das letztere Problem bezieht sich auf ein altes Problem (Zählen der Gitterpunkte innerhalb einer Ellipse), das von Gauß, der eine gute Näherung hergeleitet hat, in Betracht gezogen wurde. Das Bestimmen der Gitterpunkte innerhalb einer Ellipse (oid) ist wahrscheinlich kein so ordentliches Problem, aber es kann wahrscheinlich um eine Dimension zu einer Zeit reduziert werden (der Querschnitt eines Ellipsoids und einer Ebene ist ein anderes Ellipsoid).