Zeichnen wir eine Funktion f (x) = sin (πx) + 0,5 sin (3πx) über die Domäne [-3,3] . Wir können dies als lose Schnur interpretieren, die auf einem Brett liegt. Fahren wir nun n Nägel in die Platine an den Positionen (x ₁ , y ₁ ) bis (x _n , y _n ) , wo x _i ∈ (-3,3) und y _i ∈ [-1,1] sind . Stellen Sie sich vor, am Ende der Saite befinden sich zwei Ösen an den Positionen (-3,0) und (3,0).. Wir können jetzt die Enden der Schnur nehmen und durch die Ösen ziehen, bis die Schnur gespannt ist. Dies verformt unser Diagramm in eine stückweise lineare Funktion.

Einige Bilder könnten helfen. Nehmen Sie 8 Nägel bei (-2,8, -0,7), (-2,5, -0,9), (-1,2, .2), (-0,5, .8), (0,5, .4), (1,2, -0,9). (1,5, -0,6), (1,8, -0,8) . Die folgenden drei Darstellungen zeigen den oben beschriebenen Prozess:

^{Für größere Version: Rechtsklick -> In neuem Tab öffnen}

Und hier ist eine Animation zum Spannen der Saite, falls Sie Schwierigkeiten haben, sie zu visualisieren:

Die Herausforderung

Zeichnen Sie anhand einer Liste von "Nägeln" (die nicht unbedingt sortiert ist) diese Nägel und die gespannte Zeichenfolge, wenn sie von der Form der obigen Funktion ausgeht . F.

Sie können ein Programm oder eine Funktion schreiben und Eingaben über STDIN, ARGV oder Funktionsargument vornehmen. Sie können das Ergebnis entweder auf dem Bildschirm anzeigen oder ein Bild in einer Datei speichern.

Wenn das Ergebnis gerastert wird, muss es mindestens 300 Pixel breit und 100 Pixel hoch sein. Der Koordinatenbereich von (-3, -1.1) bis (3,1.1) muss mindestens 75% der horizontalen und vertikalen Ausdehnung des Bildes abdecken. Die Längenskalen von x und y müssen nicht gleich sein. Sie müssen die Nägel (mindestens 3x3 Pixel) und die Schnur (mindestens 1 Pixel breit) zeigen. Sie können die Achsen einschließen oder nicht.

Sie haben die Wahl zwischen Farben, aber Sie benötigen mindestens zwei unterscheidbare Farben: eine für den Hintergrund und eine für die Nägel und die Schnur (diese können jedoch unterschiedliche Farben haben).

Sie können davon ausgehen, dass alle Nägel mindestens 10 ^-5 Einheiten von f entfernt sind (damit Sie sich keine Gedanken über Gleitkomma-Ungenauigkeiten machen müssen).

Dies ist Codegolf, daher gewinnt die kürzeste Antwort (in Bytes).

Mehr Beispiele

Hier sind zwei weitere (einfachere) Beispiele:

{{-2.5, 1}, {-1.5, -1}, {-0.5, 1}, {0.5, -1}, {1.5, 1}, {2.5, -1}}

(Die Zeichenfolge stimmt mit der x- Achse überein.)

{{-2.7, -0.5}, {-2.3, -0.5}, {-1.7, 0.5}, {-1.3, 0.5}, {-0.7, -0.5}, {-0.3, -0.5}, {0.5, 1}, {1.5, -1}, {2.5, 1}}

Willst du eine weitere Herausforderung?

Hier ist Teil II!

Python + Pycairo, 727 708 608, + PyLab, 383

from pylab import*
def f(N):
 def P(u,w,N):
    T=lambda v,p:(C(v-u,p-u)>0)==(C(w-v,p-v)>0)==(C(u-w,p-w)>0);M=[(i,n)for i,n in enumerate(N)if T(V([n[0],sin(pi*n[0])+sin(3*pi*n[0])/2]),n)]
    if M:i,n=max(M,key=lambda n:C(n[1]-u,w-u)**2);M=P(u,n,N[:i])+[n]+P(n,w,N[i+1:])
    return M
 V=array;C=cross;a=V([3,0]);plot(*zip(*([-a]+P(-a,a,map(V,sorted(N)))+[a])));N and scatter(*zip(*N));show()

Beispiel

f([(-2.8,-0.7),(-2.5,-0.9),(-1.2,0.2),(-0.5,0.8),(0.5,0.4),(1.2,-0.9),(1.5, -0.6),(1.8, -0.8)])

Wie es funktioniert

Nehmen wir an, wir wissen, dass die gespannte Saite zwei Punkte A und B durchläuft (wir können immer mit
A = (-3, 0) und B = (3, 0) beginnen ) der kürzest mögliche Weg zwischen A und B , also im Idealfall das Segment AB . Befinden sich jedoch Nägel in dem von der Funktion begrenzten Bereich ( sin πx + ... ) und AB , muss mindestens einer von ihnen die Zeichenfolge blockieren. Insbesondere müssen die Nägel, die in dem genannten Bereich am weitesten von AB entfernt sind, die Saite blockieren. Wenn also C dieser Nagel ist, wissen wir, dass die gespannte Saite durchgehen mussC , zusätzlich zu A und B . Wir können nun den Vorgang für die Segmente AC und CB wiederholen und auf diese Weise fortfahren, bis schließlich keine dazwischenliegenden Nägel mehr vorhanden sind.

