How to Check if Any Three Points can Make a Triangle?

How to Check if Any Three Points can Make a Triangle?

There are many ways to check if any given three points in 2D plane can make a triangle. This includes: computing the triangle area and using the line equation.

geometry

A boomerang is a set of 3 points that are all distinct and not in a straight line. Given a list of three points in the plane, return whether these points are a boomerang.

Example 1:
Input: [[1,1],[2,3],[3,2]]
Output: true

Example 2:
Input: [[1,1],[2,2],[3,3]]
Output: false

Note:
points.length == 3
points[i].length == 2
0 <= points[i][j] <= 100

Compute Triangle Area

By computing the triangle area, we know if the three points can make a triangle if the area is not zero:

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        vector<int> a = points[0];
        vector<int> b = points[1];
        vector<int> c = points[2];
        
        return ((a[0] * (b[1] - c[1]) +  
            b[0] * (c[1] - a[1]) +  
            c[0] * (a[1] - b[1])) != 0);
    }
};

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        vector<int> a = points[0];
        vector<int> b = points[1];
        vector<int> c = points[2];
        
        return ((a[0] * (b[1] - c[1]) +  
            b[0] * (c[1] - a[1]) +  
            c[0] * (a[1] - b[1])) != 0);
    }
};

Compute the Line Equation

We know that we can use to represent a line in mathematics where A = (Y0 – Y1), B = (X0 – X1), and C is a constant value. If a point (X2, Y2) satisfies that

Then it is on the line formed by points (X0,Y0) and (X1,Y1).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& p) 
    {
        // all 3 points must be different
        if (p[0] == p[1] || p[0] == p[2]) {
            return false;
        }
 
        const int A = p[0][0] - p[1][0];
        const int B = p[0][1] - p[1][1];
        
        auto C = [=](vector<int>& pt) { return A * pt[1] - B * pt[0]; };
        
        return C(p[0]) != C(p[2]);
    }
};

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& p) 
    {
        // all 3 points must be different
        if (p[0] == p[1] || p[0] == p[2]) {
            return false;
        }

        const int A = p[0][0] - p[1][0];
        const int B = p[0][1] - p[1][1];
		
        auto C = [=](vector<int>& pt) { return A * pt[1] - B * pt[0]; };
		
        return C(p[0]) != C(p[2]);
    }
};

The above C is a inline function that computes the C constant, and syntax “[=]” captures all the values used in the function, namely A and B.

Alternatively, we can check if A B and C are on the same line by arranging the line equation e.g. y = kx + b. If three points are colinear, we know that b and k should be the same for two lines. Thus, checking the y/x should be sufficient.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int m1 = 0, m2 = 0;
        int x1 = points[0][0];
        int x2 = points[1][0];
        int x3 = points[2][0];
        int y1 = points[0][1];
        int y2 = points[1][1];
        int y3 = points[2][1];
        return ((y3 - y2) * (x2 - x1) !=  (y2 - y1) * (x3 - x2));
    }
};

class Solution {
public:
    bool isBoomerang(vector<vector<int>>& points) {
        int m1 = 0, m2 = 0;
        int x1 = points[0][0];
        int x2 = points[1][0];
        int x3 = points[2][0];
        int y1 = points[0][1];
        int y2 = points[1][1];
        int y3 = points[2][1];
        return ((y3 - y2) * (x2 - x1) !=  (y2 - y1) * (x3 - x2));
    }
};

–EOF (The Ultimate Computing & Technology Blog) —