[C#] Graham scan - problem kolinearnosti

Pozdravljeni,

sprogramiral sem graham scan algoritem za iskanje konveksne lupine, ki deluje ok, dokler točke trikotnika niso kolinearne, se pravi kadar je ccw == 0 (to se ponavadi zgodi pri večjem številu točk) :

primer(300 točk) : Klik za sliko
primer(5000 točk) : Klik za sliko

graham :

// graham scan
                for (int i = 2; i < points.Count; i++)
                {
                    while (ccw(points[M - 1], points[M], points[i]) > 0)
                    {
                        if (M > 1)
                        {
                            points.RemoveAt(M);
                            M -= 1;
                            i--;
                        }
                        else if (i == points.Count - 1)
                        {
                            break;
                        }
                            
                        else
                        {
                            i += 1;
                        }
                    }
                    
                    //listBoxInfos.Items.Add("g" + (int)points[M].X + "," + (int)points[M].Y + "," + 0);
                    //listBoxInfos.Items.Add("ccw" + ccwTest);
                    M += 1;

                }

Torej, točke so lahko kolinearne in so del konveksne lupine in lahko so kolinearne in niso del konveksne lupine. Kako obdržati tiste, ki so del konveksne lupine?

nisem gledal kode. Poglej da nimaš kakšnih precision errorjev al česa podobnega z graham scanom (mogoče tudi kak overflow v ccw če maš velike številke)

pikolovsko: ni lupina ampak ovojnica

phyro je 8. avg 2014 ob 10:08 izjavil:

pikolovsko: ni lupina ampak ovojnica

V knjigi iz katere sem se učil na faksu piše lupina

epicVoid je 8. avg 2014 ob 10:10 izjavil:

Hvala za odgovor, vendar ne razumem točno kaj misliš. Kot naj bi izračunal samo glede na extrem(najvčji/najmanjši X ali Y) in sortiral točke glede na kot. Če je kot == 0 je točka del konveksne ovojnice in se ne sme odstranit (če prav razumem).

Najprej najdeš "ekstrem" v eno smer (npr po X). Recimo da je to točka E. Izračunaš kot za vse točke glede na točko E. Točke sortiraš glede na kot in potem glede na razdaljo od E. Potem pa se "sprehodiš" po seznamu in za 3 točke izračunaš kot, če je ta >=0 srednjo točko odstraniš. Če točko odstraniš se pomakneš za 1 nazaj. Če točke ne odstraniš se pomakneš naprej.

Sam lahko izbiraš ali je točka del lupine ko je kot 0, ne sme to vplivat na izračun.

http://www.codeotaku.com/projects/jquer...