Portál AbcLinuxu, 13. května 2025 03:17

Dotaz: Detekce objektu ze samostatných hran

22.7.2011 10:40 Nosense
Detekce objektu ze samostatných hran
Přečteno: 498×
Odpovědět | Admin
Přílohy:
Dobrý den

Řeším problém jak z množiny samostatných křivek určit objekty které jsou jimy definovány. Vstupem je množina uzavřených křivek, kde každá z křivek je tvořena posloupností úseček. Křivky se neprotínají. Pořadí vstupních křivek ani směr jejich definice (po/proti směru hodin) není definován. Výstupem by pro každou křivku měla být informace "vpravo (po směru definice) je objekt, vlevo je prázdný prostor", respektive naopak a úroveň vnoření (viz přiložené obrázky).

Budu rád za jakékoliv naznačení správného algoritmu.
Nástroje: Začni sledovat (0) ?Zašle upozornění na váš email při vložení nového komentáře.

Odpovědi

22.7.2011 11:06 Marv-CZ | skóre: 21
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Odpovědět | | Sbalit | Link | Blokovat | Admin

Chceš akorát provést graficky to vyplnění ploch jako na obrázku po.png nebo získat informaci, které křivky spolu tvoří vyplněný objekt?

To první je jednodušší. Hledej „paritní řádkové vyplňování“ nebo „vyplňování rozkladovými řádky“.

22.7.2011 11:24 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Obrázky jsem zadal jen pro ilustraci. O uvedených metodách grafického vyplňování vím, ale potřebuji přesně ty informace co jsem napsal (tj. hodnota "vpravo"/"vlevo" a číslo úrovně vnoření), nikoliv grafickou reprezentaci. Vstupní data mi vypadnou z (pseudo)CAD programu a cílem je nakonec vygenerovat data pro CNC frézu. Potřebuji pro každou křivku vyřešit 2 problémy – 1. kompenzace průměru frézy: je potřeba určit po které straně řezat; 2. pořadí řezání: není možné vyříznout nejdřív vnější křivku a potom vnitřní, protože by daná část už nedržela.
22.7.2011 11:38 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Pošlete to do kooperace na laser nebo vodu. :-)(Sorry nedalo mi to :-()
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
22.7.2011 12:01 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Nevím jestli jsem to správně pochopil, ale jakékoliv odesílání někam nic nevyřeší, protože se mi cílový stroj válí doma v dílně. A u laseru i vody je třeba řešit stejné problémy – vodní ani laserový paprsek není možné zaostřit do nekonečně úzkého paprsku.
22.7.2011 15:19 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
To nelze (s pohledu frézy ano :-)), ale software dodávaný k těmto zařízením to má již vyřešené.
Což Vám samozřejmě nepomůže, pokud to chcete dělat doma a neřeší to dotazovaný problém.
Mně to nedalo jen proto, že efektivita řezaní laserem (pokud se jedná o plech do cca. 3mm) je výrazně vyšší než mechanické dělení (frézování) - u vody je to obdobné. Frézování je efektivnější jen tehdy pokud je možné položit více plechů na sebe a řezat jich více současně a dělá se to ve větších dávkách po tabulích. Ale pak je třeba řešit některé další věci jako správné broušení nástroje, dořezávání můstků apod.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
22.7.2011 19:11 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Protože se jedná v podstatě výlučně jen o řezání dřeva (překližky) je fréza nejvhodnější nástroj. Vodní paprsek nemá smysl pro dřevo řešit. U laseru je problém opálení řezaných hran, protože na nich lepidlo drží podstatně hůře než na frézovaných hranách. A co jsem se doposud setkal s laserem řezanými díly (ze dvou různých strojů) byla oproti frézování kupodivu mizerná přesnost. Nejednalo se sice o hi-tech, ale jen poloprofesionální stroje za řádově stovky tisíc, nicméně od operátorů obou strojů jsem slyšel stížnosti na to, že laser je v podstatě nemožné přesně zaostřit, protože z laserové hlavy vychází mírně kuželový paprsek. Na dílech co jsem měl v ruce dělala odchylka až 2 desetiny milimetru.
22.7.2011 20:55 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Tak to laser není dobrý nástroj, zde by uspěla voda (no dřevo lze řezat vodou :-), pokud mu to nevadí :-) ), která ovšem podřezání (rozptyl) má větší než laser (laser u tenkých plechů ten rozptyl má zanedbatelný, ale je zbytečné to rozebírat :-)). Co se týče přesnosti při dobrém seřízení a nastavení je ta přesnost ve 2D rozhodně pod 0.1mm.
Zaručenou přesnost vyšší 0.2 milimetrů na překližce a obecném 2D tvaru bych se neodvážil garantovat ani kdyby mě mučili :-).
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
22.7.2011 13:07 Marv-CZ | skóre: 21
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Příloha:

