Best Line

16.14 Best Line: Given a two-dimensional graph with points on it, find a line which passes the most number of points.

• Brute force:

  • A line is defined by two points. If we define a line with a fixed one point, that passes through all other points. We will define n number of lines, where n is the number of points. For every line we define, we check to see the number of times it passes through the points while in the process also maintaining a maximum. We check this by seeing whether or not (x,y) makes a valid solution with the line. Total, we will have defined n^2 lines, and for each line scanned through a list of n points. Order n^2 * n = n^3.

• Better:

  • Instead of having to scan through the number of times it passes through the points, we can map the line defined by two points into a hash table, and keep track of its frequency. This will tone it down to order n^2 + n.

  • The book defined using an epsilon for the slope of a hash key because, there may be some imperfect associations with floating point keys and their hash value. For me, this would be an issue, because my key will directly be a string that represents the line in its entirety e.g. y = mx + b m, and b will both by floating point values, but I will tone down their precision just a tag. This will be my epsilon. This will simplify the process while maintain accuracy.

class Line {
public:
    Line(pair<float, float> p1, pair<float, float> p2) {
        this->p1 = p1;
        this->p2 = p2;
        line = defineLine(p1, p2);
    }

    static string defineLine(pair<float, float> p1, pair<float, float> p2);
    string line;

private:
    pair<float, float> p1, p2;

    static float getSlope(pair<float, float> p1, pair<float, float> p2);
    static float getY_int(pair<float, float> p1, float slope);
};

float round_down_2(float flt) {
    return floorf(flt * 100) / 100;
}

float Line::getSlope(pair<float, float> p1, pair<float, float> p2) {
    return (round_down_2((p2.second - p1.second) / (p2.first - p1.first)));
}

float Line::getY_int(pair<float, float> p1, float slope) {
    return (round_down_2(p1.second - (slope * p1.first)));
}

string Line::defineLine(pair<float, float> p1, pair<float, float> p2) {
    float slope = getSlope(p1, p2);
    float y_int = getY_int(p1, slope);
    string line = "y = " + to_string(slope) + "x + " + to_string(y_int);
    return line;
}

string getMostFreqLine(unordered_map<string, int> &lines) {
    string str;
    int max = 0;

    for (auto &i : lines) {
        if (i.second > max) {
            max = i.second;
            str = i.first;
        }
    }
    return str;
}

string findBiggestLine(vector<pair<int, int>> &points) {
    // <line key, frequency value>
    unordered_map<string, int> lines;

    // 1). Define a line with every point discluding itself
    //     and map it into the hash table with its frequency

    int size = points.size();
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            if (i == j) continue;
            else {
                // define the line
                Line line(points.at(i), points.at(j));

                //cout << line.line << endl;
                //pause();

                // map into the hash table if it is found
                auto &found = lines.find(line.line);
                if (found == lines.end()) {
                    // not found
                    lines.insert({ {line.line},{1} });
                }
                else {
                    // found - update frequency
                    found->second++;
                }
            }
        }
    }

    // now find the line with the max frequency
    return getMostFreqLine(lines);
}


int main()
{
    vector<pair<int, int>> points = 
    {
        { { 1 },{ 1 } }, { { 2 },{ 2 } },
        { { 3 },{ 3 } }, { { 4 },{ 4 } },
        { { 5 },{ 5 } }, { { 6 },{ 6 } },
        { { 7 },{ 7 } }, { { 8 },{ 8 } }
    };

    cout << findBiggestLine(points) << endl;
    pause();


    points =
    {
        { { 1 },{ 1 } },{ { 3 },{ 3 } },
        { { 5 },{ 5 } },{ { 1 },{ 3 } },
        { { 5 },{ 1 } },{ { 7 },{ 4 } }
    };

    cout << findBiggestLine(points) << endl;
    pause();

    points =
    {
        { { -3 },{ -2 } },{ { -2 },{ 1 } },
        { { -1 },{ 4 } },{ { 2 },{ -1 } },
        { { 4 },{ -1 } },{ { 3 },{ -2 } }
    };

    cout << findBiggestLine(points) << endl;
    pause();

}