Find the smallest triangle encompassing the specified polygon

Question

Input: An integer N which represents the polygon's vertices and a list of their x and y coordinates.

Expected output: The smallest difference possible between the area of the(not necessarily convex) polygon and the triangle containing it. The triangle also has to share at least 2 vertices with the polygon. If there is no such triangle print -1.

Example:

4
0,0
2,0
1,1
0,2

Output: 0, because the polygon matches up perfectly with the triangle.

This is code-golf so answers will be scored in bytes with less bytes being better.

Answer 1

Python 3.9.12: ^{588 585 583 580 578} 572 bytes

3 bytes saved thanks to Jiří, and 2 bytes saved thanks to clarification from att!

from numpy import*
from itertools import*
def J(V):
 c,a,X,I=combinations,array,cross,vstack;V=[*map(a,V)];s=lambda A,B,P:sign(X(B-A,P-A));Q=lambda v,w,G:all((_:=[x for p in G if any(p-v)*any(p-w)*(x:=s(v,w,p))])==_[0]);F=lambda Z:abs(sum([linalg.det(I((Z[i],Z[i+1])))for i in range(len(Z)-1)]))/2;W=[a([_[0]/_[2],_[1]/_[2]])for k,l in c([a([v,w])for v,w in c(V,2)if Q(v,w,V)],2)if(_:=X(X((h:=hstack((I((k,l)),ones((4,1)))))[0],h[1]),X(h[2],h[3])))[2]!=0];return min([F(e)-F(V)for v,w in c(V,2)for k in W if s(*(e:=[v,w,k]))and Q(w,v,D:=V+e)*Q(k,w,D)*Q(v,k,D)],default=-1)

ATO link

The input for the number of vertices is ignored since it is not used or needed.

The function J takes in the input vertices, V, as a list of tuples/lists. An example function call would be J([(0,0),(1,3),(1,1),(2,0)]).

The code assumes that a polygon is defined as most people would define a polygon (made of vertices connected by non-intersecting edges)

Code explained by line/function

from numpy import*
from itertools import*
def J(V):
 c,a,X,I=combinations,array,cross,vstack;

Normal byte-saving code. Nothing fancy.

V=[*map(a,V)];

Converting the list of tuples into a list of numpy arrays. This can't be left as a map object because of some stuff that is done later.

s=lambda A,B,P:sign(X(B-A,P-A));

s takes in three points A,B,P and returns which side of the line connecting AB is point P using the cross product. The two vectors have two elements so numpy treats them as vectors of the form [x,y,0] and returns only the z component. If P is on the "right" of the line AB, s = -1. On the left, s = +1. If P is on the line AB then s = 0.

Q=lambda v,w,G:all((_:=[x for p in G if any(p-v)*any(p-w)*(x:=s(v,w,p))])==_[0]);

Q takes in two points, v and w, and a set of vertices G. Essentially, this is checking if the line vw places all points in G into the same half of the plane (or onto the line). If that is the case, then it returns True. Otherwise, False. any(p-v) is used instead of the more traditional p==v because numpy arrays can't be directly compared in that way due to "ambiguity".

F=lambda Z:abs(sum([linalg.det(I((Z[i],Z[i+1])))for i in range(len(Z)-1)]))/2;

F takes in Z, a list of vertices of a polygon, and returns the area of that polygon using the shoelace formula. This doesn't work with polygons whose edges intersect, but those polygons have ill-defined areas anyway.

W=list([a([_[0]/_[2],_[1]/_[2]])for k,l in c([a([v,w])for v,w in c(V,2)if Q(v,w,V)],2)if(_:=X(X((h:=hstack((I((k,l)),ones((4,1)))))[0],h[1]),X(h[2],h[3])))[2]!=0]));

Breaking this down:

[a([v,w])for v,w in c(V,2)if Q(v,w,V)] returns a list of 2x2 numpy array the represents the line formed by the points vw, where every combination of two points in the input polygon V gets a chance at being vw, if the line vw places all points in V onto one side of the plane (or on the line). The reason for this is to get a set of lines that forms the boundary of the polygon. Think of it as taking all the vertices that would make the input polygon convex, connecting them with edges, then extending those edges into lines.

The rest of this line is devoted to determining where those lines intersect (if they were extended infinitely far). This is done using homogenous coordinates. Another example can be found in this stackoverflow thread, whose code this is based on.

The reason for this is to determine exactly where could the vertices of the all of the triangles that could envelop the input polygon lie.

min([F(e)-F(V)for v,w in c(V,2)for k in W if s(*(e:=[v,w,k]))and Q(w,v,D:=V+e)*Q(k,w,D)*Q(v,k,D)],default=-1)

This one is very simple. For every combination of points v,w in V and then every point in W (the line intersections), first check to see if all three points are collinear using the function s. If they're not, then we check to see if all points in V are inside of the triangle formed by vwk. This is done by checking if all of the points in V, also including the three points v,w,k, are all on the same side of the plane when intersected by a line made of two of the points. Since it's a triangle, if all the "third points" are on the same side of the plane as the two points forming a line (for all three combinations of v,w,k), then all points must be inside the triangle or on the edge of it.

Lastly, we take get the area of each triangle that satisfies our conditions and subtract off the area of the input polygon. Then, the minimum area is returned. If there is no minimum area to return (because no triangle exists that satisfies all conditions), then -1 is returned instead.

---

This is my first code golf answer so please let me know if I missed anything major with the question or if there is somewhere bytes can be saved!