How to Find Largest Triangle Area using Shoelace Formula?

You have a list of points in the plane. Return the area of the largest triangle that can be formed by any 3 of the points.
Example:
Input: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
Output: 2
Explanation:
The five points are show in the figure below. The red triangle is the largest.

largest-triangle-area

Given any three points, we know how to compute its triangle area, therefore, we can iterate all points in O(n^3) loops for each possible three points combination.

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

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        double value = -1;
        int sz = points.size();
        for (int i = 0; i < sz; ++ i) {
            for (int j = i + 1; j < sz; ++ j) {
                for (int k = j + 1; k < sz; ++ k) {
                    value = max(value, area(points[i], points[j], points[k]));
                }
            }
        }
        return value;
    }
}

class Solution {
public:
    double largestTriangleArea(vector<vector<int>>& points) {
        double value = -1;
        int sz = points.size();
        for (int i = 0; i < sz; ++ i) {
            for (int j = i + 1; j < sz; ++ j) {
                for (int k = j + 1; k < sz; ++ k) {
                    value = max(value, area(points[i], points[j], points[k]));
                }
            }
        }
        return value;
    }
}

To compute the area of the Triangle based on three coordinates, we can use the Shoelace formula, which is used to compute the area of any given 2D polygon shapes/coordinates.

The formula can be expressed by the following equation:

Where A is the area of the polygon and there are n sides of the polygon and x__i, y__i are the coordinates/corners of the polygon.

Example: the polygon made by points (3,4), (5,11), (12,8), (9,5), and (5,6), which can be illustrated in the following:

shoelace-formula-to-compute-polygon-area-example

The C++ function to compute Triangle Area based on Shoelace algorithm

The shoelace could be quite useful in computing triangle area given 3 coordinates/corners of the triangle.

1
2
3
4

double area(vector<int> P, vector<int> Q, vector<int> R) {
  return 0.5 * abs(P[0] * Q[1] + Q[0] * R[1] + R[0] * P[1]
                   - P[1] * Q[0] - Q[1] * R[0] - R[1] * P[0]);
}

double area(vector<int> P, vector<int> Q, vector<int> R) {
  return 0.5 * abs(P[0] * Q[1] + Q[0] * R[1] + R[0] * P[1]
                   - P[1] * Q[0] - Q[1] * R[0] - R[1] * P[0]);
}

–EOF (The Ultimate Computing & Technology Blog) —