Finden Sie die Fläche des größten konvexen Polygons

28

Suchen Sie anhand einer Liste mit ganzzahligen Koordinaten den Bereich des größten konvexen Polygons, das Sie aus der Liste erstellen können, so dass:

  • Jeder Scheitelpunkt ist in der Liste
  • Das Polygon enthält kein Element der Liste.

Beispiel:

(0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)

Visualisiert:

o       o
o  o   o
 o   o   o
  o  o o
   o
     o     o

Das größte konvexe Polygon, das Sie daraus erstellen können, ist Folgendes:

o     
o  o  
 o   o
  o  o
   o
     o

Mit einer Fläche von 12.


Sie können die Koordinatenliste in jedem vernünftigen Format verwenden und sollten (entsprechend Ihrer Sprache) den Bereich des größten konvexen Polygons ausgeben, der auf mindestens zwei Nachkommastellen gerundet ist.

Außerdem müssen Sie einen Algorithmus verwenden und nicht einfach alle Teilmengen der Punkte brachial erzwingen. Um dies zu erzwingen, muss Ihr Programm auf einem modernen PC in weniger als einer Minute eine Liste von 50 Scheitelpunkten auflösen.

Kürzester Code in Bytes gewinnt.

orlp
quelle
Kennen Sie einen schnellen Algorithmus für den schlimmsten Fall?
Xnor
3
Wenn Sie ein Zeitlimit für 100 Scheitelpunkte festlegen möchten, sollten Sie wahrscheinlich mindestens einen solchen Testfall einschließen (idealerweise mehrere, z. B. einen, bei dem alle 100 Scheitelpunkte Teil der Lösung sind, einen, bei dem 99 Scheitelpunkte und einen, bei dem nur 10 Scheitelpunkte vorhanden sind). .
Martin Ender
@ MartinBüttner Leider kann ich diesen Testfall nicht generieren, da ich selbst keine funktionierende Implementierung habe. Das Problem ist ziemlich knifflig :)
Orlp
@xnor Ein paar Beispiele finden Sie hier .
Orlp
msgstr "auf mindestens 2 Nachkommastellen gerundet"?
DavidC

Antworten:

12

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

Hier ist eine ES5-Version oder eine niedrigere Version, die in den meisten Browsern und Knoten ohne Optimierung funktionieren sollte: 827 Byte

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 gibt eine anonyme Funktion zurück. Als Parameter wird beispielsweise ein Array von Punkten verwendet [[0,1],[2,3],[4,5]]. Um es zu verwenden, können Sie es var f=davor platzieren oder, wenn Sie es über die Befehlszeile verwenden möchten, (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))an das Ende anfügen und es wie folgt aufrufennode convpol.js '(1,2)(3,4)(5,6)'

Danke für die Herausforderung! Da es keine Referenzimplementierung gibt, kann ich nicht beweisen, dass dies korrekt ist, aber es ist zumindest für Permutationen der Punktliste konsistent. Ich hätte fast nicht gedacht, dass dies funktionieren würde, da Versionen mit Debugging-Code, selbst deaktiviert, mit exponentiellem Zeitanstieg viel zu langsam waren. Ich entschied mich trotzdem, Golf zu spielen, und war erfreut zu sehen, dass es für 50 Punkte auf meiner Maschine auf unter 2 Sekunden abfiel. Es kann ungefähr 130 Punkte in 1 Minute berechnen.

Der Algorithmus ähnelt dem Graham-Scan , muss jedoch überall nach leeren konvexen Hüllen suchen.

Erläuterung

Hier ist eine allgemeine Übersicht über die Funktionsweise des Algorithmus. Bei diesem Algorithmus wird nur nach konvexen Schleifen gegen den Uhrzeigersinn gesucht, die keinen Punkt einschließen. Das Verfahren sieht ungefähr so ​​aus:

  1. Beginnen Sie mit einem Punktepaar und einer Liste aller anderen Punkte.
  2. Wenn das aktuelle Punktepaar genau einen Punkt in der Liste durchläuft, halten Sie an.
  3. Filtern Sie alle Punkte des aktuellen Paares im Uhrzeigersinn heraus, da sie das Polygon konkav machen würden.
  4. Führen Sie für alle verbleibenden Punkte die folgenden Schritte aus:
    1. Wenn eine Linie von diesem Punkt zum ersten Punkt der Kette durch Punkte gegen den Uhrzeigersinn verläuft oder diese einschließt, überspringen Sie diesen Punkt, da Polygone den Punkt einschließen würden.
    2. Fügen Sie diesen Punkt der Kette hinzu, und wiederholen Sie Schritt 1 mit der aktuellen Kette und der Liste der Punkte.
  5. Wenn keine Punkte mehr vorhanden sind und die Kette mindestens 3 Punkte hat, ist dies ein gültiges konvexes Polygon. Erinnern Sie sich an den größten Bereich dieser Polygone.

Außerdem zeichnen wir zur Optimierung das erste Paar der Kette als markiert auf, sodass jede Suche nach dem Anzeigen dieses Paares an einer beliebigen Stelle in der Kette sofort abgebrochen werden kann, da das größte Polygon mit diesem Paar bereits gefunden wurde.

Dieser Algorithmus sollte niemals zweimal ein Polygon finden, und ich habe dies experimentell überprüft.

ricochet1k
quelle
2
+1, das ist eine erstaunliche Antwort. Sie könnten in der Lage sein, zu ersetzen ===und !==mit ==und !=, aber ich konnte nicht sicher sein, ohne Ihren Code zu verstehen ...
jrich
1
Vielen Dank! Diese speziellen === und! == vergleichen Objekte, also nein, leider. Früher wurden Indizes verglichen, aber (x,i)=>p.i==i(13 Zeichen) sind x=>p===xauch nach der Optimierung viel länger als (8 Zeichen).
Ricochet1k
2
Es gibt eine Erklärung für Sie @Lembik
Ricochet1k
1
Sie scheinen den in den Kommentaren der verknüpften SO-Frage erwähnten O (n ^ 3) -Register besiegt zu haben!
1
Okay, ich komme dahin, wo ich nicht glaube, dass es möglich ist, dass dies in weniger als O (n ^ 3) läuft. Ich bin sehr neu in der algorithmischen Komplexität.
Ricochet1k