Wie berechnen Sie die kleinste umschließende Kugel umschließenden anderen bounding-Sphären

Ich bin auf der Suche nach einem Algorithmus, welcher Benutzer Zugriff hat, berechnet die kleinste umschließende Kugel umschließt eine Reihe von anderen bounding-Sphären. Ich habe darüber nachgedacht für eine Weile und haben einige Lösungsansätze, aber ich glaube nicht, dass diese notwendigerweise die Genaueste oder die am wenigsten rechenintensiv (die schnellsten).

Erster Gedanke

Meine erste Lösung ist die einfachste, naive eine, die durchschnittlich aus der Sphäre Zentren um den center-Punkt und berechnen Sie den Abstand zwischen dem berechneten Mittelpunkt zu jedem Bereich center plus den radius als der radius. So pseudo-code geht so:

function containing_sphere_1(spheres)
  center = sum(spheres.center) /count(spheres)
  radius = max(distance(center, spheres.center) + radius)
  return Sphere(center, radius)
end

Aber ich habe das Gefühl, dass es nicht, dass rechnerisch Billig, noch ist es ganz genau ist, da der resultierende Bereich könnte durchaus größer, als es sein muss.

Zweiten Gedanken

Mein zweiter Gedanke ist die Verwendung eines iterativen Algorithmus zur Berechnung der minimal bounding-sphere. Er wird berechnet, indem nacheinander testen eine andere Sphäre, wenn der geprüfte Bereich ist innerhalb der Grenzen, dann geschieht nichts, andernfalls wird ein neues bounding-sphere berechnet sich aus den beiden Bereichen zur Verfügung. Die neue bounding-sphere hat ein Zentrum, auf halbem Weg zwischen dem Vektor zwischen den beiden Zentren, wenn es erweitert wurde, um die Kugeln Flächen, und der radius ist die Hälfte der Länge der Zeile wird (von der neuen Mitte, um entweder sphere Oberfläche).

function containing_sphere_2(spheres)
  bounds = first(spheres)
  for each sphere in spheres
    if bounds does not contain sphere
      line = vector(bounds.center, sphere.center)
      extend(line, bounds.radius)
      extend(line, sphere.radius)
      center = midpoint(line)
      radius = length(line) /2
      bounds = Sphere(center, radius)
    end
  end
  return bounds
end

Anfangs dachte ich, dies wäre der Weg zu gehen, denn es ist ein iterativer und scheint ziemlich logisch konsistent, aber nach etwas Lesen, insbesondere der Artikel "Kleinsten einschließenden Scheiben (Kugeln und Ellipsoide)" von Emo Welzl ich bin nicht so sicher.

Welzl-Algorithmus

Wie ich es verstehe, die Grundlage dieses Algorithmus ist, dass die minimum bounding-sphere über eine Reihe von Punkten in 3 Dimensionen bestimmt werden kann, auf höchstens 4 Punkte (die auf der Oberfläche der umschließenden sphere). Also der Algorithmus verwendet einen iterativen Ansatz, indem Sie 4 Punkte, und dann der Prüfung anderer Punkte, um zu sehen, ob Sie innerhalb oder nicht, wenn Sie nicht eine neue bounding-Sphäre konstruiert wird mit dem neuen Punkt.

Nun der Algorithmus befasst sich ausschließlich mit Punkte, aber ich denke, es kann an den Umgang mit Sphären, die wichtigste Komplikation wird accounding für den radius bei der Konstruktion der umschließenden sphere.

Zurück zu der Frage

Also, was ist die 'beste', wie in den am wenigsten rechenintensiv, Algorithmus, erzeugt eine minimal bounding sphere für einen Satz von bestimmten Bereichen?

Ist eine davon, die ich beschrieben habe, hier die Antwort? Einige pseudo-code oder der Algorithmus wäre toll.

InformationsquelleAutor Daemin | 2012-01-30