The University of Pedagogy - IT class

Diễn Đàn Lớp Công nghệ thông tin - Trường Đại Học Sư Phạm TP.HCM
 
Trang ChínhTrang Chính  Trợ giúpTrợ giúp  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Thành viênThành viên  NhómNhóm  Đăng NhậpĐăng Nhập  

Share | 
 

 Giao điểm của đường tròn và đường thẳng

Go down 
Tác giảThông điệp
mr.lemon
Thành viên thứ thiệt
Thành viên thứ thiệt
avatar

Tổng số bài gửi : 14
Age : 31
Registration date : 09/06/2007

Bài gửiTiêu đề: Giao điểm của đường tròn và đường thẳng   Sat Sep 29, 2007 8:56 pm

Bạn nào có thuật toán tìm giao điểm cuả đường tròn và đường thẳng send cho mình nha.
số là thế này: mình có đoạn thẳng AB và pt đường tròn. bi h mình muốn bít . cái ông đường tròn đó có cắt đường thẳng không?
Về Đầu Trang Go down
Xem lý lịch thành viên
cuongtq87
Admin
Admin
avatar

Tổng số bài gửi : 96
Registration date : 29/05/2007

Bài gửiTiêu đề: Re: Giao điểm của đường tròn và đường thẳng   Wed Oct 03, 2007 6:23 am

Cái này chắc là dựa vào công thức toán học mà làm thui. Lấy tập Hình học giải tích ra xem lại thử coi. Tui nhớ hình như có đó.

_________________
Blog hay nè : http://360.yahoo.com/cuongtqtq87
Về Đầu Trang Go down
Xem lý lịch thành viên http://itclass.forummotion.com
mr.lemon
Thành viên thứ thiệt
Thành viên thứ thiệt
avatar

Tổng số bài gửi : 14
Age : 31
Registration date : 09/06/2007

Bài gửiTiêu đề: Re: Giao điểm của đường tròn và đường thẳng   Thu Oct 04, 2007 7:37 am

Mình đã tìm ra thuật toán. thế này: đầu tiên viết pt đường thẳng AB (theo tham số t). thế pt đó vào pt đường tròn nếu tìm được t thì thay vào pt AB ta tìm được toạ độ giao điểm. xong rồi kiêm tra xem toạ độ này có năm trong đoaạn thẳng AB hay ko. nếu có thì CẮT, cái naỳ nếu giải trong giấy thi quá dễ dàng. nhưng đưa cho computer no giai. ko dễ chút nào. mình post bài này lên. vì đây là một trong những kiến thức cơ bản để học môn Dồ Hoạ Máy Tính.
có một bài toán liên quan đến phần này các bạn tham khảo:
"cho tam giác ABC và một điểm M không nằn trên ba cạnh của tam giác. vít ct tìm số lớn nhất K sao cho đường tròn (M,K) không cắt bất cứ cạnh nào, và không chứa tam giác"
tríchL Đề thi Olympic tin hoc khối không chuyên 2002
Input.txt: toa độ lần lượt 4 diểm A, B, C, M
Output.txt: R
------------------------------
ý tưởng thuật toán: tính khoảng cách từ M đến A, B, C và 3 đoạn thẳng AB,Ac,Bc
ta có 6 R. mỗi R ta kiểm tra xem (M,R) ko cắt 3 cạnh tam giác và ko chứa A, B, C thì đó là kết quả cần tim
------------------------------
#include<fstream>
#include<cmath>

using namespace std;

const char fi[] = "TRIANGLE.INP";
const char fo[] = "TRIANGLE.OUT";

struct point
{
double x,y;
};

point A, B, C, M;
double dis;

void readfile()
{
ifstream fin;
fin.open(fi);
fin>>A.x>>A.y;
fin>>B.x>>B.y;
fin>>C.x>>C.y;
fin>>M.x>>M.y;
fin.close();
}

void writefile()
{
ofstream fout;
fout.open(fo);
int idis = dis *10;
dis = (double)idis/10;
fout<<(double)dis;
fout.close();
}

double distance_point_point( point A, point B) // khoang cach hai diem
{
return sqrt( pow(A.x - B.x, 2) + pow(A.y - B.y, 2) );
}

bool point_in_segment_line(point M, point A, point B) // kiem tra diem M co thuoc doan AB khong
{
double nho = 0.000000001;
return( distance_point_point(A,M) + distance_point_point(M,B)
- distance_point_point(A,B) <= nho );
}

