eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingPunkty przecięcia okręgu i odcinka
Ilość wypowiedzi w tym wątku: 11

  • 1. Data: 2010-06-04 09:57:07
    Temat: Punkty przecięcia okręgu i odcinka
    Od: Dariusz Zolna <a...@u...com>

    Witam wszystkich,

    Dawno mnie tu nie było, ale nie mogę sobie poradzić z problemem z tematu
    i uznałem, że to dobre miejsce żeby zapytać :)
    Problem jest taki:
    W układzie kartezjańskim mam dany odcinek opisany współrzędnymi początku
    i końca (xp, yp, xk, yk) oraz okrąg opisany współrzędnymi środka i
    promieniem (x, y, r). Potrzebuję odnaleźć punkty przecięcia odcinka i
    okręgu. Możliwe są 3 przypadki:
    - brak punktów przecięcia
    - 1 punkt przecięcia (1 koniec odcinka znajduje się wewnątrz okręgu, to
    akurat jest proste do wykrycia)
    - 2 punkty przecięcia
    - przypadek odcinka stycznego do okręgu można pominąć

    Ktoś pomoże? Kawałek kodu w C byłby niezmiernie przydatny :)

    Pozdrawiam,
    Dariusz Żołna


  • 2. Data: 2010-06-04 10:11:48
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: "Stachu 'Dozzie' K." <d...@g...eat.some.screws.spammer.invalid>

    On 2010-06-04, Dariusz Zolna <a...@u...com> wrote:
    > Witam wszystkich,
    >
    > Dawno mnie tu nie było, ale nie mogę sobie poradzić z problemem z tematu
    > i uznałem, że to dobre miejsce żeby zapytać :)
    > Problem jest taki:
    > W układzie kartezjańskim mam dany odcinek opisany współrzędnymi początku
    > i końca (xp, yp, xk, yk) oraz okrąg opisany współrzędnymi środka i
    > promieniem (x, y, r). Potrzebuję odnaleźć punkty przecięcia odcinka i
    > okręgu. Możliwe są 3 przypadki:
    > - brak punktów przecięcia
    > - 1 punkt przecięcia (1 koniec odcinka znajduje się wewnątrz okręgu, to
    > akurat jest proste do wykrycia)
    > - 2 punkty przecięcia
    > - przypadek odcinka stycznego do okręgu można pominąć
    >
    > Ktoś pomoże? Kawałek kodu w C byłby niezmiernie przydatny :)

    1. Sprawdzasz czy odcinek aby na pewno przecina okrąg.
    2. Znajdujesz równanie prostej P zawierającej wybrany odcinek i równanie
    okręgu.
    3. Rozwiązujesz układ równań ułożony z równań prostej P i okręgu.
    4. ...
    5. Zysk.

    --
    Secunia non olet.
    Stanislaw Klekot


  • 3. Data: 2010-06-04 10:44:41
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: Wojciech Muła <w...@p...null.onet.pl.invalid>

    "Stachu 'Dozzie' K." <d...@g...eat.some.screws.spammer.invalid> wrote:

    > > Ktoś pomoże? Kawałek kodu w C byłby niezmiernie przydatny :)
    >
    > 1. Sprawdzasz czy odcinek aby na pewno przecina okrąg.
    > 2. Znajdujesz równanie prostej P zawierającej wybrany odcinek i równanie
    > okręgu.
    > 3. Rozwiązujesz układ równań ułożony z równań prostej P i okręgu.
    > 4. ...
    > 5. Zysk.

    W wersji praktycznej:

    1. znajdujesz równanie *parametryczne* prostej zawierające odcinek AB,
    tzn. P(t) = A + t(B-A)
    2. podstawiasz do równania okręgu - otrzymujesz równanie kwadratowe
    3. znajdujesz miejsca zerowe
    4. akceptujesz tylko parametry z zakresu [0,1]

    w.


  • 4. Data: 2010-06-04 10:59:57
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: "ŚLAMAZAR" <p...@p...onet.pl>

    > Witam wszystkich,
    >
    > Dawno mnie tu nie było, ale nie mogę sobie poradzić z problemem z tematu
    > i uznałem, że to dobre miejsce żeby zapytać :)
    > Problem jest taki:
    > W układzie kartezjańskim mam dany odcinek opisany współrzędnymi początku
    > i końca (xp, yp, xk, yk) oraz okrąg opisany współrzędnymi środka i
    > promieniem (x, y, r). Potrzebuję odnaleźć punkty przecięcia odcinka i
    > okręgu. Możliwe są 3 przypadki:
    > - brak punktów przecięcia
    > - 1 punkt przecięcia (1 koniec odcinka znajduje się wewnątrz okręgu, to
    > akurat jest proste do wykrycia)
    > - 2 punkty przecięcia
    > - przypadek odcinka stycznego do okręgu można pominąć
    >
    > Ktoś pomoże? Kawałek kodu w C byłby niezmiernie przydatny :)
    >
    > Pozdrawiam,
    > Dariusz Żołna

    jest wzorek - tu np znalazłem

    http://mathworld.wolfram.com/Circle-LineIntersection
    .html

    chyba żywcem można przepisac na c to co tutaj jest

    double dx = x2-x1;
    double dy = y2-y1;
    double dr = sqrt(dx*dx+dy*dy)
    double D = x1*y2-x2*y1;

    double x_1 =D*dy+sgn(dy)*dx*sqrt(r*r*dr*dr-D*D);
    double x_2 =D*dy-sgn(dy)*dx*sqrt(r*r*dr*dr-D*D);


    double sgn(double x)
    {
    if(x<0) return -1.0;
    else return 1.0;
    }

    itp. - trzebaby sprawdzić czy to dobrze działa itp i dac ify
    od tych przypadków po delcie tam niżej - chyba powinieneś sobie
    poradzić - bo ja jakos nie mam chęci tego tu całego klepac i
    nie mam kompilatora pod reką by sprawdzić,

    pzdr ŚLAMAZAR






    --
    Wysłano z serwisu OnetNiusy: http://niusy.onet.pl


  • 5. Data: 2010-06-04 11:17:43
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: "ŚLAMAZAR" <p...@p...onet.pl>

    no dobra doklepałem - ale klepie z palca po prostu powyzsze wzory
    ze stronki i kod niemal na 100% ma jakies proste bledy ktore
    musialbys poprawic - nie pamietam czy np nie przypluje sie do
    funkcji abs bo juz taka jest w math.h itp ani czy znaki we
    wzorkach na x_1 x_2 y_1 y_2 maja dobre znaki itp - ale mniej wiecej
    chyba o podobny prog ci chodzi (jest lato i dzis zaluje kazdej minuty
    spedzonej przed kompem tak ze wisisz mi 20 minut lata )


    pzdr ŚLAMAZAR

    #include<math.h>
    #include<stdio.h>

    double sgn(double x)
    {
    if(x<0) return -1.0;
    else return 1.0;
    }

    double abs(double x)
    {
    if(x<0) -1*x;
    else return x;
    }

    main()
    {
    double dx = x2-x1;
    double dy = y2-y1;
    double dr = sqrt(dx*dx+dy*dy)
    double D = x1*y2-x2*y1;

    double delta = r*r*dr*dr-D*D;


    if(delta<0) printf("brak punktow przeciecia");
    if(delta==0) printf("1 punkt przeciecia");
    if(delta>0)
    {
    double x_1 =(D*dy+sgn(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr;
    double x_2 =(D*dy-sgn(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr;
    double y_1 =(-D*dy+abs(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr;
    double y_2 =(-D*dy-abs(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr;

    printf("2 punkty przeciecia (%d,%d)(%d,%D)", x_1, y_1, x_2, y_2);

    }

    }

    pzdr ŚLAMAZAR



    --
    Wysłano z serwisu OnetNiusy: http://niusy.onet.pl


  • 6. Data: 2010-06-04 11:42:28
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: "ślamazar" <p...@p...onet.pl>

    acha - zapomniałem o inpucie - trzeba dodac jakis imput albo
    dane wejsciowe podac w kodzie - druga uwaga ten kod z tej stronki zakłada
    ze srodek okregu jest w (0, 0 ) jak nie to trzeba konce odcinka (i centrum
    okregu niejako niejawnie) przed przeliczeniem przesunac o roznice np

    x1-=ox;
    y1-=oy;
    x2-=ox;
    y2-=oy;

    a po przeliczeniu na odwrót do wyniku dodac (ox, oy)

    x1+=ox;
    y1+=oy;
    x2+=ox;
    y2+=oy;

    (albo cos podobnego trzeba chwile posprawdzac czy wszystko ok,
    w printfie double wyświetla sie przez %f a nie %d - ciagle zapominam

    ślamazar

    --
    Wysłano z serwisu OnetNiusy: http://niusy.onet.pl


  • 7. Data: 2010-06-04 11:43:37
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: p...@p...onet.pl

    > a po przeliczeniu na odwrót do wyniku dodac (ox, oy)
    >

    ERRATA::

    x_1+=ox;
    y_1+=oy;
    x_2+=ox;
    y_2+=oy;



    --
    Wysłano z serwisu OnetNiusy: http://niusy.onet.pl


  • 8. Data: 2010-06-04 12:20:42
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: Dariusz Zolna <a...@u...com>


    ślamazar pisze:
    > acha - zapomniałem o inpucie - trzeba dodac jakis imput albo
    > dane wejsciowe podac w kodzie - druga uwaga ten kod z tej stronki zakłada
    > ze srodek okregu jest w (0, 0 ) jak nie to trzeba konce odcinka (i centrum
    > okregu niejako niejawnie) przed przeliczeniem przesunac o roznice np


    Dzięki, niestety nie działa. Przykładowe dane dla funkcji:
    x = 87, y = -33, r = 20
    x1 = 51, y1 = -77
    x2 = 115, y2 = -4

    Dla tych danych odcinek przecina okrąg w 2 miejscach. Jest to
    (teoretycznie) wykrywane przez algorytm, ale współrzędne punktów
    przecięcia wychodzą nieprawidłowe (x_1 = 137492, y_1 = 9015003).
    Czegoś w tych wzorach brakuje...

    Pozdrawiam,
    Dariusz Żołna

    int CircleLineIntersectPts(
    double x, double y, double r, double x1, double y1, double x2, double
    y2) //, int *xo1, int *yo1, int *xo2, int *yo2)
    {
    x1 -= x;
    y1 -= y;
    x2 -= x;
    y2 -= y;
    double dx = x2-x1;
    double dy = y2-y1;
    double dr = sqrt(dx*dx+dy*dy);
    double D = x1*y2-x2*y1;

    double delta = r*r*dr*dr-D*D;

    if(delta<0) return 0;
    if(delta==0) return 1;
    if(delta>0)
    {
    double x_1 =((D*dy+sgn(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr) + x;
    double x_2 =((D*dy-sgn(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr) + x;
    double y_1 =((-D*dy+abs(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr) + y;
    double y_2 =((-D*dy-abs(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr) + y;
    }
    return 2;
    }


  • 9. Data: 2010-06-04 12:38:47
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: Dariusz Zolna <a...@u...com>

    Dariusz Zolna pisze:
    > Czegoś w tych wzorach brakuje...

    Zabrakło nawiasów po znaku dzielenia wokół dr*dr, ale i tak gdzieś
    jeszcze jest błąd, bo wychodzą wartości spoza okręgu.

    Było:
    double x_1 =((D*dy+sgn(dy)*dx*sqrt(r*r*dr*dr-D*D))/dr*dr) + x;
    (itd..)

    Jest:
    double x_1 =((D*dy+sgn(dy)*dx*sqrt(r*r*dr*dr-D*D))/(dr*dr)) + x;
    (itd..)

    Pozdrawiam,
    Dariusz Żołna


  • 10. Data: 2010-06-04 14:59:00
    Temat: Re: Punkty przecięcia okręgu i odcinka
    Od: Tomasz Sowa <t...@t...NOSPAM.org>

    Dnia Fri, 04 Jun 2010 14:38:47 +0200, Dariusz Zolna napisał(a):

    > Dariusz Zolna pisze:
    >> Czegoś w tych wzorach brakuje...

    Już Wojciech Muła podpowiedział:

    > 1. znajdujesz równanie *parametryczne* prostej zawierające odcinek AB,
    > tzn. P(t) = A + t(B-A)
    > 2. podstawiasz do równania okręgu - otrzymujesz równanie kwadratowe
    > 3. znajdujesz miejsca zerowe
    > 4. akceptujesz tylko parametry z zakresu [0,1]

    a implementacja może wyglądać tak:
    http://tmp.slimaczek.pl/tmp/punkt_przeciecia.cpp

    --
    Tomek
    http://www.ttmath.org

strony : [ 1 ] . 2


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: