Hintergrund

Die konvexe Hülle einer endlichen Anzahl von Punkten ist das kleinste konvexe Polygon, das alle Punkte enthält, entweder als Eckpunkte oder im Inneren. Weitere Informationen finden Sie in dieser Frage zu PGM, die sie sehr gut definiert .

Eingang

N+12-D-Koordinaten ( N >= 3) werden STDINim folgenden Format durchlaufen (wobei auch andere übliche Golfeingaben zulässig sind) (die Anzahl der Dezimalstellen kann variieren, Sie können jedoch davon ausgehen, dass sie "angemessen" bleibt und jede Zahl als Float dargestellt werden kann):

0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

Ausgabe

Ein Wahrheitswert, der gedruckt wird STDOUT(oder ein Äquivalent), wenn sich der erste Punkt in der Liste ( (0.00;0.00000)im obigen Beispiel) in der konvexen Hülle der anderen N Punkte befindet, und ansonsten ein Falschwert.

Dies ist Code-Golf , also gewinnt die kürzeste Lösung in Bytes.

• Grenzfälle : Sie können einen beliebigen Wert zurückgeben (aber nicht abstürzen), wenn der Punkt am Rand des konvexen Rumpfs liegt (dh auf einer Seite oder auf einem Scheitelpunkt an der Außengrenze des Rumpfes), da dies eine Wahrscheinlichkeit von Null ist Ereignis (unter jeder vernünftigen Wahrscheinlichkeit).

• Verboten : alles (Sprache, Operator, Datenstruktur, Integriertes oder Paket), das nur zur Lösung geometrischer Probleme existiert (z. B. Mathematica's ConvexHull ). Allgemeine mathematische Werkzeuge (Vektoren, Matrizen, komplexe Zahlen usw.) sind zulässig.

Tests

• Sollte zurückkehren TRUE: spiralTest1-TRUE , squareTest1-TRUE
• Sollte zurückkehren FALSE: spiralTest2-FALSE , squareTest2-FALSE

J, 40 39 34 Bytes

3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

Eine anonyme dyadische Funktion, die einen Punkt p als eines ihrer Argumente und eine Liste von Punkten P als anderes Argument verwendet (es spielt keine Rolle, welches Argument welches ist) und zurückgibt 0oder 1, wenn p außerhalb von oder liegt innerhalb der konvexen Hülle von P , respectively. Der Punkt p und die Punkte in P werden als komplexe Zahlen genommen.

Beispiel

  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

oder...

Python 2, Funktion, 121 103, volles Programm, 162

Python 3, 149 Bytes

import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

Übernimmt die Eingabe im gleichen Format wie der ursprüngliche Beitrag über STDIN und gibt einen booleschen Wert aus, der angibt, ob sich p in der konvexen Hülle von P befindet

Erläuterung

Das Programm testet, ob die Differenz zwischen dem maximalen und dem minimalen (vorzeichenbehafteten) Winkel zwischen einem Punkt r in P , p und einem festen beliebigen Punkt q in P (wir verwenden nur den ersten Punkt in P ) weniger als 180 ° beträgt. Mit anderen Worten wird geprüft, ob alle Punkte in P in einem Winkel von 180 ° oder weniger um p enthalten sind . p befindet sich genau dann in der konvexen Hülle von P, wenn diese Bedingung falsch ist.

Auf Kosten einiger weiterer Bytes können wir eine ähnliche Methode verwenden, bei der wir keine expliziten Winkel berechnen müssen: Beachten Sie, dass die obige Bedingung der Aussage entspricht, dass p genau dann außerhalb der konvexen Hülle von P liegt, wenn es existiert eine Linie l bis p , so dass alle Punkte in P auf derselben Seite von l liegen . Wenn eine solche Linie existiert, gibt es auch eine solche Linie, die auf einen (oder mehrere) der Punkte in P fällt (wir können l drehen, bis sie einen der Punkte in P berührt ).

Um diese Linie (vorläufig) zu finden, lassen wir zunächst l die Linie durch p und den ersten Punkt in P sein . Wir iterieren dann über den Rest der Punkte in P ; Wenn einer der Punkte links von l liegt (wir nehmen durchgehend eine gewisse Richtwirkung an, links oder rechts spielt keine Rolle), ersetzen wir l durch die Linie, die durch p und diesen Punkt verläuft, und fahren fort. Nachdem wir über ganz P iteriert haben , sollten sich alle Punkte in P rechts von (oder auf) l befinden , wenn (und nur wenn) p außerhalb der konvexen Hülle liegt . Wir überprüfen dies mit einem zweiten Durchgang über die Punkte in P..

Python 2, 172 Bytes

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)

