Golf der kleinste Kreis!

29

Das Problem:

Suchen Sie bei einer nicht leeren Menge von Punkten in der kartesischen Ebene den kleinsten Kreis, der sie alle einschließt ( Wikipedia-Link ).

Dieses Problem ist trivial, wenn die Anzahl der Punkte drei oder weniger beträgt (wenn es einen Punkt gibt, hat der Kreis einen Radius von Null; wenn es zwei Punkte gibt, ist das Liniensegment, das die Punkte verbindet, der Durchmesser des Kreises; wenn es solche gibt) Bei drei (nicht-kolinearen) Punkten ist es möglich, die Gleichung eines Kreises zu erhalten, der sie alle berührt, wenn sie ein nicht-stumpfes Dreieck bilden, oder eines Kreises, der nur zwei Punkte berührt und den dritten einschließt, wenn das Dreieck stumpf ist. Aus diesem Grund sollte die Anzahl der Punkte mehr als drei betragen.

Die Herausforderung:

  • Eingabe: Eine Liste von 4 oder mehr nicht-kolinearen Punkten. Die Punkte sollten X- und Y-Koordinaten haben. Koordinaten können Floats sein. Um die Herausforderung zu erleichtern, sollten keine zwei Punkte dieselbe X-Koordinate haben.
    Beispielsweise:[(0,0), (2,1), (5,3), (-1,-1)]
  • Ausgabe: Ein Tupel von Werten, (h,k,r)so dass (xh)2+(yk)2=r2 die Gleichung des kleinsten Kreises ist, der alle Punkte einschließt.

Regeln:

  • Sie können die für Ihr Programm geeignete Eingabemethode auswählen.
  • Die Ausgabe sollte auf STDOUTeine Funktion gedruckt oder von dieser zurückgegeben werden.
  • "Normale" Mehrzwecksprachen werden bevorzugt, es ist jedoch jede andere Sprache akzeptabel.
  • Sie können davon ausgehen, dass die Punkte nicht kollinear sind.
  • Das ist Code-Golf, also gewinnt das kleinste Programm in Bytes. Der Gewinner wird eine Woche nach dem Absenden der Challenge ermittelt.
    • Bitte geben Sie die von Ihnen verwendete Sprache und die Länge in Bytes als Überschrift in der ersten Zeile Ihrer Antwort an: # Language: n bytes

Testfälle:

  • 1:
    • Eingang: [(-8,0), (3,1), (-6.2,-8), (3,9.5)]
    • Ausgabe: [-1.6, 0.75, 9.89]
  • 2:
    • Eingang: [(7.1,-6.9), (-7,-9), (5,10), (-9.5,-8)]
    • Ausgabe: [-1.73, 0.58, 11.58]
  • 3:
    • Eingang: [(0,0), (1,2), (3,-4), (4,-5), (10,-10)]
    • Ausgabe: [5.5, -4, 7.5]
  • 4:
    • Eingang: [(6,6), (-6,7), (-7,-6), (6,-8)]
    • Ausgabe: [0, -0.5, 9.60]

Viel Spaß beim Golfen !!!


Verwandte Herausforderung:

Barranka
quelle
8
"Wenn es drei (nicht kolineare) Punkte gibt, ist es möglich, die Gleichung eines Kreises zu erhalten, der sie alle berührt" - aber das ist möglicherweise nicht der kleinste umschließende Kreis. Für die drei Eckpunkte eines stumpfen Dreiecks ist der kleinste umschließende Kreis derjenige, dessen Durchmesser die längste Seite ist.
Anders Kaseorg
2
@Arnauld Genau wie du. Für Testfall 2 erhalte ich die Mitte (-1,73, 0,58) und für Testfall 3 (5,5, -4).
Robin Ryder
@ Arnauld vielen Dank für Ihren Kommentar. Ich habe den Beitrag entsprechend bearbeitet
Barranka
@Arnauld Ups, Entschuldigung. Tatsächlich. Aldo, korrigiert mit Ihren Beobachtungen
Barranka

Antworten:

26

Wolfram Language (Mathematica) , 28 27 Bytes

