Builder.cz - Informacni server o programovani

Odběr fotomagazínu

Fotografický magazín "iZIN IDIF" každý týden ve Vašem e-mailu.
Co nového ve světě fotografie!

 

Zadejte Vaši e-mailovou adresu:

Kamarád fotí rád?

Přihlas ho k odběru fotomagazínu!

 

Zadejte e-mailovou adresu kamaráda:



seřazení "náhodných" bodů pro vykreslení polygonu

Seznam témat     Nová odpověď

Přihlásit se     Registrace     Zapomenuté heslo

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: tc2 ♂

9:02:11 20.02.2014

Serazeni bodu je trivialni uloha.

Mene trivilani je to udelat rychle.

Jedna z moznosti je koncove body v segmentech reprezenovat objektem ktery nese odkaz na (dva) segmenty ke kterym patri. Pak staci jeden pruchod vstupnimi daty a pak jedna prochazka od segmentu k segmentu.

V pripade, ze jednotlive body jsou dobre porovnatelne (treba celociselne souradnice) je vse vyreseno a je mozne se popasovat i se situaci, ze ve vstupnich datech nektere segmenty chybi (vysledek nebude polygon ale nekolik lomenych car).

V pripade pribliznych souradnic (float cisla vznikla vypoctem) je to trochu slozitejsi. Mozne je porovnavat body s nejakym epsilon a pak se zamyslet nad spojenim lomenych car.

Zkusenost nas ale uci, ze vstupni seznam souradnic obvykle vznika nejakym systemem a lse jiz tento seznam doplnit dalsi informaci pro spojovani. Jinymi slovy, reseni ulohy se lse vyhnout lepsi analyzou sirsiho problemu.

Zdravim

TC

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: tc2 ♂

16:43:13 19.02.2014

1. seznam usecek
2. prazdny polygon
3. vyjmout jednu usecku ze seznamu a jeji koncobe body dat jako prvni dva vrcholy polygonu


Az do vyprazdneni seznamu:
{
--- najit usecku jejiz bod (pocatecni nebo koncovy) je nejblizsi koncobemu vrcholu
--- pridat druhy konec usecky jako dalsi vrchol
--- odejmout usecku
}

Zdravim

TC

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: peta1 ♂

13:42:17 26.07.2013

Divne reseni, nikdy jsem podobny problem neresil.
Ja bych si udelal kruh nebo elisu a do ni bych se pokusil ty usecky nasoukat tak, aby krajni body byli na okrajich te elipsy. Pak vzniknou 2 mozne polohy usecky, bud nahore nebo dole.
Nebo by slo pouzit metodu takovou, ze je das vsechny stredem do stredu a vytlacujes na okraje, natahujes kruznici postupne.
Pak tu je proste moznost projit vsechny mozne kombinace, uloha ala obchodni cestujici. A zjistit, ktere z nich vyhovuji reseni jeden polygon. Treba hvezda je take z usecek. Ale ze stejnych usecek jen na jinych mistech mas i kruhovity mnohouhelnik.

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: asdrtdsftdstr ♂

9:57:18 07.05.2013

bezradný napsal/a

přesně takto jsem to dělal a funguje to jen u některých což ale je podivné :( Ovšem je třeba myslet na to že se úsečky vykreslují různě, tedy koncový bod úsečky nemusí být nutně počátečním nějaké jiné, ale může být opět počáteční (protože ta je definované v opačném směru) ale to bylo jednoduché, nicméně někde je zakopaný pes :(



kontrolu pocatecnich/koncovych bodu lehce pridas do algoritmu.
a je tam jeste nejaky jiny zakopany pes?
mohl bys treba na pastebin, ulozto dat obrazek vstupnich usecek a vystupni obrazek s prikladem kdy ti to nefungovalo.

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: bezradný ♂

9:18:10 07.05.2013

přesně takto jsem to dělal a funguje to jen u některých což ale je podivné :( Ovšem je třeba myslet na to že se úsečky vykreslují různě, tedy koncový bod úsečky nemusí být nutně počátečním nějaké jiné, ale může být opět počáteční (protože ta je definované v opačném směru) ale to bylo jednoduché, nicméně někde je zakopaný pes :(

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: hcgjfgjfghjfgjfgj ♂

9:11:57 07.05.2013

bezradný napsal/a

konkrétní X1,Y1 -> X2,Y2 body úseček možná řeknou víc:

100.8190777899, 441.8990594844 -> 510.8190777899, 441.8990594844
100.8190777899, 441.8990594844 -> 100.8190777899, 266.8990594844
100.8190777899, -8.1009405156 -> 510.8190777899, -8.1009405156
510.8190777899, 441.8990594844 -> 510.8190777899, 39.3990594844
483.2190777899, 39.3990594844 -> 510.8190777899, 39.3990594844
100.8190777899, 166.8990594844 -> 100.8190777899, -8.1009405156
100.8190777899, 266.8990594844 -> 140.8190777899, 266.8990594844
553.2190777899, 216.8990594844 -> 42.6878948411, 216.8990594844
100.8190777899, 166.8990594844 -> 140.8190777899, 166.8990594844
140.8190777899, 266.8990594844 -> 140.8190777899, 166.8990594844
483.2190777899, 39.3990594844 -> 483.2190777899, 19.3990594844
483.2190777899, 19.3990594844 -> 510.8190777899, 19.3990594844
510.8190777899, 19.3990594844 -> 510.8190777899, -8.1009405156

tyto úsečky tvoří uzavřenou oblast, ovšem, jsou definovány chaoticky (zprava,zleva,zhora,zdola)



pokud mam teda jistotu, ze to je uzavrena oblast, tak bych zacal treba nejjednoduseji.

1) vezmu prvni usecku z puvodniho seznamu s body x1,y1 -> x2,y2, vyjmu z puvodniho a vlozim do noveho seznamu

2) projdu puvodni seznam a najdu usecku s pocatecnim bodem stejnym jako je koncovy bod usecku z 1, nalezenou usecku vyjmu ze stareho seznamu a vlozim do noveho seznamu

3) najdu dalsi usecku z puvodniho seznamu, ktera ma pocatecni bod stejny jako predesla usecka koncovy

4) pokracuju dokola s bodem 3

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: bezradný ♂

