[JS] Overlap herkennen

[Priet]

Eigenlijk is het een wiskundig probleempje, maar ik probeer het met Javascript op te lossen

Ik heb twee vierkanten. Van beide vierkanten heb ik x en y coördinaten van de linkerbovenhoek en de rechteronderhoek:

code:

vierkant1.topX
vierkant1.topY
vierkant1.bottomX
vierkant1.bottomY

vierkant2.topX
vierkant2.topY
vierkant2.bottomX
vierkant2.bottomY

Vierkant2 staat altijd op dezelfde plaats en heeft altijd dezelfde afmetingen. Oftewel: van vierkant2 zijn de coördinaten altijd gelijk, die van vierkant1 kunnen daarentegen wel variëren. Nu wil weten wanneer vierkant1 overlapt met vierkant2.

Ik had zelf zoiets als dit:

code:

var blnOverlap = (vierkant2.topX >= vierkant1.topX &&
            vierkant2.topY >= vierkant1.topY &&
            vierkant2.bottomX <= vierkant2.bottomX && 
            vierkant2.bottomY  <= vierkant2.bottomY);

Maar hiermee herken je alleen als vierkant1 vierkant2 volledig overlapt en niet als een gedeelte overlapt.

Mijn wiskunde laat me even in de steek. Volgens mij moet het niet zo moeilijk zijn, maar ik kom er niet meer op

Weet iemand hoe dit eenvoudig te berekenen is?

[Dido]

Als 1 van de vier punten van vierkant 1 binnen vierkant 2 ligt, heb je overlap.

X21 => X11 and X21 <= X12 and Y21 => Y11 and Y21 <= Y12
or
X21 => X11 and X21 <= X12 and Y22 => Y11 and Y22 <= Y12
or
X22 => X11 and X22 <= X12 and Y21 => Y11 and Y21 <= Y12
or
X22 => X11 and X22 <= X12 and Y22 => Y11 and Y22 <= Y12

dus, denk ik?

[ Voor 74% gewijzigd door Dido op 04-01-2007 15:28 ]

[killercow]

JE kunt in ieder geval gaan zoeken naar de term collision detection.

Dat helpt vast al een boel, en misschien dat je ook nog wat hebt aan de verschillende drag-drop implementaties die er op het net rond dwalen.

[Priet]

Dido schreef op donderdag 04 januari 2007 @ 15:24:
Als 1 van de vier punten van vierkant 1 binnen vierkant 2 ligt, heb je overlap.

X21 => X11 and X21 <= X12 and Y21 => Y11 and Y21 <= Y12
or
X21 => X11 and X21 <= X12 and Y22 => Y11 and Y22 <= Y12
or
X22 => X11 and X22 <= X12 and Y21 => Y11 and Y21 <= Y12
or
X22 => X11 and X22 <= X12 and Y22 => Y11 and Y22 <= Y12

dus, denk ik?

Dit komt in de buurt! Waar X21 is vierkant2.topX en Y12 is vierkant1.bottomY, etc?

Het werkt op één punt nog niet helemaal: vierkant1 moet altijd boven en/of onder én aan een van de zijkanten met vierkant2 overlappen.

Ik zoek het anders verder wel uit als ik weer wat helderder ben, want 't blijft wazig

[Dido]

Priet schreef op donderdag 04 januari 2007 @ 16:18:
Dit komt in de buurt! Waar X21 is vierkant2.topX en Y12 is vierkant1.bottomY, etc?

Yupz

Het werkt op één punt nog niet helemaal: vierkant1 moet altijd boven en/of onder én aan een van de zijkanten met vierkant2 overlappen.

Wat bedoel je hier precies mee? als je op de y-as overlapt en niet op de x-as, dan overlap je dus inderdaad niet.

Daarom mijn edit: je controlleert voor alle vier de hoekpunten of zowel het x-coordinaat als het y-coordinaat binnen de grenzen van vierkant 2 liggen: als dat voor minimaal 1 hoekpunt het geval is, heb je overlap.

Of wil je dat altijd twee keer twee zijden elkaar kruisen? (Dus bijvoorbeeld dat als het ene vierkant voledig in het andere ligt is dan niet geldig? - dan heb je een awijkende definiie van overlappen, maar met wat gevogel is ook dat natuurlijk te bouwen)

[ Voor 16% gewijzigd door Dido op 04-01-2007 16:29 ]

[Priet]

Dido schreef op donderdag 04 januari 2007 @ 16:27:Daarom mijn edit: je controlleert voor alle vier de hoekpunten of zowel het x-coordinaat als het y-coordinaat binnen de grenzen van vierkant 2 liggen: als dat voor minimaal 1 hoekpunt het geval is, heb je overlap.

Dat klinkt logisch

Wat bedoel je hier precies mee?