Pořadí řezání:

  1. zjistit ohraničující okna
  2. ohodnotit do kolika větších oken, okno spadá
  3. řezat od těch s nejvyšší hodnotou

Snad to bude pochopitelnější z přiloženého obrázku.

Pro určení strany, po které řezat, by snad šlo nějak využít modifikaci toho vyplňovací algoritmu - řeže se po „nevyplněných“ stranách.

22.7.2011 14:44 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
U těch oken by mohl být problém s překrýváním. Tvary mohou být i konkávní, takže jejich křivky se sice neprotínají, ale jejich vnější okna se překrýt mohou. Napadla mě ale modifikace řádkového vyplňování, která by mohla vyřešit oba problémy. Teď bohužel musím běžet, ale do večera to ještě promyslím a ozvu se.
22.7.2011 15:05 Marv-CZ | skóre: 21
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran

Ty konkávní tvary jsem bral v úvahu a mělo by to fungovat i tak. Hodnota se zvyšuje jen v případě, že okno je celé uvnitř jiného, překrývající se v úvahu neberou.

Pokud něco zajímavého vymyslíš tak se pak určitě poděl.

22.7.2011 18:46 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
v podstatě mě napadlo, že pokud bych uměl zjistit jestli konkrétní bod leží vně nebo uvnitř křivky, mohl bych zajistit pořadí řezání následovně: pro každou křivku bych otestoval jestli libovolný bod, každé z dalších křivek (a tím i celá křivka) leží uvnitř nebo vně testované křivky. Pro každou, křivku která leží uvnitř bych inkrementoval čítač úrovně. Tedy v pseudokodu nejak takto:
MnozinaKrivek K
Krivka i,j

for i in K:
    for j in (K-i):
        if (j.bod uvnitr i) then j.level++
Tím bych pro každou křivku dostal úroveň stejně jako na druhém obrázku z úvodního příspěvku. Vyřezávání pak probíhá od nejvyšší úrovně. Úroveň kromě pořadí řezání značí i stranu – každá sudá úroveň značí vnější hranu a lichá vnitřní. Tento celý postup je ovšem založen na tom, že umíme určit jestli bod leží uvnitř nebo vně křivky. Tady přichází na řadu modifikovaný postup řádkového vyplňování, ale možná by přesnější termín byl ray casting. V podstatě jde o to vrhnout z testovaného bodu paprsek (libovolným směrem) a zkontrolovat jestli je počet průsečíků s křivkou lichý (bod je uvniř) nebo sudý (bod je vně). Je potřeba ještě promyslet speciální případy, např. paprsek procházející vrcholem, ale to se řeší právě v řádkovém vyplňování, takže vyhrabu pár poznámek ze školy a nejspíš to tam najdu.
22.7.2011 19:50 Marv-CZ | skóre: 21
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Příloha:

Ještě musíš vzít v úvahu, že u nekonvexních křivek ti to může jednu křivku protnout vícekrát. A další problém je, kam vlastně paprsek vrhat - podívej se na příklad v příloze.

A ještě mám takový dotaz víceméně nesouvisející s postupem co řešíme. Co se vlastně bude dít s tím materiálem, který jde pryč. Jen se odřízne podle obrysů nebo se postupně celý odfrézuje?

22.7.2011 21:17 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
No především se při hledání jestli bod leží uvnitř nebo vně křivky bere v úvahu pouze jedna uzavřená křivka a ostatní se ignorují. Nekonvexní tvary řeší právě sudý/lichý počet průsečíků. Předpokládejme bod uvnitř a z něj paprsek vedený libovolným směrem (v reálu se bude používat rovnoběžný s jednou z os). Tento paprsek musí konečnou uzavřenou křivku opustit ať chce nebo ne = 1 průsečík. U nekonvexního tvaru může do křivky znovu vstoupit, ale musí také znovu vystoupit, takže se počet průsečíku může dále zvyšovat pouze po dvou. Tím tedy zůstane zachován lichý počet průsečíků u paprsku, který začínal uvnitř. Pokud paprsek začíná vně křivky, buď křivku neprotne = 0 průsečíků, nebo do ní vstoupí, ale také vystoupí = 2 průsečíky, což se může opakovat, ale lichý počet průsečíků zůstane.

