Algorithmus, um Zahlen mit Hilfe von Eingabepunkten zu finden

Question

Ich habe gerade mit dem Studenten diskutiert und er hat mir gesagt, er Aufgabe, und ich denke, es ist interessant. Die Aufgabe. Es gibt Datei mit Punkten wie:

Point0: x=1; y=4; 
Point1: x=199; y=45; 
Point2: x=42; y=333; 
Point3: x=444; y=444; 
... 
PointN: x=nnn; y=mmm; 

Sie sollten Polygone finden und sie ziehen. Jedes Polygon als innere meine ich so etwas wie dieses:

--------- 
| ----- | 
| | | | 
| |----| | 
|  | 
|--------| 

Und Frage, was Algorithmus können Sie Rat in diesem Fall zu benutzen? Ich verstehe, dass dies von der Graphentheorie ist, aber Meinung von anderem wollen. Danke.

Answer 1

Idee: Finden Sie die convex hul l aller Punkte. Für alle Punkte, die nicht zum Rumpf gehören, wiederhole den Algorithmus bis keine Punkte mehr übrig sind.

Answer 2

Sie könnten wahrscheinlich eine Distanzmatrix für alle Punkte finden und dann Iterationen tun wie folgt aus:

1. dem größten Abstand für die beiden Punkte
2. Draw Rechteck finden, die den gefundenen Abstand entsprechen
3. diese Punkte aus der Liste entfernen
4. Repeat