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

  • 时间:2020-09-27 14:36:16
  • 分类:网络文摘
  • 阅读:94 次

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 How to Check if Any Three Points can Make a Triangle? algorithms c / c++ geometry math programming languages

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 tex_5e92d77231c69accc9f13175bc814743 How to Check if Any Three Points can Make a Triangle? algorithms c / c++ geometry math programming languages 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

tex_3325c681ec54f57cf20c080c735f002b How to Check if Any Three Points can Make a Triangle? algorithms c / c++ geometry math programming languages

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) —

推荐阅读:
How to Reverse Words in a String?  Design a Logger Rate Limiter in C++/Java  C++ Coding Exercise: Smallest Range of Array  Coding For Profit: 4 Types Of Websites To Consider Building  How to Compute the Projection Area of 3D Shapes?  How To Find The Ideal Monitor For Coders?  How to Partition an Array Into Three Parts With Equal Sum?  Compute the Sum of Even Numbers After Queries  How to Compute Nested List Weight Sum of Any Arrays?  7 Laws Every Blogger Must Know to Avoid Lawsuits 
评论列表
添加评论