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ą

do góry

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?

do góry

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);
}
}

do góry

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

do góry

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;
}

do góry

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

do góry

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

do góry

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

do góry

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

W <algorithm>

do góry