Brauche dringend Hilfe von C++ - Codern!

Übersicht

BlitzBasic

Allgemein

Gehe zu Seite 1, 2 Weiter

	Wanderer Betreff: Brauche dringend Hilfe von C++ - Codern!	Fr, Jan 14, 2005 17:59 Antworten mit Zitat
Ich bin auf der Suche nach einer Möglichkeit zum Testen, ob zwei Rechtecke sich überschneiden (auch, ob ein Rechteck komplett in einem anderen liegt!). Da jedes Rechteck durch Eckpunkte (xy) definiert wird, können diese auch 'rotiert' sein (womit RectsOverlap schon mal ausscheidet). Ich habe jetzt nach langem Suchen einen kleinen Code gefunden, der daß genau das lösen soll -allerdings ist es in C++ geschrieben, womit ich leider kaum etwas anfangen kann. Kennt sich hier jemand mit C++ aus und könnte das vielleicht irgendwie konvertieren? Sind wirklich nur wenige Zeilen -und im Code-Archiv fehlt eine solche Funktion noch dringend! Hier der C++ code: http://www.ragestorm.net/samples/CDRR.C
Mai Siehgnätschah gohs hiah.

Wanderer

Betreff: Brauche dringend Hilfe von C++ - Codern!

Fr, Jan 14, 2005 17:59
Antworten mit Zitat

Ich bin auf der Suche nach einer Möglichkeit zum Testen, ob zwei Rechtecke sich überschneiden (auch, ob ein Rechteck komplett in einem anderen liegt!). Da jedes Rechteck durch Eckpunkte (xy) definiert wird, können diese auch 'rotiert' sein (womit RectsOverlap schon mal ausscheidet).

Ich habe jetzt nach langem Suchen einen kleinen Code gefunden, der daß genau das lösen soll -allerdings ist es in C++ geschrieben, womit ich leider kaum etwas anfangen kann.

Kennt sich hier jemand mit C++ aus und könnte das vielleicht irgendwie konvertieren? Sind wirklich nur wenige Zeilen -und im Code-Archiv fehlt eine solche Funktion noch dringend!

Hier der C++ code: http://www.ragestorm.net/samples/CDRR.C

Mai Siehgnätschah gohs hiah.

	TheShadow Moderator	Fr, Jan 14, 2005 18:06 Antworten mit Zitat
wozu brauchst du da c++ cide? das sind einfache codes... einfach rotation-formel anwenden (ich will es nicht schon wider hier posten - ich werde dazu ein tut schreiben, damit es nie nie nie wider vorkommt!!!) rechteck in 2 dreiecke zerlegen und punkt-in-dreieck-algo ausführen... (code gibts hierzu auf blitzbase) dann noch auf linienkreuzung checken und fertig (gibts auch auf blitzbase)
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Fr, Jan 14, 2005 18:06
Antworten mit Zitat

wozu brauchst du da c++ cide? das sind einfache codes...

einfach rotation-formel anwenden (ich will es nicht schon wider hier posten - ich werde dazu ein tut schreiben, damit es nie nie nie wider vorkommt!!!)

rechteck in 2 dreiecke zerlegen und punkt-in-dreieck-algo ausführen... (code gibts hierzu auf blitzbase)

dann noch auf linienkreuzung checken und fertig (gibts auch auf blitzbase)

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	Wanderer	Fr, Jan 14, 2005 18:30 Antworten mit Zitat
Du meinst den Dot-in-Area Code dort? EDIT: Moment, da werden Banks angelegt -das kann ich in meinem Programm nicht machen - zig Objekte, Prüfung in jedem Frame usw... Alle Punkte checken, dann noch Linienkreuzung -ich hatte aber gehofft, das es vielleicht eine schnellere Methode gibt -denn jedesmal, wenn KEINE Überlappung stattfindet, rechnet die Funktion ALLE Punkte samt Linien durch.
Mai Siehgnätschah gohs hiah.

Wanderer

Fr, Jan 14, 2005 18:30
Antworten mit Zitat

Du meinst den Dot-in-Area Code dort?

EDIT: Moment, da werden Banks angelegt -das kann ich in meinem Programm nicht machen - zig Objekte, Prüfung in jedem Frame usw...