Met een plaatje wordt het duidelijker denk ik:

Dit gaat goed. Zoals je ziet valt vierkant1 onder en rechts er naast. In de gevallen met boven en/of onder en links en/of rechts gaat het altijd goed.

Hier gaat het fout:

vierkant1 valt nu slechts aan een zijde er naast, en dan gaat het fout.

Ik hoop dat m'n paint skills beter zijn dan m'n uitleg

[Dido]

Ok, helemaal gelijk natuurlijk. * Dido had zelf ff moeten painten

Aanname dat ten minste 1 hoekpunt binnen de gegeven rechthoek moest vallen is natuurlijk fout.

even kijken...

Veel simpeler aanpak aangezien je - neem ik dan aan - ervoor zorgt dat je top-coordinaten kleiner zijn dan je bottom coordinaten. Dan zou dit het al moeten doen:

vierkant1.TopX <= vierkant2.BottomX
and
vierkant1.TopY <= vierkant2.BottomY
and
vierkant1.BottomX => vierkant2.TopX
and
vierkant1.BottomY => vierkant2.TopY

Zo sluit je alle niet-overlappende situaties uit, volgens mij?

[ Voor 50% gewijzigd door Dido op 04-01-2007 16:56 ]

[tec]

geen overlap als:
top van 1 lager dan bottom van 2
bottom van 1 hoger dan top van 2
left van 1 groter dan right van 2
right van 1 kleiner dan left van 2

even snel, weet niet of het 100% klopt.

Makers van de game N hebben overigens een mooie verzameling tutorials over basic collision detection (tussen circels driehoeken vierkanten enz).

zie: http://www.harveycartel.org/metanet/tutorials/tutorialA.html

[ Voor 34% gewijzigd door tec op 04-01-2007 16:57 . Reden: url tutorials toegevoegd ]

[Dido]

tec: als twee mensen onafhankelijk op hetzelfde idee komen zou het zo maar eens kunnen kloppen

[tec]

But I beat you to it

[Dido]

Ik antwoordde dan ook vollediger
Trouwens, je hebt ge-edit na mij...

[tec]

Jaaa maaaaar!!!

(moehoaha zie reden van de edit )

[ Voor 50% gewijzigd door tec op 04-01-2007 17:03 ]

[Dido]

Die reden van de edit heb je zelf ingevuld

mgoed, genoeg slowchat, werkt het, Priet?

[Priet]

Helaas, het werkt nog niet helemaal. Situatie twee uit het foute voorbeeld lukt nog niet.

Inderdaad, alleen controleren op de hoekpunten is niet voldoende omdat de hoekpunten van vierkant (eigenlijk rechthoek) 1 er ook helemaal omheen kunnen liggen.

Ik zal even een testcase pagina maken om het te verduidelijken.

[DigiK-oz]

Met een standaard x/y assenkruis in gedachten :

((2.right > 1.left) & (2.left < 1.right))
&
((2.bottom < 1.top) & (2.top < 1.bottom))

Dido zegt eigenlijk hetzelfde, maar gaat er van uit dat je top-coördinaten kleiner zijn dan je bottom-coördinaten. En bij een standaard wiskundig assenkruis is dat nou net niet waar. Misschien dat het daarom nog niet werkt?

[Priet]

De linkerbovenhoek heeft als coördinaten 0,0.

Ik heb een testcase op http://www.peterriet.net/temp/selectie/ geplaatst.

In FF werkt het redelijk, IE 6 & 7 geven wazige script-fouten (ongeldig argument ) en selecteer bijna niets.

/Edit: de fouten in IE6 en 7 zijn nu verholpen. IE slikt style.backgroundColor = "inherit" niet De selectie gaat ook meteen een stuk beter nu in IE

[ Voor 27% gewijzigd door Priet op 04-01-2007 19:58 ]

[crisp]

IE snapt inherit sowieso niet, behalve voor een beperkt aantal css properties. Wat wel erg kwalijk is is het feit dat IE ook gewoon een JS error genereerd op het moment dat je die property-value via JS wilt toekennen, dat is compleet tegen alle specificaties in. Ik heb daar al eens een blogpost aan gewijd...

[Priet]

Ik heb de oplossing:

code:

var blnOverlap = (v1.topX <= v2.bottomX && 
                  v2.topX <= v1.bottomX && 
                  v1.topY <= v2.bottomY && 
                  v2.topY <= v1.bottomY);

Sim-pel Ere wie ere toekomt, ik ben er niet zelf achtergekomen

De testcase op http://www.peterriet.net/temp/selectie/ heb ik meteen bijgewerkt. Gelukkig zitten er nog meer fouten in, voornamelijk IE, dus ik heb nog wat te doen

[ Voor 6% gewijzigd door Priet op 05-01-2007 15:46 . Reden: Code netjes uitgelijnd ]