Řežou se pouze obrysy. To znamená, že materiál mezi díly zůstává.
22.7.2011 21:11 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Pokud by tvar byl konvexní stačí spočítat kolmý vektor do daného bodu ke všem úsečkám(vektorům) dané seřazené a CW nebo CCW křivky (kteroužto seřazenou mít musíte pro generovaní dráhy) a pokud kolmice směřují na stejnou stranu (+/-) tak je bod uvnitř. - jen nápad, mně tyto věci, ale většinou moc nejdou…
Ale jinak co tak něco skoro-hotové. (Ať přispěji něčím lepším, než v předchozím podvlákně)
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
22.7.2011 21:25 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Ano to je přesně co jsem hledal a nakonec vymyslel :), konkrétně jednodušší verzi s jednou křivkou (http://en.wikipedia.org/wiki/Point_in_polygon), která mi umožní krom orientace hran (vnitřní nebo vnější) určit také pořadí řezání, jak popisuji o něco výše.
22.7.2011 23:04 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Jaký máte stroj, má svůj řídící systém? Ptám se proto jestli kompenzaci nástroje (dráhovou korekci ) řeší systém nebo vy. Pokud Vy tak je před Váma další problém „jak objet vnější rohy“.
Máte v zásadě tři zákadní možnosti:
  1. Objet je ekvidistantními úsečkami protaženými do průniku, ale to při velmi ostrém úhlu může znamenat  „zajet si do sousedního města“, při úhlu kolem 90° to zas způsobí rázy - kinetická energie a náhlá změna směru je sfiňa (to Vám asi nebude vadit)
  2. Obtočit roh po kružnici kde poloměr se rovná kompenzaci (R nástroje), což může při pomalém chodu spálit povrch výsledného výrobku a „svalíte“ roh (zde je otázka jestli rychlost řídíte dle středu nástroje nebo dle dotyku s materiálem, jenže v tomto případě by musela být rychlost, tak vysoká že se tom ani fotonu nesnilo, bo objíždíte bod :-)).
  3. Provést elegantní smyčky, které zajistí ostrý roh, nejedou „moc“ navíc a mají klidný chod, ale kdo se s tím má počítat, že :-).
No a proč to píšu, protože mě to baví a protože krom možnosti dva, máte nové polygony a to i nekonvexní nebo samy sebe protínající se, a které musí mít všudypřítomnou vzdálenost mezi sousedními dvěma minimálně ø nástroje.

No a pokud to řeší stroj, (definujete stranu - dráhovou korekci a průměr nástroje), tak zas musíte vědět jak to systém řeší, nebo lze-li to definovat, jinak vám budou vznikat „obloučky“ (zafrézování) na vnitřních stranách dílů, které jste nechtěl :-(
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
23.7.2011 11:36 Nosense
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
No je to takový "na koleně" spíchnutý stroj z toho co dům dal. Řízené je to pomocí EMC2 (http://www.linuxcnc.org/), který má poměrně pokročilý systém plánování trajektorie a komponezace nátrojů (popsáno např zde: http://www.linuxcnc.org/docview/html/gcode_tool_compensation.html). Mně tedy vlastně stačí nadefinovat si parametry nástrojů v tabulce nástrojů EMC2 a potom na začátku programu v g-code vybrat nástroj a před každou křivkou určit řez po pravé nebo levé straně následující dráhy. Software by měl vyřešit ostatní.
23.7.2011 12:40 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Díval jsem se a je to taková „ISO“ klasika (G40/G41/G42), a výpočet se standardně obtočí kolem rohu po kružnici.
Takže pokud se pojede stejnou rychlostí může u dřeva dojít k připálení rohu (celou dobu realizace kruhového oblouku řeže nástroj obvod dílu na stejném místě) a obecně ke zaoblení rohu (dle nastavení G61/G64 a schopnosti pohonů).

a před každou křivkou určit řez po pravé nebo levé straně
Poznámka: Odečtení kompenzace (posun nástroje na ekvidistantní dráhu) je (obvykle, kde jinde :-)) provedeno v bloku (řádku), ve kterém je řazena funkce (G40/G41/G42), takže blok (řádek) předem by jste měl být ve vzdálenosti větší než R nástroje od řezané kontury. A ideální je aby pohyb v bloku kde je kompenzace řazena byl v rovině XY (předpokládám tuto rovinu) větší než R nástroje, pak je pohyb stroje „čistý“
Co to všechno znamená? No jen to, že bude třeba řešit nájezd na „konturu“ a automaticky může být obtížné toto vyřešit (laser a voda to má jednoduché, kompenzace je obvykle menší, než minimální možná vzdálenost kontur od sebe.)

No a když je obsluha pako a nechá vám zařezání na tvaru, tak je to vidět, a je to jedno jestli je to na laseru/vodě či frézce.
Nejen proto, ale i proto existují NC programátoři :-).
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†
22.7.2011 15:36 Šangala | skóre: 56 | blog: Dutá Vrba - Wally
Rozbalit Rozbalit vše Re: Detekce objektu ze samostatných hran
Nekonvexní obrazce se převedou na více konvexních a pro takovouto skupinu musí platit to co pro jeden objekt.
To, že trpíš stihomamem, ještě neznamená, že po tobě nejdou. ⰞⰏⰉⰓⰀⰜⰉ ⰗⰞⰅⰜⰘ ⰈⰅⰏⰉ ⰒⰑⰎⰉⰁⰕⰅ ⰏⰉ ⰒⰓⰄⰅⰎ ·:⁖⁘⁙†

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267, (c) 1999-2007 Stickfish s.r.o.