#~BoundingRegion~"MinDisk"&

Probieren Sie es online!

Eingebaute sind hier praktisch. Die Ausgabe ist ein Plattenobjekt mit Mittelpunkt und Radius. Wie bei anderen habe ich festgestellt, dass sich der 2. und 3. Testfall von der Frage unterscheiden.

Vielen Dank an @lirtosiast für das Speichern eines Bytes!

Wenn eine Liste als Ausgabe erforderlich ist, kann dies in 35 Bytes (auf Kosten von zusätzlichen 8 Bytes) erfolgen . Vielen Dank an @Roman für den Hinweis.

Nick Kennedy
quelle
3
Ich hatte ein eingebautes Mathematica erwartet. Aber ich hatte nicht erwartet, dass Mathematica "Plattenobjekte" hat.
Robin Ryder
36 Bytes , um das Ausgabeformat richtig zu machen:Append@@BoundingRegion[#,"MinDisk"]&
Roman
20

JavaScript (ES6),  298 ... 243  242 Byte

Gibt ein Array zurück [x, y, r] .

p=>p.map(m=([c,C])=>p.map(([b,B])=>p.map(([a,A])=>p.some(([x,y])=>H(x-X,y-Y)>r,F=s=>Y=(d?((a*a+A*A-q)*j+(b*b+B*B-q)*k)/d:s)/2,d=c*(A-B)+a*(j=B-C)+b*(k=C-A),r=H(a-F(a+b),A-F(A+B,X=Y,j=c-b,k=a-c)))|r>m?0:o=[X,Y,m=r]),q=c*c+C*C),H=Math.hypot)&&o

Probieren Sie es online!

oder sehen Sie eine formatierte Version

Wie?

Methode

Für jedes Paar von Punkten (EIN,B) erzeugen wir den Kreis (X,Y.,r) , deren Durchmesser EINB .

X=EINx+Bx2,Y.=EINy+By2,r=(EINx-Bx2)2+(EINy-By2)2

Für jedes Tripel verschiedener Punkte (A,B,C) erzeugen wir den Kreis (X,Y,r) der das Dreieck ABC umschreibt .

d=Ax(ByCy)+Bx(CyAy)+Cx(AyBy)
X=(Ax2+Ay2)(ByCy)+(Bx2+By2)(CyAy)+(Cx2+Cy2)(AyBy)2d
Y=(Ax2+Ay2)(CxBx)+(Bx2+By2)(AxCx)+(Cx2+Cy2)(BxAx)2d
r=(XAx)2+(YAy)2

Für jeden erzeugten Kreis testen wir, ob jeder Punkt (x,y) darin eingeschlossen ist:

(x-X)2+(y-Y.)2r

Und wir geben schließlich den kleinsten gültigen Kreis zurück.

Implementierung

(X,Y.)d0q=Cx2+Cy2

X=(EINx2+EINy2-q)(By-Cy)+(Bx2+By2-q)(Cy-EINy)2d
Y.=(EINx2+EINy2-q)(Cx-Bx)+(Bx2+By2-q)(EINx-Cx)2d

F(j,k)

  • (By-Cy,Cy-EINy)X
  • (Cx-Bx,EINx-Cx)Y.

Der dritte Parameter in Fs(X,Y.)d=0

Arnauld
quelle
Vielleicht ist das Schreiben eines numerischen Optimierers vom Newton-Typ kürzer ...
qwr
Haben Sie einen Richtigkeitsnachweis? Ich kann sehen, dass dies ein plausibler Ansatz ist, aber mehr als das scheint ziemlich viel Arbeit zu erfordern.
Peter Taylor
3
@PeterTaylor Der Algorithmus wird in Wikipedia erwähnt: Ein naiver Algorithmus löst das Problem in der Zeit O (n ^ 4), indem er die Kreise testet, die von allen Paaren und Dreifachen von Punkten bestimmt werden . Aber leider gibt es keine Verbindung zu einem Beweis.
Arnauld
Wird es ein Präzisionsproblem geben, das es nicht löst?
14 m²,
1
@Arnauld Wenn Sie einige seltsame Zahlen benötigen, um zu erreichen, kann ich sagen, dass das in Ordnung ist; Wenn es in einer einfachen Situation sogar scheitern sollte, könnte dies ein Problem sein
am
14

R , 59 Bytes

function(x)nlm(function(y)max(Mod(x-y%*%c(1,1i))),0:1)[1:2]

Probieren Sie es online!

Übernimmt die Eingabe als Vektor komplexer Koordinaten. Modist der Abstand (Modul) in der komplexen Ebene und nlmist eine Optimierungsfunktion: Sie ermittelt die Position des Zentrums (Ausgabe als estimate), die den maximalen Abstand zu den Eingabepunkten minimiert, und gibt den entsprechenden Abstand (Ausgabe als) anminimum ) an, dh den Radius . Genaue 3-6 Ziffern; Die TIO-Fußzeile rundet die Ausgabe auf zwei Ziffern.

