Körök érintézési pontjai [ C# ]

Körök érintézési pontjai [ C# ]
2022-11-01T09:47:24+01:00
2022-11-13T21:32:49+01:00
2022-11-14T11:15:26+01:00
DFORCER
Sziasztok!

Lenne egy olyan problémám, hogy ki kéne számolni kettő, vagy több különböző sugarú kör érintkezési pontjait.

Egyes kör adatai:
                                   - sugár
                                   - kör középpontja (x, y)

Matematikai megoldásom a kör egyenletéből egyenlet rendszer készítése, viszont egy programba nyílván nem írhatom bele az egyenletet.
Kifejezni a kör egyenletéből az x, illetve az y változót nagyon nehézkes lenne.

Van valakinek valami ötlete egy olyan algoritmusra, ami meghatározza azokat az éritkezési pontokat, persze ha léteznek éritkezési pontok.
Ha valaki kész megoldést küldene nem szeretnék libraryket, és c# future-oket sem használni a kódban, mintha c-ben programoznánk :D

A tippeket, és válaszokat előre is köszönöm!
Mutasd a teljes hozzászólást!

  • Hali!

    Mutasd – akár (!) C#-forráskóddal/-részlettel –, hogy eddig mivel, hogyan próbálkoztál, meddig jutottál el, mi nem megy, miben/hol akadtál el!

    Mutasd a teljes hozzászólást!
  • Kifejezni a kör egyenletéből az x, illetve az y változót nagyon nehézkes lenne.

    Pedig ez lesz a megoldás. Papír-ceruza módszerrel szépen levezeted, hogy milyen pontok elégítik ki mindkét kör egyenletét, és azok lesznek a metszési pontok. (Vagy csak egy pont, ha a körök érintik egymást de nem metszik. Vagy végtelen sok pont, ha a két kör középpontja és sugara is megegyezik, tehát igazából ugyanazt a kört kaptad inputnak kétszer. Gyanítom hogy be fog jönni a képbe a másodfokú egyenlet megoldóképlete, és a kettő/egy/nulla lehetséges megoldás fogja jelezni hogy metsző, érintő vagy egymástól távol eső köröket.)

    Ha nem megy egyből általánosan a levezetés, akkor próbálhatod először konkrét körökkel, különböző esetekkel, hogy meg tudd figyelni mikor hogy alakul a levezetés. Ebből is próbálhatod általánosítani a megoldást.

    Vagy kereshetsz guglin kész kódot, amit csak kopi-pásztázni kell, de cserébe nem is fogsz tanulni belőle semmit...
    Mutasd a teljes hozzászólást!
  • Szia!

    Leírtam mivel próbálkoztam, nem szükséges kód a megoldáshoz, mivel a megoldás algoritmusa az amit nem tudok megoldani.

    Akár mondatokkal vagy matematikailag is leírhatod a megoldásod, a programozás része csak az algoritmus megvalósítása, de az a gond, hogy nincs meg az az algoritmus amivel kiszámolhatnám.
    Mutasd a teljes hozzászólást!
  • A kör egyenletén kívül geometriai úton is meg lehet oldani az egyenletet, ami sokkal célravezetőbb programozás szempontjából.
    Mutasd a teljes hozzászólást!
  • Én elhiszem neked, mert már jó tizenöt éve lediplomáztam, a geometria már régen volt

    De a lényeg remélem átment azért: ahelyett, hogy kész algoritmust kérsz, inkább próbáld meg megoldani papír-ceruza módszerrel különböző esetekre, és abból próbálj általánosítani. Így többet fogsz tanulni belőle mintha lemásolnál egy készet.

    Például, ha a két kör középpontja messzebb van egymástól, mint a sugaruk összege, akkor tudod hogy nulla megoldás lesz. Ha pont egyenlő, akkor megint könnyű, a két középpont közé húzott szakaszon lesz a megoldás. Ha közelebb van, akkor két metszéspont lesz, ott fel lehet rajzolni különböző háromszögeket, de ezt most lusta vagyok (helyetted) végiggondolni. A koordináta-geometriát persze nem fogod megúszni így sem, mert azokból a szakaszokból és szögekből valahogy X, Y koordinátát kell kihoznod.
    Mutasd a teljes hozzászólást!
  • Pl. itt találsz egy képletet rá általános formában: How can I find the points at which two circles intersect? az "The intersection points are given by" alatti képlet az.
    De amúgy meg lehet empirikusan közelítőleg is oldani. Pl. ha tudsz bitmap képre rajzolni és a pixeleit olvasni (GetPixel eljárás), akkor eljárhatsz a következőként: Beszínezel egy bitmappet pl. fehérre. Rárajzolod az első kört a "szabványos" drawellipse eljárással feketével. A második kör paramétereit alapul véve az X-et változtatva x0 +- r között megkeresed az y megfelelő értékeit, amik a második körhöz tartoznak és megnézed, hogy az x,y pont milyen színü a bitmap-ban. Ha fekete, akkor metszi az első kört abban a pontban, egyébként nem. Figyelj rá, hogy egy x értékhez általában 2 y is tartozik. Nyilván ahhoz, hogy legalább megközelítőleg pontos legyen érdemes felnagyítani a koordinátákat, hogy a bitmap hasznos mérete eléggé nagy legyen (pl. 1000-nél egy ezrelék pontosságod lesz).
    Mutasd a teljes hozzászólást!
  • De amúgy meg lehet empirikusan közelítőleg is oldani.

    Érdekes javaslat. Egyrészt intuitíve belátható hogy hogyan működik, de cserébe nagyságrendekkel több számítást végzel mint amennyi indokolt lenne. (Az a körrajzoló függvény végső soron a kör egyenletének megoldásait fogja szolgáltatni, de ahelyett hogy ezeket direktben kipróbálnád, inkább belerajzolod egy bitmapbe hogy később visszaolvashasd.) Ráadásként még pontatlanabb is lesz a végeredmény, mint amit a közvetlen számítás adott volna.

    Egyszóval cseles a megoldás, de ha én javítanám a beadandót én nem engedném át
    Mutasd a teljes hozzászólást!
  • Hello,

    Circle-circle intersection points

    Az elsö hozzászólásban szépen le van írva mit kell csinálni (javaslom ezzel kezdd), aztán ha nem bírsz el az implementációval, akkor a következö hozzászólásban van kód is. Ha jól láttam.

    Ezen kívül még sok féle képpen meg lehet oldani, de ez elég egyszerü.
    Mutasd a teljes hozzászólást!
  • Van link egy exact képletre is a hozzászólásomban.
    Mutasd a teljes hozzászólást!
  • Köszönöm, a figyelmemet az előtt sem kerülte el hogy rámutattál volna, csak hát a hozzászólásodnak nem arra a részére reagáltam. A válaszom elején azért volt az idézet tőled, hogy világos legyen melyik részre reagálok.
    Mutasd a teljes hozzászólást!
  • Te ebben biztos vagy?

    Nem értem, hogy pontosan mit szeretnél. Van N darab köröd. Ez 3*N szám (X, Y, r).
    Ha érintkezési pontokra vagy kíváncsi (tehát biztos vagy benne, hogy a körök csak érintkeznek, nem pedig metszik egymást, vagy téged a metszőpontok nem érdekelnek), akkor az alábbi O(N^2) algoritmust javaslom, ahol X, Y, r tömbök és a kör adatait tárolják.

    for (int i=0; i<N; ++i) { for (int j=i+1; j<N; ++j) { float d = distance(X[i], Y[i], X[j], Y[j]); if (abs(d-r[i]-r[j]) < epsilon) { float x_h = (X[i]*r[i] + X[j]*r[j])/(r[i]+r[j]); float y_h = (Y[i]*r[i] + Y[j]*r[j])/(r[i]+r[j]); println(i, " és ", j, " kör érintkezik a ", x_h, ", ", y_h, " ponton"); } } }
    A distance(x1, y1, x2, y2) megadja az euklideszi távolságot (x1, y1) és (x2, y2) pontok között. 
    Ez az algoritmus azt nézi meg, hogy két kör távolsága (epsilon hibahatáron belül) annyi-e, hogy érintkeznek csak és ha igen, akkor kiszámolja a középpontok súlyozott átlagából az érintkezési pontot.

    Ha érdekel a körök metszéspontja is, akkor annyival fog bonyolódni a kódod, hogy nem súlyozott átlaggal kell kiszámolnod az érintkezési pontot, hanem fel kell írnod mindkét kör egyenletét, ki kell számolnod a megoldást x-re és y-ra és azok lesznek a megoldásaid. A körök egyenletei másodfokúak, ezért egy másodfokú egyenletrendszered lesz. Nem nehéz lekódolni, de ha nem akarod papíron, a Volfram Alpha-val szimbolikusan meg tudod oldani, azt pedig szinte már csak másolnod kell.

    (Még annyi, hogy ha metszéspont is érdekel, akkor az if feltételét se felejtsd el átírni és az érintőpontokat illik külön kezelni, hogy elkerüld a numerikus hibákat.
    Arra gondolok, hogy ha két kör pont érintkezik, akkor a számábrázolás sajátosságai miatt vagy kapsz két valós megoldást (mintha metszenék egymást), vagy két komplex megoldást (mintha nem metszenék egymást).
    Mutasd a teljes hozzászólást!
  • Van eset, amikor ez a módszer jó ötlet.
    Például egyszer írtam egy Super Mario szerű játékot, ahol pontos ütközésdetekciót akartam. Itt azt csináltam, hogy a figurákat berajzoltam egy nem látszó bitmapra is olyan "színnel", ami az adott pixel funkcióját kódolta. (Pl.: ellenség piros, fal fekete, stb...)
    Innentől csak azt kellett vizsgálnom, hogy a játékos milyen színű pixeleket takar ki a "hátsó" bitmapon.
    Mutasd a teljes hozzászólást!
  • szerintem kihagytad a nagy körben egy kicsi kör esetét. tehát nem csak az r1+r2 == d lehet megoldás hanem abs(r1-r2) == d
    Mutasd a teljes hozzászólást!
  • Ki bizony...
    Mutasd a teljes hozzászólást!
  • Én eleve csak a metsző esettel foglalkoztam, mert talán az érintős  nem okoz gondot. (Ha mégis akkor majd azt is megnézem.) 
    Nemigen ellenőriztem a javasolt algoritmust, inkább egy pársoros kóddal próbáltam ki pár kockás papírra rajzolt kört. (És működött.)

    Egyébként ajánlatos jóban lenni a vektorgeometriával.

    Ezennel üdvözlök minden régi és új tagot, miután 7 éve léptem be utoljára, a prog.hu-ra,
    Mutasd a teljes hozzászólást!
    Csatolt állomány
Tetszett amit olvastál? Szeretnél a jövőben is értesülni a hasonló érdekességekről?
abcd