Javascript ES6, 738 bytes
((V,C,L,r,k,n,A,G,F,e,i,j,q)=>p=>{p=p.map((p,i)=>({i:i,x:p[0],y:p[1]}));A=(f,p,a,b,v,i)=>{for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))return 1};G=(p,i,a)=>{for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=(p,s,l,f,a,b,v)=>(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A((a,b)=>C(a,b)?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b),p,a,b)?0:(p=(v=V(a,b),p[k](x=>C(v,V(a,x))>=0)),A((a,b)=>C(a,b)>0,p,b,f)?0:(p.map(q=>F(p[k](r=>q!==r),[...s,q])),s[2]&&!p[n]&&!e[b.i][f.i]?G(s):0)));e=p.map(x=>p.map(y=>x===y));for(i=p[n];i--;){for(j=i;j--;){q=p[k]((p,x)=>x-i&&x-j);F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)})((a,b)=>({x:b.x-a.x,y:b.y-a.y}),(a,b)=>a.x*b.y-a.y*b.x,v=>v.x*v.x+v.y*v.y,0,'filter','length')
Here's an ES5 or less version that should work in most browsers and node without tweaking: 827 bytes
eval("(%V,C,L,r,k,n,A,G,F,e,i,j,q){@%p){p=p.map(%p,i){@{i:i,x:p[0],y:p[1]}});A=%f,p,a,b,v,i){for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))@1};G=%p,i,a){for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=%p,s,l,f,a,b,v){@(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A(%a,b){@C(a,b)!=0?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b)},p,a,b)?0:(p=(v=V(a,b),p[k](%x){@C(v,V(a,x))>=0})),A(%a,b){@C(a,b)>0},p,b,f)?0:(p.forEach(%q){@F(p[k](%r){@q!==r}),s.concat([q]))}),s[2]&&p[n]==0&&!e[b.i][f.i]?G(s):0)))};e=p.map(%x,i){@p.map(%y,j){@i==j})});for(i=p[n];i--;){for(j=i;j--;){q=p[k](%p,x){@x!=i&&x!=j});F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)}})(%a,b){@{x:b.x-a.x,y:b.y-a.y}},%a,b){@a.x*b.y-a.y*b.x},%v){@v.x*v.x+v.y*v.y},0,'filter','length')".replace(/%/g,'function(').replace(/@/g,'return '))
Code returns an anonymous function. As a parameter, it takes an array of points, like [[0,1],[2,3],[4,5]]
. To use it you can place var f=
before it, or if you want to use it from the command line, add (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))
to the end, and call it like node convpol.js '(1,2)(3,4)(5,6)'
Thanks for the challenge! As there is no reference implementation, I can't prove this is correct, but it is consistent at least for permutations of the point list. I almost didn't think this was going to work, as versions with debugging code, even disabled, were way too slow with exponential time increase. I decided to golf it anyway, and was pleased to see that it dropped down to under 2 seconds for 50 points on my machine. It can calculate approximately 130 points in 1 minute.
The algorithm is similar to the Graham scan, except that it has to search for empty convex hulls everywhere.
Explanation
Here's a high-level overview of how the algorithm works. The meat of this algorithm is just searching for counter-clockwise convex loops that don't enclose a point. The procedure is something like this:
- Start with a pair of points, and a list of all other points.
- If the current pair of points goes exactly through any point in the list, stop.
- Filter out all points clockwise of the current pair, since they would make the polygon concave.
- For all points left, do the following:
- If a line from this point to the first point of the chain goes through or encloses any points counter-clockwise, skip this point, since any polygons would enclose the point.
- Add this point to the chain, recurse from step 1 with the current chain and list of points.
- If there were no points left, and the chain has at least 3 points, this is a valid convex polygon. Remember the largest area of these polygons.
Also, as an optimization, we record the initial pair of the chain as checked, so any searches afterwards upon seeing this pair anywhere in the chain can immediately stop searching, since the largest polygon with this pair has already been found.
This algorithm should never find a polygon twice, and I've experimentally verified this.