Wie Sascha in einem Kommentar geantwortet hat, ist es unmöglich, Ihnen zu helfen, knifflige Testfälle zu generieren oder zu wissen, ob das möglich ist, ohne zu wissen, wie Sie den Algorithmus implementiert haben.
Der Algorithmus selbst hat sich natürlich als richtig erwiesen und das Problem zu lösen. Es geht also nur darum zu testen, ob Ihre Implementierung das tut, was der Algorithmus sagt.
Ich würde vorschlagen, versuchen Sie sich Ihre Implementierung zu beweisen - beweisen Sie, dass Sie den richtigen Punkt als Ausgangspunkt erhalten, beweisen Sie, warum die Berechnungen, die Sie für das Sortieren tun geben die richtige Sortierreihenfolge nach Winkel, beweisen, dass die Berechnungen auf Auf der Grundlage der Entscheidung, einen Punkt zu löschen oder fortzufahren, wird die Frage der Rechts- oder Linksabbiegung gleichgesetzt (oder direkt herausgefunden) und es wird bewiesen, dass jeder Schritt des Algorithmus in Ihrer Implementierung ausgeführt wird. Alle diese Nachweise können zweimal durchgeführt werden - einmal theoretisch und dann mithilfe von Testcodes, die auf die spezifischen Fragen mit Testfällen ausgerichtet sind, die für sie erstellt wurden (zum Beispiel um zu überprüfen, ob die Rechts-/Linksabbieger-Berechnungen ordnungsgemäß durchgeführt wurden) Sie brauchen nicht den Rest des Algorithmus - testen Sie einfach eine Menge von 3-Punkte-Sets mit jeder möglichen Konstellation gegen das bekannte korrekte Ergebnis, um zu testen, ob die von Ihnen verwendete Berechnung die richtige Antwort gibt.
Generieren Sie einfach einige zufällige Testfälle und überprüfen Sie Ihre Lösung. Bei großen Instanzen ist es einfach, zu überprüfen, ob alle Punkte enthalten sind. Um zu überprüfen, ob es sich um eine minimale Hülle handelt, könnten Sie kleine Testfälle generieren und mit einer erschöpfenden Suche vergleichen. Es gibt keine Möglichkeit, harte Instanzen ohne Kenntnis Ihres Algorithmus zu generieren. Sie könnten auch eine Funktion implementieren, die Instanzen generiert, in denen Sie die optimale Lösung kennen (nach Konstruktion). Aber es wird mehr voreingenommen sein. – sascha
Manchmal bricht der Code der konvexen Hülle, wenn Punkte kollinear sind, besonders auf der Hülle selbst. –
Ein Belastungstest besteht darin, dass alle Stellen kollinear sind, entweder auf einer horizontalen/vertikalen oder auf einer schrägen Linie. Auch doppelte Scheitelpunkte. Wenn Sie eine Polarkoordinaten-basierte Implementierung verwendet haben, versuchen Sie Konfigurationen mit Sites, die an der Mitte ausgerichtet sind. –