Учитывая только трехмерные точки, не будет ли этот наивный подход к «маленькому закрывающемуся шару» достаточно хорошим?

Question

Позволяет использовать C# в нашем примере.

public class Sphere 
{ 
    public Point Center { get; set; } 
    public float Radius { get; set; } 

    public Sphere(IEnumerable<Point> points) 
    { 
     Point first = points.First(); 
     Point vecMaxZ = first; 
     Point vecMinZ = first; 
     Point vecMaxY = first; 
     Point vecMinY = first; 
     Point vecMinX = first; 
     Point vecMaxX = first; 

     foreach (Point current in points) 
     { 
      if (current.X < vecMinX.X) 
      { 
       vecMinX = current; 
      } 
      if (current.X > vecMaxX.X) 
      { 
       vecMaxX = current; 
      } 
      if (current.Y < vecMinY.Y) 
      { 
       vecMinY = current; 
      } 
      if (current.Y > vecMaxY.Y) 
      { 
       vecMaxY = current; 
      } 
      if (current.Z < vecMinZ.Z) 
      { 
       vecMinZ = current; 
      } 
      if (current.Z > vecMaxZ.Z) 
      { 
       vecMaxZ = current; 
      } 
     } 

     //the lines bellow assure at least 2 points sit on the surface of the sphere. 
     //I'm pretty sure the algorithm is solid so far, unless I messed up the if/elses. 
     //I've been over this, looking at the variables and the if/elses and they all 
     //seem correct, but our own errors are the hardest to spot, 
     //so maybe there's something wrong here. 
     float diameterCandidateX = vecMinX.Distance(vecMaxX); 
     float diameterCandidateY = vecMinY.Distance(vecMaxY); 
     float diameterCandidateZ = vecMinZ.Distance(vecMaxZ); 
     Point c; 
     float r; 
     if (diameterCandidateX > diameterCandidateY) 
     { 
      if (diameterCandidateX > diameterCandidateZ) 
      { 
       c = vecMinX.Midpoint(vecMaxX); 
       r = diameterCandidateX/2f; 
      } 
      else 
      { 
       c = vecMinZ.Midpoint(vecMaxZ); 
       r = diameterCandidateZ/2f; 
      } 
     } 
     else if (diameterCandidateY > diameterCandidateZ) 
     { 
      c = vecMinY.Midpoint(vecMaxY); 
      r = diameterCandidateY/2f; 
     } 
     else 
     { 
      c = vecMinZ.Midpoint(vecMaxZ); 
      r = diameterCandidateZ/2f; 
     } 

     //the lines bellow look for points outside the sphere, and if one is found, then: 
     //1 let dist be the distance from the stray point to the current center 
     //2 let diff be the equal to dist - radius 
     //3 radius will then the increased by half of diff. 
     //4 a vector with the same direction as the stray point but with magnitude equal to diff is found 
     //5 the current center is moved by half the vector found in the step above. 
     // 
     //the stray point will now be included 
     //and, I would expect, the relationship between the center and other points will be mantained: 
     //if distance from p to center = r/k, 
     //then new distance from p to center' = r'/k, 
     //where k doesn't change from one equation to the other. 
     //this is where I'm wrong. I cannot figure out how to mantain this relationship. 
     //clearly, I'm moving the center by the wrong amount, and increasing the radius wrongly too. 
     //I've been over this problem for so much time, I cannot think outside the box. 
     //my whole world is the box. The box and I are one. 
     //maybe someone from outside my world (the box) could tell me where my math is wrong, please. 
     foreach (Point current in points) 
     { 
      float dist = current.Distance(c); 
      if (dist > r) 
      { 
       float diff = dist - r; 
       r += diff/2f; 
       float scaleFactor = diff/current.Length(); 
       Point adjust = current * scaleFactor; 
       c += adjust/2f; 
      } 
     } 
     Center = c; 
     Radius = r; 
    } 

    public bool Contains(Point point) => Center.Distance(point) <= Radius; 

    public override string ToString() => $"Center: {Center}; Radius: {Radius}"; 
} 

public class Point 
{ 
    public float X { get; set; } 
    public float Y { get; set; } 
    public float Z { get; set; } 

    public Point(float x, float y, float z) 
    { 
     X = x; 
     Y = y; 
     Z = z; 
    } 

    public float LengthSquared() => X * X + Y * Y + Z * Z; 

    public float Length() => (float) Math.Sqrt(X * X + Y * Y + Z * Z); 

