Punkt in Polygon einfügen [GELÖST]

[Root2k]

Hallo,

ich entwickle momentan ein kleines Zeichenprogramm, welches u.a. eine Bereichsfunktion beinhaltet.
Diese funktioniert wie folgt:

- Der Benutzer klick 3 Mal auf den Zeichenbereich (z.B. an Position A [10 | 10] ; B [20 | 20] ; C [30 | 15])
- Das Programm speichert die Koordinaten (Array) und berechnet daraus eine geschlossene Kurve/Spline mit mehreren Zwischenpunkten (Polygon/Ellipse).

Nachdem das alles erledigt ist, kann der Benutzer weitere Punkte (durch Klicks) einfügen. Das Programm fügt diese dann in die Liste ein und berechnet eine neue Kurve/Spline. Allerdings wird der neue Punkt immer an letzter Stelle eingefügt.
Das ist genau das Problem: Wenn jetzt der Punkt D bei [15 | 15] liegt, berechnet meine Methode eine Kurve über die Punkte mit der Reihenfolge A, B, C, D.
Das ergibt allerdings eine 8:


Hier wäre es aber besser, wenn die Kurve die Reihenfolge A, D, B, C verwenden würde.

Hat von Euch vielleicht jemand eine Idee wie ich mir berechnen lassen kann, wo der Punkt in das Array eingefügt werden soll?
Bin gerade etwas ratlos...

Das ist übrigens der Code für die Berechnung der Kurve (nicht von mir - Autor aber nicht mehr gefunden):

Delphi-Quellcode:

procedure CalcCubicCurve(const points: tArrayOfFixedPoint;
  const steps: cardinal; const closed: boolean; var curve: tArrayOfFixedPoint);

  function CubicPoint(v1, v2, v3, v4: Integer; t: single): Integer;
  begin
    result := Round(v2 + t * ((-v1 + v3) + t * ((2 * v1 - 2 * v2 + v3 - v4) + t
      * (-v1 + v2 - v3 + v4))));
  end;

var
  ni, si, ci, hp, lc: Integer;
  p1, p2, p3, p4: tFixedPoint;
begin
  // writeln (tst, 'Gr32_Ext.CalcCubicCurve: steps=',steps,'  closed=', closed);
  hp := High(points);
  if hp < 1 then
    exit; // ===>
  if closed then
  begin // closed curve ?
    lc := hp + 1;
    p2 := points[hp];
  end
  else
  begin // curve is not closed
    lc := hp;
    p2 := points[0];
  end;
  p3 := points[0];
  p4 := points[1];

  SetLength(curve, lc * Integer(steps) + 1);
  curve[0] := points[0];
  ci := 1;
  for ni := 1 to lc do
  begin
    p1 := p2; // shift curve points
    p2 := p3;
    p3 := p4;
    if closed then
      p4 := points[(ni + 1) mod (hp + 1)]
    else if ni + 1 <= hp then
      p4 := points[ni + 1];

    // calculate interpolation points
    for si := 1 to steps do
    begin
      curve[ci].X := CubicPoint(p1.X, p2.X, p3.X, p4.X, si / steps);
      curve[ci].Y := CubicPoint(p1.Y, p2.Y, p3.Y, p4.Y, si / steps);
      // writeln (tst, ci:3, curve[ci].x shr 16 :7, curve[ci].y div 65536:7);
      inc(ci);
    end;
  end;
end;

[Bummi]

Es wird schwierig sein für das Programm zu beurteilen was genau der Benutzer jetzt meinen könnte, ich habe derartige Sachen gelöst indem ich bei z.B. gedrückter Schifttaste die Haltepunkte als kleine Rechtecke mit darstelle, bei Mausklick werden die jeweils letzen beiden angeklickten markiert, jetzt eine Option (zb: Strg gedrückt) und ein erneuter Mausklick und der Punkt wird zwischen die anderen Punkte eingefügt.

[Medium]

Der einfache Weg:
Ermittle die 2 benachbarten bestehenden Kontrollpunkte, deren addierter Abstand zum Cursor am kleinsten ist, und füge zwischen diesen ein.

Der bessere Weg:
Berechne den Abstand vom Cursor zu allen Strecken, die man zwischen benachbarte Kontrollpunkte ziehen könnte. Die Punkte der Strecke mit dem geringsten Abstand sind deine Kandidaten.

Der korrekte Weg:
Berechne den Abstand der Splines zwischen allen Punktpaaren zum Cursor, und dann weiter wie beim besseren Weg. Problem: Punkt-Spline-Abstände sind nicht ganz so trivial.

Der einfache korrekte Weg:
Puffer alle Punkte, die zum Zeichnen der Splines berechnet werden in einer Liste, und füge ihnen einen Index hinzu, zu welchem Punktepaar sie jeweils gehören. (Geht trivial aus der Zeichenroutine hervor.) Suche aus diesen den dem Cursor am nächsten liegenden, und dessen Index gibt dir die 2 Kandidaten an Kontrollpunkten. Der Tradeoff: Die komplizierte Berechnung wird durch eine LUT bereits berechneter Splinepunkte ersetzt, der Verlust an Genauigkeit ist meist kaum merkbar, da diese zum Zeichnen meist schon in ausreichend genauer Auflösung erzeugt sind. Dafür braucht's aber etwas mehr Speicher, und die paarweise Abstandsberechnung kann langsamer werden als die Spline-Punkt-Abstandsrechnung - je nach deren Implementierung, Anzahl der Kontrollpunkte und Anzahl der Zeichenpunkte.
Ein Vorteil: Der verwendete Splinetyp ist für die Abstandsberechnung nicht mehr wichtig. Geht mit allen.

Gerade wenn man sehr "ausstülpende" Kurven berüksichtigen will, kommt man um einen der letzten 2 Wege kaum herum. Bei beiden lässt sich zudem approximieren, wo der neue Kontrollpunkt (koordinatenmäßig) einzufügen wäre, um auf der bestehenden Kurve zu landen (ggf. wünschenswert).

Es ist ggf. auch sinnvoll einen maximalen minimalen Abstand zu setzen, ab dem tatsächlich ein neuer Punkt eingefügt wird. (Lies: Wenn man zu weit weg von "irgendwo am Rand" der Kurve klickt, dann kein neuer Punkt, weil potenziell nicht offensichtlich wo der dann landen würde.)

[Root2k]

Danke an euch!

Heute bin ich auf der Roadshow von XE2, aber ich werde das dann gleich mal morgen testen.
Meine Frage ist also ertmal geklärt... jetzt fehlt nur noch die Umsetzung.