C++ iki kesimin kesişip geçmediğini belirlemek için yordam

Question

Son zamanlarda bilişimsel geometriyle biraz çalışıyorum ve iki çizgi parçasının kesişip kesişmediğini kontrol etmenin bir yolunu bulmaya çalışıyorum. Bunu belirlemek için saat yönünün tersi yönde (kısaca CCW) kullanabileceğimi düşündüm.

struct point { double x, y }; 

double CCW(point a, point b, point c) 
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); } 

int intersect(point a, point b, point c, point d) 
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); } 

Yukarıdaki kod girdiğim test durumları için çalıştı ve oldukça okunaklı ve uygulamak çok kolay: İşte benim kod öylesine uzaktır. Ancak web'de arama yaptıktan sonra segment kesişim sorununu çözmenin başka bir yolunu buldum. Kod benimkine benziyor, fakat benim uygulamamın atlattığı bazı if ifadelerine sahip. İşte kod:

struct line { point s, e; }; 

int middle(int a, int b, int c) { 
    int t;  
    if (a > b) { 
    t = a; 
    a = b; 
    b = t; 
    } 
    if (a <= c && c <= b) return 1; 
    return 0; 
} 

int intersect(line a, line b) { 
    if ((CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0) && 
    (CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0)) return 1; 

    if (CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y)) return 1; 
    if (CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y)) return 1; 
    if (CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y)) return 1; 
    if (CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y)) return 1; 

    return 0; 
} 

birisi iki uygulamaları arasındaki fark olan açıklayabilir misiniz ve hangi kullanmak daha güvenlidir? Şimdiden teşekkürler.

Answer 1

Bulduğunuz işlev, satır bölümlerinin aynı satırda bulunduğu durumu da kontrol etmektir. Bu durumda, iki çizgi parçasının örtüşüp örtüşmediğini bulmak tek boyutlu bir problem haline gelir. Bu durumda kodunuz yanlış gelecektir. Bunun tercih edilip edilmeyeceği uygulamaya bağlı.

Örnek:

Örnek:

point a={1,0}, b={3,0}, c={2,0}, d={2,3}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true 

bir hat parçasının son nokta diğer çizgi parçası boyunca uzandığı yerde, bulunan işlevi de durumlarda bakar

point a={1,0}, b={3,0}, c={2,0}, d={4,0}; 

intersect(a,b,c,d); // your function will return false, 
        // but the one you found will return true