Diagonal sweep and orthogonal distance of a point to diagonal

Question

I have a problem where I'm required to find the maximum number of points that are less than or equal to a given distance D to a line drawn in a two-dimensional Euclidean plane. To solve this I wrote the algorithms that would compute a possible maximum if the line was orthogonal to either the x-axis or the y-axis. My problem is when only a diagonal line would yield the maximum number of points.

Given the constraints that both x and y have a minimum value of -1000000 and maximum of 1000000. I wrote the following algorithm to try and find out the maximum. I don't seem to be getting the right answer. Could someone please guide me on where I am going wrong. I've tried drawing a regression line as well but that used vertical distance which did not work for my purposes. Maybe I'm going all wrong and this problem can be solved as an optimization problem. Anyways' any help with a descent explanation is much appreciated.

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

Not entirely sure I understand your intention. You loop through degrees from 0 to 180, then create a line at that angle... but passing through what origin point? — dbc, Feb 12 '15 at 05:49
what is this about? you have many points somewhere and have to regress a line through them and then select all points up to some distance from it? because OP text and code are confusing me (text implies you do not know the points and code is bruteforceing points and line) so what is know and what is unknown? If points are unknown are they on some grid? (I am not C# coder so I may be missing something) — Spektre, Feb 12 '15 at 07:45
btw look here: http://stackoverflow.com/a/20888844/2521214 it might help a bit — Spektre, Feb 12 '15 at 07:48
@Spektre the points are known. I begin by creating the segment AB using variables x1 and x2 for Point A and B respectively. Point P is the point whose perpendicular distance to the segment AB I wish to measure. The only thing not shown is the class Point and the arrays X and Y which have the coordinates for Point P as x[i] and y[i] — TheJackal, Feb 12 '15 at 08:10
then the link from my last comment (find the line from set of known points) is what you need. be aware does not find optimal solution just close one to it. from that you can add the close point selection ... If you want optimal solution then search for line regression ... — Spektre, Feb 12 '15 at 08:13

score 0 · Answer 1 · answered Feb 11 '15 at 09:35

If you want to define this problem as an optimization problem, you should do it as follows, but it doesn't seem to me this optimization problem is solveable efficiently as is.

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}

Explanation:

x_i are inclusion variables - can get a value of 0 / 1 , and it indicates if the point p_i is in the required distance from the line.
a,b,c are the parameters for the line: ax + by + c = 0
The idea is to maximize the sum of included points, such that each included point is in the desired range. This is represented by the constraint, if x_i=0 - there is no restriction on the point p_i, as the constraint is always satisfied. Otherwise, x_i=1, and you need the distance from the line (let it be d) satisfy 1* d/MAX_DISTANCE <= 1 - which is exactly what you want.

Though I don't think there is an optimal efficient solution to this optimization problem, you might want to try some heuristical solutions for this optiization - such as Genetic Algorithms or Hill Climbing

As a side note, my gut says this problem is NP-Complete, though I have no proof for it yet - and will update this part of the answer if I (or someone else) can come up with a reduction/polynomial solution.

Diagonal sweep and orthogonal distance of a point to diagonal

1 Answers1