    public float Distance(Point another) 
    { 
     return (float) Math.Sqrt(
      (X - another.X) * (X - another.X) 
      + (Y - another.Y) * (Y - another.Y) 
      + (Z - another.Z) * (Z - another.Z)); 
    } 

    public float DistanceSquared(Point another) 
    { 
     return (X - another.X) * (X - another.X) 
      + (Y - another.Y) * (Y - another.Y) 
      + (Z - another.Z) * (Z - another.Z); 
    } 

    public Point Perpendicular() 
    { 
     return new Point(-Y, X, Z); 
    } 

    public Point Midpoint(Point another) 
    { 
     return new Point(
      (X + another.X)/2f, 
      (Y + another.Y)/2f, 
      (Z + another.Z)/2f); 
    } 

    public override string ToString() => $"({X}, {Y}, {Z})"; 
    public static Point operator +(Point p1, Point p2) 
    { 
     return new Point(p1.X + p2.X, p1.Y + p2.Y, p1.Z + p2.Z); 
    } 

    public static Point operator *(Point p1, float v) 
    { 
     return new Point(p1.X * v, p1.Y * v, p1.Z * v); 
    } 

    public static Point operator /(Point p1, float v) 
    { 
     return new Point(p1.X/v, p1.Y/v, p1.Z/v); 
    } 
} 

//Note: this class is here so I can be able to solve the problems suggested by 
//Eric Lippert. 
public class Line 
{ 
    private float coefficient; 
    private float constant; 

    public Line(Point p1, Point p2) 
    { 
     float deltaY = p2.Y - p1.Y; 
     float deltaX = p2.X - p1.X; 
     coefficient = deltaY/deltaX; 
     constant = coefficient * -p1.X + p1.Y; 
    } 

    public Point FromX(float x) 
    { 
     return new Point(x, x * coefficient + constant, 0); 
    } 

    public Point FromY(float y) 
    { 
     return new Point((y - constant)/coefficient, y, 0); 
    } 

    public Point Intersection(Line another) 
    { 
     float x = (another.constant - constant)/(coefficient - another.coefficient); 
     float y = FromX(x).Y; 

     return new Point(x, y, 0); 
    } 
} 

Могу ли я смело предположить, что это будет работать, по крайней мере так же быстро, как и фантазии алгоритмов, которые там обычно считают, ради робастности, возможности точек, имеющих любое число измерений, от 2 к чему-либо, как 1000 или 10000.

Мне это нужно только для 3-х измерений, никогда больше и не меньше. Поскольку у меня нет ученой степени по информатике (или в какой бы то ни было степени, я - второкурсник средней школы), мне сложно анализировать алгоритмы производительности и потребления ресурсов. Поэтому мой вопрос в основном заключается в следующем: «Является ли моя« самая маленькая замкнутая сфера для немых »альгоритмой хорошей в производительности и потреблении ресурсов по сравнению с причудливыми? Есть ли момент, когда мой алгоритм ломается, а профессиональные - нет, что означает, что он работает так плохо, что приведет к заметной потере (например, если у меня слишком много очков).

EDIT 1: Я редактировал код, потому что это не имело никакого смысла (я был голоден, было 4 вечера, и я не ел весь день). Думаю, это имеет смысл, но не уверен, что это правда. Первоначальный вопрос: если этот вопрос решает проблему, делает ли он это достаточно хорошо, чтобы конкурировать с профессиональными алгоритмами stardard в случае, если мы заранее знаем, что все точки имеют 3 измерения?

EDIT 2: Теперь я уверен, что производительность плохая, и я потерял всякую надежду реализовать наивный алгоритм, чтобы найти наименьшую охватывающую сферу. Я просто хочу что-то сделать. Проверьте последнее обновление.

EDIT 3: Не работает. С меня хватит.

EDIT 4: Наконец, после, я не знаю ... около 5 часов. Я понял. Иисус Христос. Это работает. Может ли кто-нибудь рассказать мне об эффективности? Это действительно плохо по сравнению с профессиональными алгоритмами? Какие строки я могу изменить, чтобы сделать их лучше? Есть ли момент, когда он ломается? Помните, я всегда буду использовать его для 3D-очков.