double distance_point_segment_line( point M, point A, point B )
{
point v,gd;
float a, b, c,t;

// v la vec to chi phuong
v.x = -1*(A.y - B.y);
v.y = A.x - B.x;

// Phuong trinh duong thang AB: ax + by +c = 0
a = A.y - B.y;
b = B.x - A.x;
c = A.x*B.y - A.y*B.x;

float ms = a*v.x+b*v.y;
if (ms!=0)
t = -1*( (c+a*M.x+b*M.y)/(ms) );

// gd la giao diem cua duong cao ke tu M xuong duong thang AB
gd.x = M.x + t*v.x;
gd.y = M.y + t*v.y;

if( point_in_segment_line(gd, A, B) )
{
return distance_point_point(gd, M);
}

float dis1, dis2;
dis1 = distance_point_point(A,M);
dis2 = distance_point_point(B,M);

if( dis1 > dis2 )
{
dis1 = dis2;
}
return dis1;
}



bool point_in_circle( point M, point O, double R ) // kiem tra diem M co nam trong duong tron khong
{
return(pow((M.x - O.x),2) + pow((M.y - O.y),2) - pow(R,2) <= 0);
}

// kiem tra xem doan thang AB co cat duong tron khong?
bool segment_cut_circle( point A, point B, point O, double R )
{
if( distance_point_segment_line( O, A, B ) >= R )
return 0;
// tim toa do giao diem
point v, gd;
v.x = A.x - B.x;
v.y = A.y - B.y;
double t1,t2,a, b, c, delta_phay; // b: b phay
a = v.x*v.x + v.y*v.y;
b = A.x*v.x - v.x*O.x + A.y*v.y - v.y*O.y;
c = A.x*A.x + A.y*A.y + O.x*O.x + O.y*O.y - R*R - 2*A.x*O.x -2*A.y*O.y;

delta_phay = b*b - a*c;
if( delta_phay>0 )
{
t1 = (-1*b +sqrt(delta_phay))/a;
gd.x = A.x + v.x*t1;
gd.y = A.y + v.y*t1;
if( point_in_segment_line(gd, A, B) )
return 1;

t2 = (-1*b -sqrt(delta_phay))/a;
gd.x = A.x + v.x*t2;
gd.y = A.y + v.y*t2;
if( point_in_segment_line(gd, A, B) )
return 1;
}
return 0;
}

void process() // xu ly
{
dis = distance_point_point( M, A );

///////////////////////////// kiem tra diem

if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(A,C,M,dis))
&& (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(B,M,dis) && (!point_in_circle(C,M,dis)))
)
return;
//
dis = distance_point_point( M, B );
if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(A,C,M,dis))
&& (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(A,M,dis) && (!point_in_circle(C,M,dis)))
)
return;
//
dis = distance_point_point( M, C );
if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(A,C,M,dis))
&& (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(B,M,dis) && (!point_in_circle(A,M,dis)))
)
return;

///////////////////////////// kiem tra doan

dis = distance_point_segment_line( M, A, B );
if( (!segment_cut_circle(A,C,M,dis)) && (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(A,M,dis))&& (!point_in_circle(B,M,dis))&& (!point_in_circle(C,M,dis))
)
return;
//
dis = distance_point_segment_line( M, A, C );
if( (!segment_cut_circle(A,B,M,dis)) && (!segment_cut_circle(B,C,M,dis))
&& (!point_in_circle(A,M,dis))&& (!point_in_circle(B,M,dis))&& (!point_in_circle(C,M,dis))
)
return;
//
dis = distance_point_segment_line( M, B, C );
if( (!segment_cut_circle(A,C,M,dis)) && (!segment_cut_circle(A,B,M,dis))
&& (!point_in_circle(A,M,dis))&& (!point_in_circle(B,M,dis))&& (!point_in_circle(C,M,dis))
)
return;
dis = -1;
}

void main()
{
readfile();
process();
writefile();
}
Về Đầu Trang Go down
Xem lý lịch thành viên
phong
Thành viên năng nổ
Thành viên năng nổ
avatar

Tổng số bài gửi : 60
Registration date : 15/09/2007

Bài gửiTiêu đề: Re: Giao điểm của đường tròn và đường thẳng   Fri Oct 05, 2007 12:00 am

hic,Sad nhìn vô hổng hiểu gì hết trơn hết affraid
Về Đầu Trang Go down
Xem lý lịch thành viên
Sponsored content




Bài gửiTiêu đề: Re: Giao điểm của đường tròn và đường thẳng   

Về Đầu Trang Go down
 
Giao điểm của đường tròn và đường thẳng
Về Đầu Trang 
Trang 1 trong tổng số 1 trang
 Similar topics
-
» Giao lưu 2 Khóa 86 và 87TuNghia Nhân Ngày 20-11
» 101 bài tiếng anh giao tiếp bằng cơ bản rất hay
» Đèn giao thông dùng PLC S7-300
» Giao nhận hàng rời bằng cách nào?
» Thông báo tuyển sinh lớp tiếng anh giao tiếp chuyên ngành hàng hải

Permissions in this forum:Bạn không có quyền trả lời bài viết
The University of Pedagogy - IT class :: Câu Lạc Bộ Tin Học :: Thủ Thuật-
Chuyển đến