nlmVerwendet einen numerischen Vektor als Eingabe: Das y%*%c(1,1i)Unternehmen wandelt ihn in einen Komplex um.

Robin Ryder
quelle
9

Jelly , 100 98 Bytes

_²§½
1ịṭƊZIṚṙ€1N1¦,@ṭ@²§$µḢZḢ×Ø1œị$SḤ÷@P§
ZṀ+ṂHƲ€_@Ç+ḷʋ⁸,_²§½ʋḢ¥¥
œc3Ç€;ŒcZÆm,Hñ/$Ʋ€$ñ_ƭƒⱮṀ¥Ðḟ⁸ṚÞḢ

Probieren Sie es online!

Im Gegensatz zu meiner Wolfram-Antwortsprache benötigt Jelly ziemlich viel Code, um dies zu erreichen (es sei denn, ich vermisse etwas!). Dieses vollständige Programm verwendet die Liste der Punkte als Argument und gibt den Mittelpunkt und den Radius des kleinsten umschließenden Kreises zurück. Es werden für alle Sätze von drei Punkten Umkreiskreise und für alle Sätze von zwei Punkten Durchmesser generiert. Dabei werden alle Punkte überprüft und derjenige mit dem kleinsten Radius ausgewählt.

Code für das make_circumcircle-Bit wurde von Code auf dieser Site inspiriert, der wiederum von Wikipedia inspiriert wurde.

Nick Kennedy
quelle
1
Ich verstehe diesen Code nicht, aber anstelle von Durchmessern und Kreisen können Sie alle Sätze von drei Punkten mit Duplikaten generieren und die Listen von drei identischen Punkten herausfiltern?
Lirtosiast
2

APL (NARS), 348 Zeichen, 696 Byte

f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}
c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}
p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}
s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}
s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}
s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}
s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}

Dies ist eine 'Implementierung' von Formeln in der Arnauld-Lösung ... Ergebnisse und Kommentare:

  s1 (¯8 0)(3 1)(¯6.2 ¯8)(3 9.5)
¯1.6 0.75  9.885469134 
  s1 (7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
¯1.732305109 0.5829680042  11.57602798 
  s1 (0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
5.5 ¯4  7.5 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)
0 ¯0.5  9.604686356 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(0 0)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)
2 ¯1.5  11.67261753 
  s1 (6 6)(¯6 7)(¯7 ¯6)(6 ¯8)(1 2)(3 ¯4)(4 ¯5)(10 ¯10)(7.1 ¯6.9)(¯7 ¯9)(5 10)(¯9.5 ¯8)
1.006578947 ¯1.623355263  12.29023186 
  s1 (1 1)(2 2)(3 3)(4 4)
2.5 2.5  2.121320344 
  ⎕fmt s3 (1 1)(2 2)(3 3)(4 4)
┌0─┐
│ 0│
└~─┘

f: Findet die Kombination von Alpha-Ojets im Omega-Set

f←{h←{0=k←⍺-1:,¨⍵⋄(k<0)∨k≥i←≢w←⍵:⍬⋄↑,/{w[⍵],¨k h w[(⍳i)∼⍳⍵]}¨⍳i-k}⋄1≥≡⍵:⍺h⍵⋄⍺h⊂¨⍵}