Dies ist ein binärer Divide-and-Conquer-Algorithmus mit einer linearen Abtastung in jedem Schritt, so dass er eine Best-Case-Komplexität von O (n log n) und eine Worst-Case-Komplexität von O (n ² ) aufweist .

Python + Pylab, 576 Bytes

Algorithmus:

Ich habe das Problem so interpretiert, dass der kürzeste Weg von (-3, 0) nach (3, 0) gefunden wurde , sodass ein vertikales Liniensegment, das einen Punkt auf dem Weg mit einem Punkt auf f (x) verbindet, niemals einen Nagel kreuzt. Finden Sie

an jedem x , an dem mindestens ein Nagel vorhanden ist, die kleinste Obergrenze und die größte Untergrenze, die durch die Nägel an diesem x gegeben sind . Betrachten Sie die durch diese Grenzen gegebenen Punkte sowie den Start- und den Endpunkt als Eckpunkte in einem Diagramm. Fügen Sie eine Kante mit dem Gewicht hinzu, das durch den euklidischen Abstand zwischen zwei Scheitelpunkten gegeben ist, wenn das Liniensegment zwischen ihnen für jede dazwischen liegende x-Koordinate innerhalb der oberen und unteren Grenze liegt. Finden Sie den kürzesten Weg in diesem Diagramm.

Beispiel mit 27 zufälligen Punkten:

(-0.367534, -0.722751), (-0.710649, -0.701412), (1.593101, -0.484983), (1.771199, 0.681435), (-1.878764, -0.491436), (-0.061414, 0.628570), (-0.326483, -0.512950), (0.877878, 0.858527), (1.256189, -0.300032), (1.528120, -0.606809), (-1.343850, -0.497832), (1.078216, 0.232089), (0.930588, -0.053422), (-2.024330, -0.296681), (-2.286014, 0.661657), (-0.009816, 0.170528), (2.758464, 0.099447), (-0.957686, 0.834387), (0.511607, -0.428322), (-1.657128, 0.514400), (1.507602, 0.507458), (-1.469429, -0.239108), (0.035742, 0.135643), (1.194460, -0.848291), (2.345420, -0.892100), (2.755749, 0.061595), (0.283293, 0.558334), 

Golf gespielt

Was als mehrere Einrückungsbereiche in der for j in R(i&~1)Schleife erscheint, sollte eigentlich ein Tabulator sein.

from pylab import*
P=((3,0),(-3,0))+input()
X=sorted(set(zip(*P)[0]))
l=len(X)*2
if l>4:scatter(*zip(*P[2:]))
f=lambda x:sin(pi*x)+sin(3*pi*x)/2
B=[[max([-9]+[p[1]for p in P if x==p[0]and p[1]<f(x)]),min([9]+[p[1]for p in P if x==p[0]and p[1]>f(x)])]for x in X]
b=zeros(l);b[2:]=inf
v=list(b)
R=range
for i in R(l):
 for j in R(i&~1):
    A=B[j/2][j&1];D,d=B[i/2][i&1]-A,X[i/2]-X[j/2];K=1;c=b[j]+norm((d,D))
    for k in R(j/2+1,i/2):C=A+D/d*(X[k]-X[j/2]);K&=C<B[k][1];K&=C>B[k][0]
    if(c<b[i])&K:b[i]=c;v[i]=j,(X[j/2],A)
l-=2
s=P[:1]
while l/2:l,p=v[l];s+=(p,)
plot(*zip(*s))
show()

Ungolfed

from pylab import*
P = input()
Xn,Yn = zip(*P)
X = set(Xn+(3,-3))
f = lambda x:sin(pi*x)+sin(3*pi*x)/2
ylb = {x: max([-9]+[p[1] for p in P if p[0] == x and p[1] < f(x)]) for x in X}
yub = {x: min([9]+[p[1] for p in P if p[0] == x and p[1] > f(x)]) for x in X}
ylb[-3] = yub[3] = ylb[3] = 0
X = sorted(X)
l = len(X)
best = zeros((l,2))
best[1:] = inf
prev = [ [0,0] for i in range(l) ]
for i in range(l): # calculate min path to X[i] lb or ub
  for ib in 0,1:
    for j in range(i): # point to come from
      for jb in 0,1:
          Y2, Y1 = (ylb, yub)[ib][X[i]], (ylb, yub)[jb][X[j]]
          dy,dx = Y2 - Y1, X[i] - X[j]
          if all([Y1 + dy/dx*(x - X[j]) < yub[x] and Y1 + dy/dx*(x - X[j]) > ylb[x] for x in X[j+1:i]]):
             c = best[j][jb] + (dy**2+dx**2)**.5
             if c < best[i][ib]:
                 best[i][ib] = c
                 prev[i][ib] = j, jb, (X[j], Y1)
j, jb = l-1,0
pts = [(3,0)]
while j:
    j, jb, p = prev[j][jb]
    pts += [p]
plot(*zip(*pts))
scatter(Xn,Yn)
show()