eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingEliminacja podwójnych wierzchołków = uniq na liście cyklicznej
Ilość wypowiedzi w tym wątku: 9

  • 1. Data: 2014-11-06 16:15:30
    Temat: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: Borneq <b...@a...hidden.pl>

    Jak przepisać jeden wielokąt na inny zamieniając się duplikujące się
    (lub zwielokrotnione) wierzchołki oznaczające krawędzie długości zero?
    Problem wydaje się banalny, oto przelatujemy w pętli listę wierzchołków
    i kopiujemy do drugiej listy tylko gdy się różnią i tylko wtedy
    zwiększamy drugi indeks.
    Ale problemy są:
    - jest to lista cykliczna, musimy usuwać ostatni równy pierwszemu
    - chcę by pierwszy punkt pozostał pierwszym, choć ten warunek jest nie
    taki ważny
    - mogą być całe serie, więcej niż dwa takie same

    Najpierw zliczamy ilość powtórek, to proste i działa dobrze:
    int cntZeroLen = 0;
    for (int i = 0; i < polyIn->n; i++)
    {
    Point P0 = polyIn->pts[i];
    Point P1;
    if (i<polyIn->n - 1)
    P1 = polyIn->pts[i + 1];
    else
    P1 = polyIn->pts[0];
    if (P0.x==P1.x && P0.y==P1.y)
    cntZeroLen++;
    }
    To potrzebne do zaalokowania miejsca w drugim
    tmpPoly.SetSize(polyIn->n - cntZeroLen);

    Komplikuje się przepisywanie:
    if (polyIn->n>=1) tmpPoly.pts[0] = polyIn->pts[0];
    int ii=1;
    for (int i = 1; i < polyIn->n; i++)
    {
    Point prevp = polyIn->pts[i-1];
    Point p = polyIn->pts[i];
    if (i<polyIn->n-1)
    {
    if (prevp.x!=p.x || prevp.y!=p.y)
    {
    tmpPoly.pts[ii] = polyIn->pts[i];
    ii++;
    }
    }
    else
    {
    Point firstP = polyIn->pts[0];
    if ((prevp.x!=p.x || prevp.y!=p.y)
    && (firstP.x!=p.x || firstP.y!=p.y))
    {
    tmpPoly.pts[ii] = polyIn->pts[i];
    ii++;
    }
    }
    }
    Najpierw osobno obrabiam punkt zerowy, potem inaczej zwykłe a inaczej
    ostatni, ale to i tak nie działa gdy na końcu mamy więcej niż dwa jednakowe.
    Przykład: nie działało dla:
    n=77
    [0]=[1]
    [72]=[73]
    [75]=[76]
    [76]=[0]
    czyli cała czwórka [75]=[76]=[0]=[1]
    W pętli mieliśmy
    tmp[1]:=in[2]
    tmp[2]:=in[3]
    tmp[3]:=in[4]
    ......
    tmp[69]:=in[70]
    tmp[70]:=in[71]
    tmp[71]:=in[72]
    tmp[72]:=in[74]
    tmp[73]:=in[75]
    Jak widać, źle jest dla tmp[73]:=in[75], bo in[75]=in[0]
    A może jakoś cyklicznie usuwać też zerowy?
    Problem trudniejszy niż działanie procedury uniq, która usuwa duplikaty
    bo mamy listę cykliczną



  • 2. Data: 2014-11-06 16:26:01
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-11-06 o 16:15, Borneq pisze:
    > Jak przepisać jeden wielokąt na inny zamieniając się duplikujące się

    Zwykły uniq:
    ListUniq:={}
    for i:=0 to List.Count-1 do
    if (i=0) or (List[i]<>prevElem) then
    begin
    prevS:=List[i];
    ListUniq.Add(prevS);
    end;

    bardzo prosto z wykorzystaniem prevElem - poprzedniej wartości elementu
    Jak jednak to zrobić na cyklach?
    A może najpierw bez cykli, przejść całość a potem odrzucić końcowy gdy
    taki sam jak początkowy?


  • 3. Data: 2014-11-06 16:46:10
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-11-06 o 16:26, Borneq pisze:
    > Zwykły uniq:

    Mam:
    Poly tmpPoly;
    int newSize = polyIn->n - cntZeroLen;
    tmpPoly.SetSize(newSize);
    Point prevp,p0;
    int ii=0;
    for (int i = 0; i < polyIn->n; i++)
    {
    Point p = polyIn->pts[i];
    if (i==0) p0=p;
    if ((i==0) || (prevp.x!=p.x || prevp.y!=p.y))
    {
    if (ii<newSize)
    {
    tmpPoly.pts[ii] = polyIn->pts[i];
    ii++;
    prevp = p;
    }
    else
    assert(p.x==p0.x && p.y==p0.y);
    }
    }


  • 4. Data: 2014-11-07 17:13:06
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: bartekltg <b...@g...com>

    On 06.11.2014 16:15, Borneq wrote:
    > Jak przepisać jeden wielokąt na inny zamieniając się duplikujące się
    > (lub zwielokrotnione) wierzchołki oznaczające krawędzie długości zero?
    > Problem wydaje się banalny, oto przelatujemy w pętli listę wierzchołków
    > i kopiujemy do drugiej listy tylko gdy się różnią i tylko wtedy
    > zwiększamy drugi indeks.
    > Ale problemy są:
    > - jest to lista cykliczna, musimy usuwać ostatni równy pierwszemu
    > - chcę by pierwszy punkt pozostał pierwszym, choć ten warunek jest nie
    > taki ważny
    > - mogą być całe serie, więcej niż dwa takie same


    Zapomnaiłeś powiedzieć, jak wygląda Twoja struktura.

    Nie widzę powodu, dlaczego zwykłe std::unique miałoby
    nie zadziałać.

    pzdr
    bartekltg


  • 5. Data: 2014-11-07 17:56:32
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-11-07 o 17:13, bartekltg pisze:
    > Zapomnaiłeś powiedzieć, jak wygląda Twoja struktura.
    >
    > Nie widzę powodu, dlaczego zwykłe std::unique miałoby
    > nie zadziałać.

    std::unique działa na wektorze?
    Tu musi działać na cyklu

    stuktury:
    struct Poly
    {
    int n;
    Point *pts;
    }

    struct Point
    {
    int x, y;
    }


  • 6. Data: 2014-11-07 18:34:04
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: bartekltg <b...@g...com>

    On 07.11.2014 17:56, Borneq wrote:
    > W dniu 2014-11-07 o 17:13, bartekltg pisze:
    >> Zapomnaiłeś powiedzieć, jak wygląda Twoja struktura.
    >>
    >> Nie widzę powodu, dlaczego zwykłe std::unique miałoby
    >> nie zadziałać.
    >
    > std::unique działa na wektorze?

    I nie tylko.

    > Tu musi działać na cyklu

    A co to znaczy, że działa na cyklu?
    Tego właśnie nie mówisz. Najpierw myślałem, że masz
    prawdziwą listę cykliczną (zapomniju o QT;) lista to taka
    struktura, gdzie trzymasz wskaźnik na następny element
    http://en.wikipedia.org/wiki/Doubly_linked_list )
    ale kod sugeruje, że trzymasz to w tablicy.

    To na czym polega cykliczność? NA tym, że ostatni element
    jest taki sam jak pierwszy?
    To jeśli lista skłąda się tylko z takich samych elementów,
    unique zwróci coś zawierającego tylko jeden element.
    Jeśli pomiędzy jest cokolwiek innego, po przejśćiu
    algorytmu pozostanie jeden element na początku i na końcu
    równy temu, co było przed operacją.
    Nie wiedzę nic niezgodnego z wypisanymi oczekiwaniami.

    a-a-a-a => a
    a-a-b-c-b-b-d-d-a-a-a => a-b-c-b-d-a


    > stuktury:
    > struct Poly
    > {
    > int n;
    > Point *pts;
    > }

    A czemu nie vector<Point> ;>


    > struct Point
    > {
    > int x, y;
    > }

    Użyj pary albo dodaj operator ==.

    pzdr
    bartekltg



  • 7. Data: 2014-11-07 18:36:40
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-11-07 o 18:34, bartekltg pisze:
    > a-a-a-a => a
    > a-a-b-c-b-b-d-d-a-a-a => a-b-c-b-d-a

    a powinno być => a-b-c-b-d
    bo nie trzymam ostatniego równemu pierwszemu ale wierzchołki wielokąta,
    po ostatnim d jest pierwsze a


  • 8. Data: 2014-11-07 20:59:45
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: bartekltg <b...@g...com>

    On 07.11.2014 18:36, Borneq wrote:
    > W dniu 2014-11-07 o 18:34, bartekltg pisze:
    >> a-a-a-a => a
    >> a-a-b-c-b-b-d-d-a-a-a => a-b-c-b-d-a
    >
    > a powinno być => a-b-c-b-d
    > bo nie trzymam ostatniego równemu pierwszemu ale wierzchołki wielokąta,
    > po ostatnim d jest pierwsze a

    Czyli po unique trzeba sprawdzić, czy ostatni nie jest taki sam jak
    pierwszy i ewentualnie go wyrzucić.


    vector <Point> points; //Point ma zdefiniowane ==

    ....

    auto new_end = unique(data.begin(), data.end());
    if (new_end!=data.begin()) // mogę się cofnąć?
    if ( *(prev(new_end)) == *(data.begin()) //elementy są równe
    && prev(new_end)!=data.begin() )//i nie jest to jedyny element
    --new_end;
    data.erase (new_end,data.end() ); // i tak trzeba ro zrobić po unique
    //albo data.resize(new_end - data.begin());

    Jak wolisz kopiować, to jest unique_copy.


    Zerknij jak samo unique jest zaimplementowane, ładnie i sprytnie.


    pzdr
    bartekltg


  • 9. Data: 2014-11-07 21:17:24
    Temat: Re: Eliminacja podwójnych wierzchołków = uniq na liście cyklicznej
    Od: Borneq <b...@a...hidden.pl>

    W dniu 2014-11-07 o 20:59, bartekltg pisze:
    > Zerknij jak samo unique jest zaimplementowane, ładnie i sprytnie.

    W <algorithm>

strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: