Размах по диагонали и ортогональное расстояние от точки до диагонали

Question

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

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

// 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

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

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 - что именно то, что вы хотите.

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

---

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