Диагональная развертка и ортогональное расстояние от точки до диагонали

Question

У меня проблема, когда мне нужно найти максимальное количество точек, которые меньше или равно заданному расстоянию D до линии, нарисованной в двумерном евклидовом самолет. Чтобы решить эту проблему, я написал алгоритмы, которые вычисляли бы возможный максимум, если бы линия была ортогональна либо по оси х, либо по оси у. Моя проблема заключается в том, что только диагональная линия будет давать максимальное количество точек.

Учитывая ограничения, что и x, и y имеют минимальное значение -1000000 и максимум 1000000. Я написал следующий алгоритм, чтобы попытаться узнать максимум. Кажется, я не получаю правильный ответ. Мог бы кто-нибудь, пожалуйста, направить меня туда, где я ошибаюсь. Я попытался также рисовать линию регрессии, но использовал вертикальное расстояние, которое не срабатывало для моих целей. Возможно, я ошибаюсь, и эта проблема может быть решена как проблема оптимизации. В любом случае, любая помощь с объяснением спуска очень ценится.

// diagonal sweep 
     for (int degree = 1; degree < 180; degree++) if (degree % 90 != 0) 
     { 
      int k = 1, degrees = degree; 
      double x1 = -1000000, x2 = 1000000; 
      if (degree > 90 && degree < 180) 
      { 
       degrees = 180 - degrees; 
       k = -1; 
      } 
      //slope 
      double m1 = Math.Tan(Math.PI * degrees * k/180.0); 
      //Point A 
      Point A = new Point(x1, m1 * x1); 
      //Point B 
      Point B = new Point(x2, m1 * x2); 
      for (int i = 0; i < x.Length; i++) 
      { 
       //Point P = household that needs power 
       Point P = new Point(x[i], y[i]); 
       double normalLength = Math.Sqrt((B.X - A.X) * (B.X - A.X) + (B.Y - A.Y) * (B.Y - A.Y)); 
       double segmentLength = 1d * Math.Abs((P.X - A.X) * (B.Y - A.Y) - (P.Y - A.Y) * (B.X - A.X))/normalLength; 
       if (segmentLength <= D) 
        tempCnt++; 
      } 
      maxConnections = Math.Max(maxConnections, tempCnt); 
      tempCnt = 0; 
     } 

     return maxConnections; 

Answer 1

Если вы хотите, чтобы определить эту проблему как задачу оптимизации, вы должны сделать это как следует, но это не кажется мне эта проблема оптимизации solveable эффективно, как это.

maximize: x_1 + x_2 + ... + x_n + 0*a + 0*b + 0*c 
s.t. 
    x_i * d(p_i, line(a,b,c))/ MAX_DISTANCE <= 1 
    x_i is in {0,1} 

Пояснение:

• x_i являются переменными включения - можно получить значение 0/1, и это указывает на то, если точка p_i находится в требуемом расстоянии от линии.
• a,b,c являются параметрами для линии: ax + by + c = 0
• Идея заключается в том, чтобы максимизировать сумму включаемых точек, таким образом, что каждая включена точка находится в требуемом диапазоне. Это представлено ограничением, если x_i = 0 - нет ограничений на точку p_i, так как ограничение всегда выполняется. В противном случае x_i = 1, и вам нужно расстояние от линии (пусть оно будет d) удовлетворяют 1* d/MAX_DISTANCE <= 1 - это именно то, что вы хотите.

Хотя я не думаю, что существует оптимальное эффективное решение этой проблемы оптимизации, вы можете попробовать некоторые эвристического решения этой optiization - такие, как Genetic Algorithms или Hill Climbing

---

В качестве стороны Заметьте, моя кишка говорит, что эта проблема NP-Complete, хотя у меня пока нет доказательств - и обновит эту часть ответа, если я (или кто-то другой) может придумать решение для сокращения/полинома.