Alle Punkte checken, dann noch Linienkreuzung -ich hatte aber gehofft, das es vielleicht eine schnellere Methode gibt -denn jedesmal, wenn KEINE Überlappung stattfindet, rechnet die Funktion ALLE Punkte samt Linien durch.

Mai Siehgnätschah gohs hiah.

	stfighter01	Fr, Jan 14, 2005 19:46 Antworten mit Zitat
wenn es ein einfaches rechteck ist, dann schau einfach ob min. ein punkt im berech des anderen rechtecks liegt. und das geht ganz einfach: wobei: punkt 1= links oben und punkt4= rechts unten imbereich= false for i = 1 to 4 if rect1x[i]> rects2x[1] and rectt1x[i] < rect2x[4] and rect1y[i]> rects2y[1] and rectt1y[i] < rect2y[4] then imbereich= true endif next if imbereich= true print "rechteck1 ist im bereich von rechteck 2" endif
Denken hilft!

stfighter01

Fr, Jan 14, 2005 19:46
Antworten mit Zitat

wenn es ein einfaches rechteck ist, dann schau einfach ob min. ein punkt im berech des anderen rechtecks liegt.

und das geht ganz einfach:

wobei: punkt 1= links oben und punkt4= rechts unten

imbereich= false
for i = 1 to 4

if rect1x[i]> rects2x[1] and rectt1x[i] < rect2x[4] and
rect1y[i]> rects2y[1] and rectt1y[i] < rect2y[4] then

imbereich= true
endif

next

if imbereich= true
print "rechteck1 ist im bereich von rechteck 2"
endif

Denken hilft!

	Klaas	Fr, Jan 14, 2005 20:07 Antworten mit Zitat
@stfighter01: Das ist nicht zuverlässig ! Stell dir mal 2 gleiche quadrate übereinander vor und drehe dann eines um 45grad. Dann sind alle Punkte ausserhalb des anderen quadrates. Mann muß also zusätzlich die linienkreutzung berechnen. optimierungsidee: berechne die maximal ausdehnung zum drehzentrum (stell dir einen kreis um das quadrat vor. Der entfernteste punkt des quadrates zum drehzentrum ist der radius). Wenn 2 quadrate sich nicht mit ihren umfangskreis berühren dann braucht man auch nicht auf überlappung zu testen! also: mag# = sqr(deltaX#^2 + deltaY#^2) if mag < (radius1 + radius2) then ;abstand der quads ist geringer als ihr kombinierter radius ;hier muß genauer geschaut werden check_intersetion() else ;berechnung nicht notwendig end if

Klaas

Fr, Jan 14, 2005 20:07
Antworten mit Zitat

@stfighter01:
Das ist nicht zuverlässig ! Stell dir mal 2 gleiche quadrate übereinander vor und drehe dann eines um 45grad. Dann sind alle Punkte ausserhalb des anderen quadrates. Mann muß also zusätzlich die linienkreutzung berechnen.

optimierungsidee:
berechne die maximal ausdehnung zum drehzentrum (stell dir einen kreis um das quadrat vor. Der entfernteste punkt des quadrates zum drehzentrum ist der radius). Wenn 2 quadrate sich nicht mit ihren umfangskreis berühren dann braucht man auch nicht auf überlappung zu testen!
also:

mag# = sqr(deltaX#^2 + deltaY#^2)
if mag < (radius1 + radius2) then
;abstand der quads ist geringer als ihr kombinierter radius
;hier muß genauer geschaut werden
check_intersetion()
else
;berechnung nicht notwendig
end if

	stfighter01	Fr, Jan 14, 2005 23:57 Antworten mit Zitat
sorry, hätt ich dazuschreiben sollen
Denken hilft!

stfighter01

Fr, Jan 14, 2005 23:57
Antworten mit Zitat

sorry, hätt ich dazuschreiben sollen Embarassed

Denken hilft!

	Wanderer	Sa, Jan 15, 2005 13:07 Antworten mit Zitat