8:53:33 07.05.2013

konkrétní X1,Y1 -> X2,Y2 body úseček možná řeknou víc:

100.8190777899, 441.8990594844 -> 510.8190777899, 441.8990594844
100.8190777899, 441.8990594844 -> 100.8190777899, 266.8990594844
100.8190777899, -8.1009405156 -> 510.8190777899, -8.1009405156
510.8190777899, 441.8990594844 -> 510.8190777899, 39.3990594844
483.2190777899, 39.3990594844 -> 510.8190777899, 39.3990594844
100.8190777899, 166.8990594844 -> 100.8190777899, -8.1009405156
100.8190777899, 266.8990594844 -> 140.8190777899, 266.8990594844
553.2190777899, 216.8990594844 -> 42.6878948411, 216.8990594844
100.8190777899, 166.8990594844 -> 140.8190777899, 166.8990594844
140.8190777899, 266.8990594844 -> 140.8190777899, 166.8990594844
483.2190777899, 39.3990594844 -> 483.2190777899, 19.3990594844
483.2190777899, 19.3990594844 -> 510.8190777899, 19.3990594844
510.8190777899, 19.3990594844 -> 510.8190777899, -8.1009405156

tyto úsečky tvoří uzavřenou oblast, ovšem, jsou definovány chaoticky (zprava,zleva,zhora,zdola)

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: dfsadfasdf ♂

8:43:54 07.05.2013

bezradný napsal/a

díky za odpověď, bohužel se obávám, že convex hull hledá pouze krajní body, já potřebuji propojit všechny



takze mas hafo nahodnych usecek, dve nahodne usecky obecne nemusi sdilet svoje koncove body.
a ty chces pospojovat nespojene koncove body, aby nakonec vznikl jakykoliv polygon.
detaily?

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: bezradný ♂

8:24:30 07.05.2013

díky za odpověď, bohužel se obávám, že convex hull hledá pouze krajní body, já potřebuji propojit všechny

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: zdfgsdfgsdg ♂

17:55:04 06.05.2013

asi je celkem jedno jak jsou jednotlive nahodne body x1,y1...x2,y2 proppojene do usecek.
nestaci pro ty nahodne body najit "conveh hull"

http://en.wikipedia.org/wiki/Convex_hull

Citovat příspěvek

 

Re: seřazení "náhodných" bodů pro vykreslení polygonu

Autor: bezradný ♂

14:50:12 06.05.2013

BTW: úsečky nejsou v definici kontinuální, ale celkově tvoří uzavřenou oblast.
to říkám jen proto kdyby někoho napadlo proč prostě nevykreslím ty úsečky co mám :)

Citovat příspěvek

 

seřazení "náhodných" bodů pro vykreslení polygonu

Autor: bezradný ♂

14:47:14 06.05.2013

zdravím, mám následující problém:
mám náhodné úsečky (x1,y1 -> x2,y2) a potřebuji je seřadit tak, abych z nich měl polygonální oblast.
Resp. abych je mohl vykreslit. Poradí někdo jak na to?
Díky moc

Citovat příspěvek

 

 

 

Přihlášení k mému účtu

Uživatelské jméno:

Heslo: