### Show differencesHistory of post edits

### #6Aphton

Posted 23 January 2013 - 11:30 AM

We have two lines f and g f: A + i * AB g: C + j * CD First, we need to find out, whether they are parallel If they are parallel, then their slope must be equal parallel: AB.Y/AB.X == CD.Y/CD.Y If they are parallel, return false At this point, we know they are not paralle and two non-parallel lines in 2D intersect so this is valid: A + i * AB = C + j * CD We can rewrite that to: I. A.X + i * AB.X = C.X + j * CD.X II. A.Y + i * AB.Y = C.Y + j * CD.Y We determine j in I: j = (A.X + i*AB.X - C.X) / CD.X now we can substituate j in II II. A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y After some tranformation (you can skip this): > A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y > A.Y + i*AB.Y = C.Y + (A.X/CD.X + i*AB.X/CD.X - C.X/ CD.X) * CD.Y > A.Y + i*AB.Y = C.Y + A.X*CD.Y/CD.X + i*AB.X*CD.Y/CD.X - C.X*CD.Y/ CD.X > i*AB.Y - i*AB.X*CD.Y/CD.X = C.Y + A.X*CD.Y/CD.X - C.X*CD.Y/ CD.X - A.Y > i*(AB.Y - AB.X*CD.Y/CD.X) = C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y > i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X) We get: i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X) We determined j previously. We simply insert the value of i into that formula and get thevalue for j. We need both to determine, whether they really intersect As for the intersection, since we have i, we can calculate the point of intersection by inserting it into f: A + i * AB return InRange(i, 0, 1) && InRange(j, 0, 1)-> if both i and j are in that range, they intersect!

You have to extrude AB so that it intersects with the square around it 100%. Then you have to execute that above for each side of the square!

### #5Aphton

Posted 23 January 2013 - 11:28 AM

<p> </p>

<p> </p>

<p>

</p> <pre> We have two lines f and g f: A + i * AB g: C + j * CD First, we need to find out, whether they are parallel If they are parallel, then their slope must be equal parallel: AB.Y/AB.X == CD.Y/CD.Y If they are parallel, return false At this point, we know they are not paralle and two non-parallel lines in 2D intersect so this is valid: A + i * AB = C + j * CD We can rewrite that to: I. A.X + i * AB.X = C.X + j * CD.X II. A.Y + i * AB.Y = C.Y + j * CD.Y We determine j in I: j = (A.X + i*AB.X - C.X) / CD.X now we can substituate j in II II. A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y After some tranformation (you can skip this): > A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y > A.Y + i*AB.Y = C.Y + (A.X/CD.X + i*AB.X/CD.X - C.X/ CD.X) * CD.Y > A.Y + i*AB.Y = C.Y + A.X*CD.Y/CD.X + i*AB.X*CD.Y/CD.X - C.X*CD.Y/ CD.X > i*AB.Y - i*AB.X*CD.Y/CD.X = C.Y + A.X*CD.Y/CD.X - C.X*CD.Y/ CD.X - A.Y > i*(AB.Y - AB.X*CD.Y/CD.X) = C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y > i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X) We get: i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X) We determined j previously. We simply insert the value of i into that formula and get thevalue for j. We need both to determine, whether they really intersect As for the intersection, since we have i, we can calculate the point of intersection by inserting it into f: A + i * AB return InRange(i, 0, 1) && InRange(j, 0, 1)-> if both i and j are in that range, they intersect!</pre>

<p><span><img alt="happy.png" src="http://public.gamedev.net//public/style_emoticons/default/happy.png" /></span><br />

What you have to do now is to extrude AB by a specific factor so that it always intersects with the square around it.</p>

<p>Then you simply execute that above for all the 4 sides</p>

### #4Aphton

Posted 23 January 2013 - 11:27 AM

If you are interested in the maths:

- We have two lines f and g
- f: A + i * AB
- g: C + j * CD
- First, we need to find out, whether they are parallel
- If they are parallel, then their slope must be equal
- parallel: AB.Y/AB.X == CD.Y/CD.Y
- If they are parallel, return false
- At this point, we know they are not paralle and two non-parallel lines in 2D intersect so this is valid:
- A + i * AB = C + j * CD
- We can rewrite that to:
- I. A.X + i * AB.X = C.X + j * CD.X
- II. A.Y + i * AB.Y = C.Y + j * CD.Y
- We determine j in I:
- j = (A.X + i*AB.X - C.X) / CD.X
- now we can substituate j in II
- II. A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y
- After some tranformation (you can skip this):
- > A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y
- > A.Y + i*AB.Y = C.Y + (A.X/CD.X + i*AB.X/CD.X - C.X/ CD.X) * CD.Y
- > A.Y + i*AB.Y = C.Y + A.X*CD.Y/CD.X + i*AB.X*CD.Y/CD.X - C.X*CD.Y/ CD.X
- > i*AB.Y - i*AB.X*CD.Y/CD.X = C.Y + A.X*CD.Y/CD.X - C.X*CD.Y/ CD.X - A.Y
- > i*(AB.Y - AB.X*CD.Y/CD.X) = C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y
- > i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X)
- We get:
- i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X)
- We determined j previously. We simply insert the value of i into that formula and get thevalue for j.
- We need both to determine, whether they really intersect
- As for the intersection, since we have i, we can calculate the point of intersection by inserting it into
- f: A + i * AB
- return InRange(i, 0, 1) && InRange(j, 0, 1)-> if both i and j are in that range, they intersect!

