Koordinatareaformeln -algoritm?

Finns det någon algoritm som sorterar punkter ur ett koordinatsystem så dom hamnar medurs?

Jag försöker göra ett program som använder sig av koordinatareaformeln. Problemet ligger i just att datorn ska förstå vilken ordning punkterna ska vara i.

Förslag?

Det går i alla fall inte att i allmänhet bestämma ordningen. Titta till exempel på femhörningen i din länk. Givet punktera så ger ordningen P1-> P2 -> P3 -> P4 -> P5 -> P1 och P1-> P2 -> P3 -> P5 -> P4 -> P1 två olika femhörningar, vars areor för övrigt är olika. Punkternas ordning är alltså inte unikt bestämda av deras koordinater.

Är figuren redan bestämd och punkterna redan bestämda? Nu återstår alltså enbart att "sortera" punkterna så att datorn vet vilken koordinat som svarar mot ett specifikt n i koordinatareaformeln?!

I övrigt så kan jag inte ett jävla skit om detta. Men jag kan la ge lite idéer kanske. Om vi har en enkel polygon så borde det gå att finna en punkt (vi kallar den en enkel mittpunkt) så att man kan dra räta linjer från denna punkt och träffa alla hörnpunkter på polygonen så att ingen av dessa räta linjer skär randen av polygonen.

Se bild
http://i44.tinypic.com/abk1ds.png

Det borde dessutom gå att bevisa att en sådan punkt alltid finns eller inte finns för alla enkla polygoner. Om den finns så är problemet nog inte svårt att lösa. Då är det nog bara att translatera alla punkter så att en enkel mittpunkt ligger i origo och sedan parametisera till planpolära koordinater. Då har man ju vinklarna så att säga. Sedan är det ju för datorn bara att välja nästa vinkel i storleksordning antingen från största till minsta eller vice versa.

Problemet kan ju då vara att hitta den enkla mittpunkten om den ens finns för alla enkla polygoner, men min intuition säger mig att den existerar. Annars kan vi ju lämna som uppgift till alla riktigt grymma matematiker här att bevisa att den finns eller kanske säga att ett sådant bevis redan existerar.

Hur som helst! Om den enkla mittpunkten alltid finns så lär det ju i alla fall gå att finna en brute-force metod för att finna den enkla mittpunkten. Denna algoritm kan man nog utveckla en hel del i form av att leta kring sannolika punkter osv och den kan säkert vara hyffsat svår att skapa, men det är nog inte omöjligt. I vilket fall lär det kräva rätt mycket datorkraft och det är ju alltid riktigt negativt.

Punkten existerar för varje godtycklig punktmängd. I själva verket är (nästan) varje punkt inom punktmängdens konvexa hölje en sådan mittpunkt du beskriver.

Betrakta punktmängen. Välj en punkt p inom det konvexa höljet av denna mängd, som inte ligger på någon förlängning (exklusive direkt mellan) linje mellan två punkter i mängden. För varje punkt q_i i den ursprungliga mängden skapa vektorn p->q_i. Sortera denna vektormängd efter argument och förbind punkterna q_0...q_n i denna ordning. Se exempel, där varje färg ger upphov till en egen cyklisk ordning av punkterna (och därmed olika polygoner).

Här är ett exempel där medelpunkten används som mittpunkt: http://www.shiffman.net/2011/12/23/night-4-sorting-the-vertices-of-a-polygon/

För att gå in på den sekundära diskussionen om den s.k. mittpunkten:
När det gäller en given polygon så existerar det inte alltid en sådan punkt, se exempelvis denna figur

Ett lite mer målande exempel, tänk dig ett rum format som polygonen. Finns det då en punkt i rummet varifrån man kan se alla hörn?

Mängden av alla sådan punkter kallas polygonens kernel, och är lite knivig att räkna ut. Finns en applet och en artikel (läs specifikt om CAB-algoritmen).

De tre senaste styckena är såklart irrelevanta för ursprungsproblemet, eftersom ordningen redan är given om man har polygonen, men är ett litet mer utförligt svar på BengtZz funderingar.

Förutsatt att du vet samtliga punkter samt samtliga bågar går det, annars finns inget entydigt sätt att bestämma en polygon utifrån en punktmängd. Bara beräkna arean båge för båge och sedan ta beloppet av resultatet. Antingen räknar programmet medurs eller moturs, och skillnaden i output är bara tecknet.

Glöm vad jag skrev om CAB-algoritmen, läste inte igenom så bra.

Existerar kerneln så är polygonen star-shaped. Kerneln kan räknas ut i O(N*log N) tid genom att ta skärningen av alla halvplan definierade av polygonens sidor. Finns även en algoritm för att räkna ut det i O(N) tid, men den har jag ingen aning om hur den ser ut. Finns här om du har tillgång.