Builder.cz - Informacni server o programovani

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

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

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

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

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.

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

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.

[quote="bezradný"]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 :([/quote] 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

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

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

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

[quote="bezradný"]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)[/quote] 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

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)

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

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?

[quote="bezradný"]díky za odpověď, bohužel se obávám, že convex hull hledá pouze krajní body, já potřebuji propojit všechny[/quote] 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

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

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

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

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

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

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

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

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