Łączenie punktów

Po pierwsze dzieńdobry :P

Więc mam taki problem : w układzie współrzednych jest n punktów i chce je połączyć w JEDEN wielokąt. Linie nie mogą się przecinać.

Na maksa nie wiem jak to zrobić ;) nie wiem jak wybierać dla punktów inne punkty, z którymi one się połączą tak, aby te wszystkie linie się nie przecinały i wyszedł jeden ładny wielokąt ;) Troche to zamotałem ;)

Z góry dziekuję za odpowiedzi i pozdrawiam

Korzystajac z algorytmu na znajdowanie otoczki wypuklej, ja bym to zrobil tak:

1. Znalezc otoczke wypukła podanych punktow
2. Znalezc otoczke wypukla pozostalych, itd...
3. "Otworzyc? ta co jest najglebiej i wlaczyc ja do tej, w ktorej się znajdowala. Ja bym to robil tak: jesli jeden punkt lub dwa to wystarczy je gdzies wpiac do tej nadrzednej, jeśli trzy lub wiecej to wybrac sobie z tej otoczki polaczona pare punktow (A i B) i rozlaczyc, znalezc punkt najblizszy (C) punktowi A w otoczce wyzej i go z nim polaczyc, punkt B polaczyc z blizszym (D) polaczonym z C i rozlaczyc C z D
4. "Otworzyc? nowo powstala otoczke (tylko nie rozdzielac tych punktow, które nalezaly do tej wewnetrznej) i tak az do pierwszej otoczki.
   Mysle, ze powinno dzialac, ale glowy nie daje ;)
   Do tego jeszcze "rysunek":

Mamy np. takie punkty

*            *
              
     *    *    
                
       *         *
  *          *   
     *  *        
         
     *    *      *
               
              
*             * 

Po znalezienu otoczek cos takiego:
*------------*
|             \
|    *----*    \
|   /      \    \
|  /   *    \    *
| *   / |    *   |
|  \ *--*   /    |
|   \      /     |
|    *----*      *
|               /
|              /
*-------------*

Nastepnie:
*------------*
|             \
|    *----*    \
|   /      \    \
|  /   *    \    *
| *   / |    *   |
|  \ *  *   /    |
|   \|   \ /     |
|    *    *      *
|               /
|              /
*-------------*

I otrzymujemy:

*------------*
|          /  
|    *----*    
|   /           
|  /   *      ---*
| *   / |    *   |
|  \ *  *   /    |
|   \|   \ /     |
|    *    *      *
|               /
|              /
*-------------*