What you are looking for is called the shoelace formula:
\begin{align*}
\text{Area}
&= \frac12 \big| (x_A - x_C) (y_B - y_A) - (x_A - x_B) (y_C - y_A) \big|\\
&= \frac12 \big| x_A y_B + x_B y_C + x_C y_A - x_A y_C - x_C y_B - x_B y_A \big|\\
&= \frac12 \Big|\det \begin{bmatrix}
x_A & x_B & x_C \\
y_A & y_B & y_C \\
1 & 1 & 1
\end{bmatrix}\Big|
\end{align*}
The last version tells you how to generalize the formula to higher dimensions.
PS. Another generalization of the formula is obtained by noting that it follows from a discrete version of the Green's theorem:
$$ \text{Area} = \iint_{\text{domain}}dx\,dy = \frac12\oint_{\text{boundary}}x\,dy - y\,dx $$
Thus the signed (oriented) area of a polygon with $n$ vertexes $(x_i,y_i)$ is
$$ \frac12\sum_{i=0}^{n-1} x_i y_{i+1} - x_{i+1} y_i $$
where indexes are added modulo $n$.
Rewritten on 2018-03-26.
We only need to rely on the following four statements:
The sign of the 2D analog of the vector cross product indicates whether the second vector is clockwise (positive) or counterclockwise (negative) with respect to the first vector, in a standard right-handed coordinate system.
If the 2D analog of the vector cross product is zero, the two vectors are collinear.
If the 2D analog of the vector cross product between consecutive pairs of edge vectors in a polygon has differing signs (ignoring zeroes, as if they had no sign), the polygon must be concave.
If we examine the signs of the $x$ and $y$ components of the edge vectors, (again ignoring zeroes as if they had no sign), consecutively along the polygon, as a circular list, there must be exactly two sign changes, or the polygon is concave.
Statements 1, 2 and 3 are known from basic vector algebra.
Statements 3 and 4 combined, is equivalent to calculating the angle between each pair of consecutive edges in the polygon, and verifying that they are all in the same orientation (counterclockwise or clockwise), and that the sum of the angles is 360° (so that we can correctly detect self-intersecting polygons), except that we only consider four separate directions (the four quadrants in a standard coordinate system).
In pseudocode, the testing algorithm is as follows:
Function isconvex(vertexlist):
If (the number of vertices in 'vertexlist' < 3), Then
Return FALSE
End If
Let wSign = 0 # First nonzero orientation (positive or negative)
Let xSign = 0
Let xFirstSign = 0 # Sign of first nonzero edge vector x
Let xFlips = 0 # Number of sign changes in x
Let ySign = 0
Let yFirstSign = 0 # Sign of first nonzero edge vector y
Let yFlips = 0 # Number of sign changes in y
Let curr = vertexlist[N-1] # Second-to-last vertex
Let next = vertexlist[N] # Last vertex
For v in vertexlist: # Each vertex, in order
Let prev = curr # Previous vertex
Let curr = next # Current vertex
Let next = v # Next vertex
# Previous edge vector ("before"):
Let bx = curr.x - prev.x
Let by = curr.y - prev.y
# Next edge vector ("after"):
Let ax = next.x - curr.x
Let ay = next.y - curr.y
# Calculate sign flips using the next edge vector ("after"),
# recording the first sign.
If ax > 0, Then
If xSign == 0, Then
xFirstSign = +1
Else If xSign < 0, Then
xFlips = xFlips + 1
End If
xSign = +1
Else If ax < 0, Then
If xSign == 0, Then
xFirstSign = -1
Else If xSign > 0, Then
xFlips = xFlips + 1
End If
xSign = -1
End If
If xFlips > 2, Then
Return FALSE
End If
If ay > 0, Then
If ySign == 0, Then
yFirstSign = +1
Else If ySign < 0, Then
yFlips = yFlips + 1
End If
ySign = +1
Else If ay < 0, Then
If ySign == 0, Then
yFirstSign = -1
Else If ySign > 0, Then
yFlips = yFlips + 1
End If
ySign = -1
End If
If yFlips > 2, Then
Return FALSE
End If
# Find out the orientation of this pair of edges,
# and ensure it does not differ from previous ones.
w = bx*ay - ax*by
If (wSign == 0) and (w != 0), Then
wSign = w
Else If (wSign > 0) and (w < 0), Then
Return FALSE
Else If (wSign < 0) and (w > 0), Then
Return FALSE
End If
End For
# Final/wraparound sign flips:
If (xSign != 0) and (xFirstSign != 0) and (xSign != xFirstSign), Then
xFlips = xFlips + 1
End If
If (ySign != 0) and (yFirstSign != 0) and (ySign != yFirstSign), Then
yFlips = yFlips + 1
End If
# Concave polygons have two sign flips along each axis.
If (xFlips != 2) or (yFlips != 2), Then
Return FALSE
End If
# This is a convex polygon.
Return TRUE
End Function
where !=
is the not-equal operator. This approach considers vertex lists with less than three vertices concave, but as this is determined by the very first If
clause, you can change it to suit yourself. Degenerate polygons with at least three points, so either all the same point, or collinear, are considered convex by this approach.
Note that because this implementation does only two multiplications, and a number of additions, subtractions, and comparisons per polygon edge, it should be extremely efficient approach in most programming languages.
In a practical implementation, you might wish to replace > 0
with > eps
, < 0
with < eps
, x == 0
with x >= -eps && x <= eps
, and x != 0
with x < -eps || x > eps
, to account for rounding errors with floating-point numbers. I'd use an eps
about one quarter to one sixteenth of the smallest meaningful change in either $x$ or $y$ coordinates.
Best Answer
Incomplete proof
Since $P$ is convex, we can uniquely truncate $P$ with right-angled triangles with hypotenuses equal to the side lengths of $P$ and the remaining rectilinears inside.
Let reducible triangle be a right-angled triangle with Pythagorean triple $(a,b,c)$ where both $a$,$b$ and $c$ are divisible by $n$.
If all triangles above truncating $P$ is reducible triangles, area of each triangle and rectilinear is divisible by $n^2$. Thus, $2S$ must be divisible by $n$.
Please figure out the case with $P$ truncated by some non-reducible triangles.