@Klaas: gute Idee, zuerst einmal den Radius zu testen. Ich werde das mal einfügen -aber generell scheint wohl kein Weg daran vorbeizugehen, dass man in jedem Fall hierfür a) Testen aller Punkte (ob inerhalb des anderen Quadrats) = 8 Tests b) Testen aller Linien mit allen Linien des anderen Quadrats = 16 Tests braucht, oder? Einen anderen Weg gibt es nicht?
Mai Siehgnätschah gohs hiah.

Wanderer

Sa, Jan 15, 2005 13:07
Antworten mit Zitat

@Klaas: gute Idee, zuerst einmal den Radius zu testen. Ich werde das mal einfügen -aber generell scheint wohl kein Weg daran vorbeizugehen, dass man in jedem Fall hierfür

a) Testen aller Punkte (ob inerhalb des anderen Quadrats) = 8 Tests
b) Testen aller Linien mit allen Linien des anderen Quadrats = 16 Tests

braucht, oder? Einen anderen Weg gibt es nicht?

Mai Siehgnätschah gohs hiah.

	Klaas	Sa, Jan 15, 2005 17:07 Antworten mit Zitat
also, ich glaub man kann einige Fälle ausschließen. Wenn alle Punkte ausserhalb des jeweils anderen Quadrates liegen dann müssen alle Seiten sich kreutzen ... oder ? Wenn das der Fall ist, dann muß man nachdem die 8 Punkte getestet wurden nur eine einzige Linie (gegen 4 des anderen Quadrates) checken. Sollte die sich dann nicht kreutzen kann man sagen das sie sich nicht überlappen. Korriegiert mich bitte wenn das falsch ist, komme aber beim überlegen zu keinem Fall wo dies anderst ist.

Klaas

Sa, Jan 15, 2005 17:07
Antworten mit Zitat

also, ich glaub man kann einige Fälle ausschließen.

Wenn alle Punkte ausserhalb des jeweils anderen Quadrates liegen dann müssen alle Seiten sich kreutzen ... oder ?
Wenn das der Fall ist, dann muß man nachdem die 8 Punkte getestet wurden nur eine einzige Linie (gegen 4 des anderen Quadrates) checken. Sollte die sich dann nicht kreutzen kann man sagen das sie sich nicht überlappen.

Korriegiert mich bitte wenn das falsch ist, komme aber beim überlegen zu keinem Fall wo dies anderst ist.

	stfighter01	Sa, Jan 15, 2005 21:11 Antworten mit Zitat
jetzt mach ich mich auch noch mal nützlich mag= deltax^2+deltay^2 if mag < (radius1+radius2)^2 then checkgenauer() endif damit fällt sqr weg sqr ist bei mir 3 mal so langsam wie ^2 und bei manch anderen warscheinlich sogar noch viel viel langsamer
Denken hilft!

stfighter01

Sa, Jan 15, 2005 21:11
Antworten mit Zitat

jetzt mach ich mich auch noch mal nützlich Laughing

mag= deltax^2+deltay^2

if mag < (radius1+radius2)^2 then
checkgenauer()
endif

damit fällt sqr weg
sqr ist bei mir 3 mal so langsam wie ^2 und bei manch anderen warscheinlich sogar noch viel viel langsamer

Denken hilft!

	Klaas	So, Jan 16, 2005 1:15 Antworten mit Zitat
... ja, aber das hat dann doch nichts mehr mit dem Abstand zu tun !!!!

Klaas

So, Jan 16, 2005 1:15
Antworten mit Zitat

... ja, aber das hat dann doch nichts mehr mit dem Abstand zu tun !!!!

	Wanderer	So, Jan 16, 2005 6:34 Antworten mit Zitat
Hier mal ein paar Beispiele, welche Situationen auftreten können: Zitat: Wenn alle Punkte ausserhalb des jeweils anderen Quadrates liegen dann müssen alle Seiten sich kreutzen ... oder ? Kommt auch darauf an, von welchem Rechteck aus man das sieht (siehe Bild) - aber woher soll man wissen, welches man zuerst checkt?
Mai Siehgnätschah gohs hiah.

Wanderer

So, Jan 16, 2005 6:34
Antworten mit Zitat

Hier mal ein paar Beispiele, welche Situationen auftreten können:
user posted image