What you have to do now is to extrude AB by a specific factor so that it always intersects with the square around it.

Then you simply execute that above for all the 4 sides

### #3Aphton

Posted 23 January 2013 - 11:25 AM

If you are interested in the maths:

We have two lines f and g f: A + i * AB g: C + j * CD First, we need to find out, whether they are parallel If they are parallel, then their slope must be equal parallel: AB.Y/AB.X == CD.Y/CD.Y If they are parallel, return false At this point, we know they are not paralle and two non-parallel lines in 2D intersect so this is valid: A + i * AB = C + j * CD We can rewrite that to: I. A.X + i * AB.X = C.X + j * CD.X II. A.Y + i * AB.Y = C.Y + j * CD.Y We determine j in I: j = (A.X + i*AB.X - C.X) / CD.X now we can substituate j in II II. A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y After some tranformation (you can skip this): > A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y > A.Y + i*AB.Y = C.Y + (A.X/CD.X + i*AB.X/CD.X - C.X/ CD.X) * CD.Y > A.Y + i*AB.Y = C.Y + A.X*CD.Y/CD.X + i*AB.X*CD.Y/CD.X - C.X*CD.Y/ CD.X > i*AB.Y - i*AB.X*CD.Y/CD.X = C.Y + A.X*CD.Y/CD.X - C.X*CD.Y/ CD.X - A.Y > i*(AB.Y - AB.X*CD.Y/CD.X) = C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y > i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X) We get: i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X) We determined j previously. We simply insert the value of i into that formula and get thevalue for j. We need both to determine, whether they really intersect As for the intersection, since we have i, we can calculate the point of intersection by inserting it into f: A + i * AB return InRange(i, 0, 1) && InRange(j, 0, 1)-> if both i and j are in that range, they intersect!

What you have to do now is to extrude AB by a specific factor so that it always intersects with the square around it. Then you simply execute that above for all the 4 sides

### #2Aphton

Posted 23 January 2013 - 11:22 AM

If you are interested in the maths:

We have two lines f and gf: A + i * ABg: C + j * CDFirst, we need to find out, whether they are parallelIf they are parallel, then their slope must be equalparallel: AB.Y/AB.X == CD.Y/CD.YIf they are parallel, return falseAt this point, we know they are not paralle and two non-parallel lines in 2D intersect so this is valid:A + i * AB = C + j * CDWe can rewrite that to:I. A.X + i * AB.X = C.X + j * CD.XII. A.Y + i * AB.Y = C.Y + j * CD.YWe determine j in I:j = (A.X + i*AB.X - C.X) / CD.Xno we can substituate j in IIII. A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.YAfter some tranformation (you can skip this):> A.Y + i*AB.Y = C.Y + ((A.X + i*AB.X - C.X) / CD.X) * CD.Y> A.Y + i*AB.Y = C.Y + (A.X/CD.X + i*AB.X/CD.X - C.X/ CD.X) * CD.Y> A.Y + i*AB.Y = C.Y + A.X*CD.Y/CD.X + i*AB.X*CD.Y/CD.X - C.X*CD.Y/ CD.X> i*AB.Y - i*AB.X*CD.Y/CD.X = C.Y + A.X*CD.Y/CD.X - C.X*CD.Y/ CD.X - A.Y> i*(AB.Y - AB.X*CD.Y/CD.X) = C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y> i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X);We get:i = (C.Y + (A.X - C.X)*CD.Y/CD.X - A.Y) / (AB.Y - AB.X*CD.Y/CD.X)We determined j previously. We simply insert the value of i into that formula and get thevalue for j. We need both to determine, whether they really intersectAs for the intersection, since we have i, we can calculate the point of intersection by inserting it into f: A + i * ABreturn InRange(i, 0, 1) && InRange(j, 0, 1)-> if both i and j are in that range, they intersect!

What you have to do now is to extrude AB by a specific factor so that it always intersects with the square around it. Then you simply execute that above for all the 4 sides