Witam. Na wstępie zaznaczę, że walczę różnymi metodami z tą funkcją od paru dni. Potrzebuję rzeczowej odpowiedzi.
Są dwa prostokąty opisane przez punkty srodkowe cx, cy, punkty krawędziowe left, right, top, bottom oraz dla ułatwienia posiadają parametry width oraz height.
Jaki warunek musi zostać spełniony by się przecinaly?
Mój błędny kod:
bool intersect;
if(
abs(R1x-R2x) < (R1w+R2w)/2 &&
abs(R1y-R2y) < (R1h+R2h)/2
)
intersect = true;
else
intersect = false;
Jest takie ćwiczenia algorytmiczne, intersekcja na jednej osi. Wydaje się że trzeba 4-6 porównań, po głębszej analizie okazuje się, że wystarczają dwa porównania (bez wartości bezwzglednej)
Pomedytuj.
Bartosz Bogusławski napisał(a):
Są dwa prostokąty opisane przez punkty srodkowe cx, cy, punkty krawędziowe left, right, top, bottom oraz dla ułatwienia posiadają parametry width oraz height.
Cos nie gra.
Za dużo warunków, wiec mogą być sprzeczne.
Jakie jest prawdziwe zadanie?
Mi wyszły 4 porównania :(
object HelloWorld extends App {
final case class Rectangle(x: Int, y: Int, w: Int, h: Int)
def intersec(r1: Rectangle, r2: Rectangle) = intersectHalf(r1, r2) && intersectHalf(r2, r1)
def intersectHalf(r1: Rectangle, r2: Rectangle) = (r1.x < r2.x + r2.w) && (r1.y < r2.y + r2.h)
val r11 = Rectangle(0, 0, 2, 2)
val r12 = Rectangle(1, 1, 2, 2)
println(intersec(r11, r12))
val r21 = Rectangle(0, 0, 2, 2)
val r22 = Rectangle(0, 2, 2, 2)
println(intersec(r21, r22))
val r31 = Rectangle(0, 0, 2, 2)
val r32 = Rectangle(0, 4, 2, 2)
println(intersec(r31, r32))
}
Sorry, nie umiem C++ więc jest w pseudokodzie :D
Bartosz Bogusławski napisał(a):
Jaki warunek musi zostać spełniony by się przecinaly?
Jeden ze sposobów - możesz porównać kolizje cząstkowo na dwóch współrzędnych (to się nazywa fachowo zdaje się projekcja na oś współrzędnych?). Tj. sprawdzasz czy odcinki się przecinają na poszczególnych osiach.
jak oba warunki są spełnione, to jest kolizja.
Jeśli R1x i R2x są liczone od środka, to liczysz odległości środków od siebie. A powinieneś bardziej liczyć odległość od siebie skrajnych punktów (wg tego sposobu, o którym pisałem):
czyli jakaś operacja max i min będzie potrzebna (nie wiesz, który prostokąt jest po lewej, a który po prawej stronie, poza tym jeden może być w środku drugiego, więc to też nie musi o niczym świadczyć).
Bartosz Bogusławski napisał(a):
Są dwa prostokąty opisane przez punkty srodkowe cx, cy, punkty krawędziowe left, right, top, bottom oraz dla ułatwienia posiadają parametry width oraz height.
C czy C++ czy inny język nie istotne, najpierw powinieneś sobie wszystko sobie zorganizować dane w jakiś rozsądny sposób.
struct RectData {
double left, right, top, bottom;
};
int RectAreIntersecting(struct RectData a, struct RectData b);
Zakładając, że dane są konsystentne (t/z: left<=rigth top<=bottom), wszystko jest proste:
int RectAreIntersecting(struct RectData a, struct RectData b)
{
return a.right >= b.left && b.right >= a.left &&
a.bottom >= b.top && b.bottom >= a.top;
}
Masz całkiem sporo danych. Jeśli chciałbyś wykorzystać długość i szerokość i nie masz rotacji
if (left_A + W_A < left_B || left_B + W_B < left_A || bottom_A + H_A < bottom_B || bottom_B + H_B < bottom_A)
// nie przecinaja sie
else
// przecinaja sie
I jeszcze jedno, jeżeli jeden prostokąt znajduje się całkowicie w środku drugiego, to liczysz to jako przecięcie? Bo jeśli tak, to lepiej by pasowało opisać to jako zachodzenie na siebie. W ogóle, po angielsku są do tego zgrabne słowa intersection oraz overlap i wszystko jest jasne, a po polsku to jakoś dziwnie - przecięcie i zachodzenie na siebie :D
ja ostatnio coś takiego napisałem (w JS)
const horizontal = Math.max(platform.x + platform.width, obj.x + obj.width) - Math.min(platform.x, obj.x) < (obj.width + platform.width);
const vertical = Math.max(platform.y + platform.height, obj.y + obj.height) - Math.min(platform.y, obj.y) < (obj.height + platform.height);
return horizontal && vertical;
gdzie platform - pierwszy prostokąt
obj - drugi prostokąt
(bo to początek platformówki)
no i właściwości x oraz y oznaczają u mnie róg (lewy górny, zakładam, że x idzie w prawo, y do dołu), a nie środek.
Czy w swoim kodzie poprawiłeś te błędy, co miałeś? (bo tam nawiasy się nie zgadzały i była spacja & & - post poprawiłeś, ale czy w programie też naniosłeś zmiany?
Bo skonwertowałem twój kod z pierwszego posta na JS i działa:
https://jsfiddle.net/pxkn179q/
Bo to ma sens w sumie. Liczyć od środków też się da.
Jeśli ci to nie działa, to przypuszczalnie problem jest gdzieś poza tym kodem, gdzieś w reszcie aplikacji. Może te liczby masz nieprawidłowe już wcześniej i masz dobre obliczenia, ale na złych liczbach?
Dodam jeszcze, że prostokąt można traktować jako dwa przedziały - przedział współrzędnych X i Y. Sprawdzenie przecinania się prostokątów sprowadza się wtedy do sprawdzenia, czy obie pary przedziałów mają część wspólną. Analogicznie można znaleźć to przecięcie, a nie tylko wykazać, że istnieje. Można to ładnie zapisać w Javie - klasa "przedział" i klasa "prostokąt" zawierająca dwa przedziały, oczywiście z odpowiednimi metodami.
Bartosz Bogusławski napisał(a):
Jaki warunek musi zostać spełniony by się przecinaly?
Przede wszystkim proste równoległe nie powinny się zbiegać.
To dość powszechny problem w systemach wykrywania kolizji, słowo klucz to AABB (axis-aligned bounding box), wyszukiwanie po tym prowadzi szybko do linków pokroju https://gamedev.stackexchange.com/questions/586/what-is-the-fastest-way-to-work-out-2d-bounding-box-intersection
Real-Time Collision Detection podaje kod:
int TestAABBAABB(AABB a, AABB b)
{
// Exit with no intersection if separated along an axis
if (a.max[0] < b.min[0] || a.min[0] > b.max[0]) return 0;
if (a.max[1] < b.min[1] || a.min[1] > b.max[1]) return 0;
if (a.max[2] < b.min[2] || a.min[2] > b.max[2]) return 0;
// Overlapping on all axes means AABBs are intersecting
return 1;
}
Gdzie min to lewy górny, a max prawy dolny róg.