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

do góry

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

do góry

"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.

do góry

> 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

do góry

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

do góry

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

do góry

> 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

do góry

ś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;
}

do góry

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

do góry

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

do góry