Zitat:

Wenn alle Punkte ausserhalb des jeweils anderen Quadrates liegen dann müssen alle Seiten sich kreutzen ... oder ?

Kommt auch darauf an, von welchem Rechteck aus man das sieht (siehe Bild) - aber woher soll man wissen, welches man zuerst checkt?

Mai Siehgnätschah gohs hiah.

	Plasma(alt) Betreff: ein arger hack ist z.b	So, Jan 16, 2005 8:24 Antworten mit Zitat
immer das kleinere viereck testen. ... einfach rauszukriegen von diesem dann jeweils die eckpunkte bestimmen und gugen ob der pixel über den eckpunkten ne andere farbe hat ........... also die des anderen rects ... das problem ist du musst erst zeichnen ....
DIV is dead !

Plasma(alt)

Betreff: ein arger hack ist z.b

So, Jan 16, 2005 8:24
Antworten mit Zitat

immer das kleinere viereck testen. ... einfach rauszukriegen
von diesem dann jeweils die eckpunkte bestimmen und gugen ob
der pixel über den eckpunkten ne andere farbe hat ...........
also die des anderen rects ...
das problem ist du musst erst zeichnen ....

DIV is dead !

	hot-bit Gast	So, Jan 16, 2005 11:01 Antworten mit Zitat
Hoi. Warum zuerst zeichnen ? Jeder Punkt hat doch seine Koordinaten ... Toni

hot-bit

Gast

So, Jan 16, 2005 11:01
Antworten mit Zitat

Hoi.

Warum zuerst zeichnen ?

Jeder Punkt hat doch seine Koordinaten ...

Toni

	Plasma(alt) Betreff: ja hotte	So, Jan 16, 2005 17:33 Antworten mit Zitat
dann is es ja wieder mathe
DIV is dead !

Plasma(alt)

Betreff: ja hotte

So, Jan 16, 2005 17:33
Antworten mit Zitat

dann is es ja wieder mathe Twisted Evil

DIV is dead !

	stfighter01	So, Jan 16, 2005 17:58 Antworten mit Zitat
@klaas mag ist bei mir zwar das quadrat des abstandes, aber es ist immer noch eine funktion des abstandes. und die vergleiche ich einfach mir dem quadrat des minimalabstandes. ist auch nicht falsch oder?
Denken hilft!

stfighter01

So, Jan 16, 2005 17:58
Antworten mit Zitat

@klaas
mag ist bei mir zwar das quadrat des abstandes, aber es ist immer noch eine funktion des abstandes.
und die vergleiche ich einfach mir dem quadrat des minimalabstandes.
ist auch nicht falsch oder?

Denken hilft!

	stfighter01	So, Jan 16, 2005 18:13 Antworten mit Zitat
@wanderer ich will ja nicht den spass verderben, aber mach ma dagegen nichts? in der bewegung sollte das aber eher nicht so leicht zustande kommen. mfg stfighter
Denken hilft!

stfighter01

So, Jan 16, 2005 18:13
Antworten mit Zitat

@wanderer
ich will ja nicht den spass verderben, aber mach ma dagegen nichts?

user posted image

in der bewegung sollte das aber eher nicht so leicht zustande kommen.

mfg stfighter

Denken hilft!

	Klaas	So, Jan 16, 2005 22:09 Antworten mit Zitat
@stfighter01: sorry, hatte das "^2" einfach übersehen ! Da hast du natürlich Recht. man muß 8 Punkte abchecken, aber wenn die nicht zutreffen dann muß man glaub ich nur eine Linie gegen die 4 des anderen Quadrates testen. Dann kommt man von 8 und 16 auf immerhin 8 und 4 runter. Das ist ja nicht unerheblich. Zusammen mit der Radius-Optimierung sollte das einen sehr starken Performance-Sprung ausmachen.

Klaas

So, Jan 16, 2005 22:09
Antworten mit Zitat

@stfighter01: sorry, hatte das "^2" einfach übersehen ! Da hast du natürlich Recht.

man muß 8 Punkte abchecken, aber wenn die nicht zutreffen dann muß man glaub ich nur eine Linie gegen die 4 des anderen Quadrates testen.