((X, Y), r) repräsentieren ab jetzt einen Kreisumfang von Radius r und Mittelpunkt in (XY).

c: Findet, ob der Punkt in ⍺ innerhalb des Umfangs ((XY) r) in ⍵ liegt (Ergebnis <= 0) oder extern ist (Ergebnis> 0). Wenn der Umfang in ⍵ eingegeben wird, ist er ⍬ als Eingabe würde 1 (außerhalb des Umfangs) für jede mögliche Eingabe in ⍺ zurückgeben.

c←{⍵≡⍬:1⋄(x r)←⍵⋄(-r*2)++/2*⍨⍺-x}

p: wenn ⍵ ein Array von ((XY) r) ist; für jedes der ((XY) r) in ⍵ schreibe 1, wenn alle Punkte im Array ⍺ intern zu ((XY) r) sind, sonst schreibe 0 NB Hier ist etwas, das nicht geht, weil ich auf epsilon = 1e ¯ runden musste 13. in Grenzfällen von Punkten in der Ebene (und wahrscheinlich absichtlich gebaut) ist es nicht zu 100% lösungsversichert

p←{(b k)←⍺ ⍵⋄∧/¨1e¯13≥{{⍵{⍵c⍺}¨b}k[⍵]}¨⍳≢k}

s2: von 2-Punkt in ⍵ wird der Umfang in dem Format ((XY) r) zurückgegeben, das in diesen 2 Punkten den Durchmesser hat

s2←{(+/k),√+/↑2*⍨-/k←2÷⍨⍵}

s3: von 3 Punkten gibt es den Umfang in dem Format ((XY) r) zurück, das durch diese drei Punkte verläuft. Wenn es Probleme gibt (zum Beispiel Punkte sind ausgerichtet), würde es fehlschlagen und ⍬ zurückgeben.

s3←{0=d←2×-.×m←⊃{⍵,1}¨⍵:⍬⋄m[;1]←{+/2*⍨⍵}¨⍵⋄x←d÷⍨-.×m⋄m[;2]←{1⊃⍵}¨⍵⋄y←d÷⍨--.×m⋄(⊂x y),√+/2*⍨(x y)-1⊃⍵}

beachte, dass -. × die Determinante einer Matrix nxn und

  ⎕fmt ⊃{⍵,1}¨(¯8 0)(3 1)(¯6.2 ¯8)
┌3─────────┐     
3 ¯8    0 1│     |ax  ay 1|
│  3    1 1│   d=|bx  by 1|=ax(by-cy)-bx(ay-cy)+cx(ay-by)=ax(by-cy)+bx(cy-ay)+cx(ay-by)
│ ¯6.2 ¯8 1│     |cx  cy 1|
└~─────────┘

s: Ermittelt aus n Punkten in ⍵ die Typumfänge der von s2 gefundenen oder der vom Typ s3, die alle n Punkte enthalten.

s←{v/⍨⍵p v←(s2¨2 f⍵)∪s3¨3 f⍵}

s1: berechnet aus der Menge aus dem obigen s diejenigen mit minimalem Radius und gibt die erste mit minimalem Radius zurück. Die drei Zahlen als Arrays (die erste und die zweite Koordinate sind die Koordinaten des Zentrums, während die dritte der Radius des gefundenen Umfangs ist).

s1←{↑v/⍨sn=⌊/sn←{2⊃⍵}¨v←s⍵}
RosLuP
quelle
2

Python 2 (PyPy) , 244 242 Bytes

P={complex(*p)for p in input()}
Z=9e999,
for p in P:
 for q in{p}^P:
	for r in{p}^P:R,S=1j*(p-q),q-r;C=S.imag and S.real/S.imag-1jor 1;c=(p+q-(S and(C*(p-r)).real/(C*R).real*R))/2;Z=min(Z,(max(abs(c-t)for t in P),c.imag,c.real))
print Z[::-1]

Probieren Sie es online!

