» »

[C#] Graham scan - problem kolinearnosti

[C#] Graham scan - problem kolinearnosti

epicVoid ::

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?

AnriK ::

Sem šel pregledat mojo kodo za isto nalogo, sam se odstranjeval točke kjer je bil kot enak >= 0.
So se pa take slike pojavljale če si odstranjeval napačno točko.

phyro ::

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 :D

epicVoid ::

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).

Zgodovina sprememb…

  • spremenilo: epicVoid ()

AnriK ::

phyro je izjavil:


pikolovsko: ni lupina ampak ovojnica :D


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

epicVoid je 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.

amacar ::

Js imam tak. Očitno točke samo zamenjam, namesto da jih brišem, ker imam polje, v seznamu1 do m so pa potem taprave točke.

for (int i = 2; i < n+1; i++)
            {
                while (orientacija(seznam1[m - 1], seznam1[m], seznam1[i]) <= 0)
                {
                    if (m > 1)
                        m--;
                    else if (i == n)
                        break;
                    else
                        i++;
                }
                m++;
                tocka bla = seznam1[i];
                seznam1[i] = seznam1[m];
                seznam1[m] = bla;
            }

krneki0001 ::

Asrock X99 Extreme 4 | Intel E5-2683V4 ES | 64GB DDR4 2400MHz ECC |
Samsung 250GB M.2 | Asus 1070 TI | 850W Antec | LC Tank Buster

AnriK ::

while (x+2 < konv_lupina.Count && x>=0)
{
    //U = (Pi+1-Pi) x (Pi+2-Pi) = (x2-x1)(y3-y1) - (x3-x1)(y2-y1)
    U = (konv_lupina[x+1].X - konv_lupina[x].X) * (konv_lupina[x+2].Y - konv_lupina[x].Y) 
        - (konv_lupina[x+2].X - konv_lupina[x].X) * (konv_lupina[x+1].Y - konv_lupina[x].Y);

    if (U >= 0)
    {
      konv_lupina.RemoveAt(x + 1);
      x--;
    }
    else
       x++;
}


Še moja koda..

Zgodovina sprememb…

  • spremenil: AnriK ()


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Python - pomoč!

Oddelek: Programiranje
7951 (787) lknix
»

Algoritem: Se da ločiti dve množici točk s premico v O(n)?

Oddelek: Programiranje
61199 (965) Rokm
»

[C++] std::sort problem

Oddelek: Programiranje
8819 (819) nejck
»

[C/C++] Konveksna lupina - brute force

Oddelek: Programiranje
71733 (1607) WarpedGone
»

Program v c++

Oddelek: Programiranje
191684 (1353) Bela01

Več podobnih tem