Dann kommt man von 8 und 16 auf immerhin 8 und 4 runter. Das ist ja nicht unerheblich. Zusammen mit der Radius-Optimierung sollte das einen sehr starken Performance-Sprung ausmachen.

	Wanderer	Mo, Jan 17, 2005 0:32 Antworten mit Zitat
Okay, aber wie errechne ich den Abstand zwischen zwei Rechtecken möglichst schnell und effizient? Es sind ja keine Quadrate, wo man einen einfachen Radius nehmen kann. Hier wäre es eine Ellipse -oder doch ein Radius, aber dann mit Umfang des am weitesten von der Mitte des Rechtecks entfernten Punkts -aber allein den herauszufinden, kostet ja auch wieder extra 8 Sqr's (und die will ich immer vermeiden, wie Hölle, weil grottenlahm)...
Mai Siehgnätschah gohs hiah.

Wanderer

Mo, Jan 17, 2005 0:32
Antworten mit Zitat

Okay, aber wie errechne ich den Abstand zwischen zwei Rechtecken möglichst schnell und effizient? Es sind ja keine Quadrate, wo man einen einfachen Radius nehmen kann. Hier wäre es eine Ellipse -oder doch ein Radius, aber dann mit Umfang des am weitesten von der Mitte des Rechtecks entfernten Punkts -aber allein den herauszufinden, kostet ja auch wieder extra 8 Sqr's (und die will ich immer vermeiden, wie Hölle, weil grottenlahm)... Sad

Mai Siehgnätschah gohs hiah.

	stfighter01	Mo, Jan 17, 2005 0:57 Antworten mit Zitat
du wirst ja irgendeinen mittelpunkt für dein reckteck definiert haben, sonst kannst dus ja nicht rotieren und bewegen. der weg vom äussersten punkt von einer mitte aus (berechnest du mit pytagoras) gibt den radius an den du überpfrüfen musst die radien kannst du vorberechnen, also wird das ganze sehr fix vonstatten gehen.
Denken hilft!

stfighter01

Mo, Jan 17, 2005 0:57
Antworten mit Zitat

du wirst ja irgendeinen mittelpunkt für dein reckteck definiert haben, sonst kannst dus ja nicht rotieren und bewegen.
der weg vom äussersten punkt von einer mitte aus (berechnest du mit pytagoras) gibt den radius an den du überpfrüfen musst
die radien kannst du vorberechnen, also wird das ganze sehr fix vonstatten gehen.

Denken hilft!

	Klaas	Mo, Jan 17, 2005 1:07 Antworten mit Zitat
ich muß mich nochmal korriegieren: Zitat: man muß 8 Punkte abchecken, aber wenn die nicht zutreffen dann muß man glaub ich nur eine Linie gegen die 4 des anderen Quadrates testen. Dann kommt man von 8 und 16 auf immerhin 8 und 4 runter. Das ist ja nicht unerheblich. Zusammen mit der Radius-Optimierung sollte das einen sehr starken Performance-Sprung ausmachen. wie man auf stfighter01's zeichnung sieht muß man natürlich minimal 2 linien auf jeweils 4 testen und zwar 2 zusamenhängende Linien.

Klaas

Mo, Jan 17, 2005 1:07
Antworten mit Zitat

ich muß mich nochmal korriegieren:

Zitat:

man muß 8 Punkte abchecken, aber wenn die nicht zutreffen dann muß man glaub ich nur eine Linie gegen die 4 des anderen Quadrates testen.

Dann kommt man von 8 und 16 auf immerhin 8 und 4 runter. Das ist ja nicht unerheblich. Zusammen mit der Radius-Optimierung sollte das einen sehr starken Performance-Sprung ausmachen.

wie man auf stfighter01's zeichnung sieht muß man natürlich minimal 2 linien auf jeweils 4 testen und zwar 2 zusamenhängende Linien.

Gehe zu Seite 1, 2 Weiter

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Brauche dringend Hilfe von C++ - Codern!

Betreff: Brauche dringend Hilfe von C++ - Codern!

Betreff: ein arger hack ist z.b

hot-bit

Betreff: ja hotte