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 + bm, 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();
}
Last modified 3yr ago