Hierbei wird der Brute-Force-O (n ^ 4) -Algorithmus verwendet, der jedes Punktpaar und -dreieck durchläuft, den Mittelpunkt berechnet und den Mittelpunkt beibehält, der den kleinsten Radius benötigt, um alle Punkte einzuschließen. Der Umfang von 3 Punkten wird berechnet, indem der Schnittpunkt von zwei senkrechten Winkelhalbierenden ermittelt wird (oder wenn zwei Punkte gleich sind, wird der Mittelpunkt mit dem dritten Punkt verwendet).

Vash3r
quelle
Willkommen bei PPCG! Da Sie Python 2 verwenden, können Sie 1 Byte sparen, indem Sie die beiden Leerzeichen in der 5. Zeile in einen Tabulator konvertieren.
Stephen
P={x+y*1j for x,y in input()}Spart auch 2 Bytes.
Mr. Xcoder
1

Python 212 190 Bytes

Diese Lösung ist falsch, und ich muss jetzt arbeiten, damit ich keine Zeit habe, sie zu beheben.

a=eval(input())
b=lambda a,b: ((a[0]-b[0])**2+(a[1]-b[1])**2)**.5
c=0
d=1
for e in a:
    for f in a:
        g=b(e,f)
        if g>c:
            c=g
            d=[e,f]
print(((d[0][0]+d[1][0])/2,(d[0][1]+d[1][1])/2,c/2))

Probieren Sie es online!

Ich habe herausgefunden, welche zwei Punkte am weitesten entfernt sind, und dann eine Gleichung für einen Kreis aus diesen Punkten erstellt!

Ich weiß, dass dies nicht die kürzeste in Python ist, aber es ist das Beste, was ich tun kann! Dies ist auch mein erster Versuch, einen dieser Schritte durchzuführen. Bitte haben Sie Verständnis dafür!

Ben Morrison
quelle
2
Hier kann noch etwas mehr golfen werden. Sie können if g>c:\n c=g\n d=[e,f]zum Beispiel auf verkürzen if g>c:c=g;d=[e,f]und so viel Leerzeichen sparen. Ich denke nicht, dass Sie d im Voraus initialisieren müssen, auch wenn Sie zwei Variablen verwenden, und E,F=e,fin Zeile 10 werden Sie printviel kürzer. Ich denke, eine Lösung mit maxund ein Listenverständnis wären sogar kürzer als zwei Schleifen, aber ich könnte mich irren. Leider ist Ihre Lösung jedoch nicht korrekt. Für die Punkte (-1,0), (0,1,41), (0,5, 0), (1,0) berechnet Ihre Lösung einen Kreis um 0 mit Radius 1. Aber der Punkt (1, 1,41) liegt nicht darin Kreis.
Black Owl Kai
Herzlich willkommen! Vielen Dank für Ihre Antwort. Wie im obigen Kommentar erwähnt, ist Ihre Lösung nicht korrekt. Ein Hinweis für eine Brute-Force-Lösung: Der kleinstmögliche Kreis berührt entweder zwei oder drei Punkte. Sie können die Gleichung für den Kreis berechnen, der jedes Punktepaar berührt, und prüfen, ob es einen Kreis gibt, der alle Punkte einschließt. Berechnen Sie dann die Gleichung für den Kreis, der jedes Punkttripel berührt, und prüfen Sie, ob es einen Kreis gibt, der alle Punkte einschließt. Sobald Sie alle möglichen Kreise erhalten haben, wählen Sie den mit dem kleinsten Radius aus.
Barranka
1
Okay, ich werde versuchen, es zum Laufen zu bringen, und dann werde ich die Antwort aktualisieren. Ich muss herausfinden, wie ich überprüfen kann, ob ein Punkt in einem Kreis enthalten ist.
Ben Morrison
Wenn Sie Mittelpunkt und Radius des Kreises haben, prüfen Sie, ob der Abstand zwischen Mittelpunkt und jedem Punkt kleiner oder gleich dem Radius ist. Wenn diese Bedingung für alle Punkte erfüllt ist, ist dieser Kreis ein Kandidat
Barranka