EDIT 5: Я узнал от Биченко, что предыдущий алгоритм все еще не работал. Я спал по этой проблеме, и это моя новая версия алгоритма. Я знаю, что это не работает, и у меня есть хорошая подсказка, где это неправильно, может ли кто-нибудь рассказать, почему эти конкретные вычисления ошибочны и как их исправить? Я склонен думать, что это имеет отношение к тригонометрии. Мои предположения не верны для евклидова пространства, потому что я не могу перестать видеть векторы как реальные числа вместо множеств реальных чисел, которые в моем случае я использую, чтобы указать точку в евклидовом пространстве. Я уверен, что я пропускаю синус или косинус где-то в последнем цикле (конечно, не совсем синус или косинус, но эквивалент в декартовых координатах, так как мы не знаем никаких углов.

Addendum РЕДАКТИРОВАТЬ 5: о проблемах, предложенных Эрик Липпертом: (1) Argh слишком тривиально: р (2) Я сделаю это для круга первого, я добавлю класс линию для этого

Point a, b, c; //they are not collinear 
Point midOfAB = a.Midpoint(b); 
Point midOfBC = b.Midpoint(c); 

//multiplying the vector by a scalar as I do bellow doesn't matter right? 
Point perpendicularToAB = midOfAB.Perpendicular() * 3; 
Point perpendicularToBC = midOfBC.Perpendicular() * 3; 

Line bisectorAB = new Line(perpendicularToAB, midOfAB); 
Line bisectorBC = new Line(perpendicularToBC, midOfBC); 

Point center = bisectorAB.Intersection(bisectorBC); 
float distA = center.Distance(a); 
float distB = center.Distance(b); 
float distC = center.Distance(c); 

if(distA == distB && distB == distC) 
    //it works (spoiler alert: it doesn't) 
else 
    //you're a failure, programmer, pick up your skate and practice some ollies 

Answer 1

.

Извините, но ваш алгоритм не так.. Это не решит проблему.

пример счетчика (3 балла):

A = (0, 0, 0) - closest to origin (0) 
B = (3, 3, 0) - farthest from origin (3 * sqrt(2) == 4.2426...) 
C = (4, 0, 0) 

ваш наивный алгоритм заявляет, что сфера имеет центр в

P = (3/sqrt(2), 3/sqrt(2), 0) 

и радиус

R = 3/sqrt(2) 

, и вы можете видеть, что точка C = (4, 0, 0) является за пределами сферой e

Редактировать Обновленный (но наивный) алгоритм по-прежнему ошибочен.

контрпример (3 балла):

A = (0, 0, 0) 
B = (1, 2, 0) 
C = (4, 1, 0) 

по алгоритму сфера имеет свой центр в

P = (2, 1, 0) 

с радиусом

R = sqrt(5) 

, и вы можете видеть, что области не является минимальный (мельчайший) один.

Nth Редактировать у вас все еще есть алгоритм. При исследовании серой зоны (вы знаете проблему, но частично, с отверстиями), это хорошая практика для инвестиций в автоматизацию тестирования. Как вам известно, в случае треугольника все вершины должны быть на сфере; давайте проверить ваше решение по этому факту:

public static class SphereValidator { 
    private static Random m_Random = new Random(); 

    private static String Validate() { 
     var triangle = Enumerable 
     .Range(0, 3) 
     .Select(i => new Point(m_Random.Next(100), m_Random.Next(100), m_Random.Next(100))) 
     .ToArray(); 

     Sphere solution = new Sphere(triangle); 
     double tolerance = 1.0e-5; 

     for (int i = 0; i < triangle.Length; ++i) { 
     double r = triangle[i].Distance(solution.Center); 

     if (Math.Abs(r - solution.Radius) > tolerance) { 
      return String.Format("Counter example\r\n A: {0}\r\n B: {1}\r\n C: {2}\r\n expected distance to \"{3}\": {4}; actual R {5}", 
      triangle[0], triangle[1], triangle[2], (char) ('A' + i), r, solution.Radius); 
     } 
     } 

     return null; 
    } 

    public static String FindCounterExample(int attempts = 10000) { 
     for (int i = 0; i < attempts; ++i) { 
     String result = Validate(); 

     if (!String.IsNullOrEmpty(result)) 
      Console.WriteLine(result); 

     return; 
     } 

     Console.WriteLine(String.Format("Yes! All {0} tests passed!", attempts)); 
    } 
    } 

Я просто запустить выше код и получил:

Counter example 
    A: (3, 30, 9) 
    B: (1, 63, 40) 
    C: (69, 1, 16) 
    expected distance to "A": 35.120849609375; actual R 53.62698 

Answer 2

Для грубом приближении вычислить выровненный по осям габаритный прямоугольник, то ограничивающая сфера этого ящика (тот же центр, диаметр = √ (W² + H² + D²)).

Вы можете исправить, вычислив наибольшее расстояние от этого центра.