Um dasselbe in einem einzigen Durchgang zu tun, sei links von P eine Beziehung zwischen zwei beliebigen Punkten q und r in P , so dass q links von r steht, wenn q links ist der Linie durch p und r . Es ist zu beachten, dass links davon eine Ordnungsbeziehung auf P ist, wenn und nur wenn alle Punkte in P auf derselben Seite einer Linie liegen, die durch p verläuft, dh wenn p außerhalb der konvexen Hülle von P liegt . Das oben beschriebene Verfahren findet den Minimalpunkt in P.wrt diese Ordnung, das heißt, den „ganz links“ Punkt in P . Anstatt zwei Durchgänge durchzuführen, können wir das Maximum (dh den Punkt "ganz rechts") sowie das Minimum der Punkte in P in derselben Reihenfolge in einem einzigen Durchgang ermitteln und sicherstellen, dass das Minimum links vom Punkt liegt Maximum, dh effektiv, dass links davon transitiv ist.

Dies würde gut funktionieren, wenn sich p außerhalb der konvexen Hülle von P befindet. In diesem Fall ist links von tatsächlich eine Ordnungsrelation, kann jedoch brechen, wenn sich p innerhalb der konvexen Hülle befindet (versuchen Sie beispielsweise herauszufinden, was wird passieren, wenn wir diesen Algorithmus ausführen, bei dem die Punkte in P die Eckpunkte eines regulären Fünfecks sind, das gegen den Uhrzeigersinn verläuft, und p sein Zentrum ist.) Um dies zu berücksichtigen, ändern wir den Algorithmus geringfügig: Wir wählen einen Punkt q in P und halbieren P entlang der Linie durch p und q (dh wir teilen P um q auflinks von.) Wir haben jetzt einen "linken Teil" und einen "rechten Teil" von P , die jeweils in einer Halbebene enthalten sind, so dass links von jedem eine Ordnungsrelation auf jedem ist; Wir finden das Minimum des linken Teils und das Maximum des rechten Teils und vergleichen sie wie oben beschrieben. Natürlich müssen wir P nicht physisch halbieren , wir können einfach jeden Punkt in P klassifizieren, während wir in einem einzigen Durchgang nach dem Minimum und Maximum suchen.

Python 2, 194 Bytes

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)

Oktave, 82 72 Bytes

d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

Die Idee ist zu prüfen, ob das lineare Programm min {c'x: Ax = b, e'x = 1, x> = 0} eine Lösung hat, wobei e ein Vektor aller Einsen ist, Spalten von A die Koordinaten von sind die Punktwolke und b ist der Testpunkt und c ist beliebig. Mit anderen Worten, wir versuchen, b als eine konvexe Kombination von Spalten von A darzustellen.

Verwenden Sie zum Ausführen des Skripts octave -f script.m <input.dat

R, 207 Bytes

d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Das Skript bezieht seine Eingaben von STDIN, z Rscript script.R < inputFile.

Es generiert alle Dreiecke aus den Nletzten Punkten (der letzten Linie apply(combn(...) und prüft mit der tFunktion , ob sich der erste Punkt im Dreieck befindet .

tverwendet die Bereichsmethode, um zu entscheiden, ob Uin ABC: (Schreiben (ABC)für den Bereich von ABC) Uin ABCiff (ABC) == (ABU) + (ACU) + (BCU). Außerdem werden Flächen nach der Determinantenformel berechnet (siehe hier für eine schöne Demo von Wolfram).

Ich vermute, dass diese Lösung anfälliger für numerische Fehler ist als meine andere, aber sie funktioniert in meinen Testfällen.

R 282 Bytes

d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Das Skript bezieht seine Eingaben von STDIN, z Rscript script.R < inputFile.

Es generiert alle Dreiecke aus den Nletzten Punkten (der letzten Linie apply(combn(...) und prüft mit der tFunktion , ob sich der erste Punkt im Dreieck befindet .

tverwendet die baryzentrische Methode, um zu entscheiden, ob Uin ABC: (Schreiben XYfür den Xto- YVektor), da dies (AB,AC)eine Basis für die Ebene ist (mit Ausnahme der entarteten Fälle, in denen A, B, C ausgerichtet sind), AUals AU = u.AB + v.ACund Uim Dreieck iff geschrieben werden kann u > 0 && v > 0 && u+v < 1. Siehe zum Beispiel hier für eine detailliertere Erklärung und eine schöne interaktive Grafik. NB: Um ein paar Zeichen zu speichern und DIV0-Fehler zu vermeiden, berechnen wir nur eine Verknüpfung zu uund vund einen modifizierten Test ( min(u*k,v*k,k-u-v)>0).

Die einzigen mathematischen Operatoren verwendet werden +, -, *, min()>0.