`if (box1.xmax < box2.xmin OR box1.ymax < box2.ymin OR box1.xmin > box2.xmax OR box1.ymin > box2.ymax) then reject`

In the case shown below, line1's box.xmax is less than line2's box xmin, so they can never cross.
`sqrt( (B.x-A.x)^2 + (B.y-A.y>^2) )`

In order to rotate points by a given angle, we need the sine and cosine of that angle. For angle a these are:-
`sin a = length(EB) / length(AB) or sin = B.x / length(AB)`

`cos a = length(EA) / length(AB) or cos = B.y / length(AB)`

Remember that we calculated length(AB) using Pythagoras, above.
To rotate points around (0,0) by angle a, use these formulae, which you may have encountered in school maths:-
`x' = x cos a - y sin a`

`y' = y cos a + x sin a`

When the above formula is applied to AB and CD we see the result below.
`const double small_value = 0.00001;`

`if C'.y < 0 AND D'.y < 0 they do not cross`

`if C'.y > B'.y AND D'.y > B'.y they do not cross`

`if C'.x < 0 AND D'.x < 0 they do not cross`

`if C'.x > 0 AND D'.x > 0 they do not cross`

`F.y = C'.y - (((D'.y - C'.y) * C'.x) / (D'.x - C'.x) ) `

Note that we already know that C'D' is not vertical, so D'.x-C'x cannot be zero - there is no need to apply a division by zero check before executing the above calculation.
We now have the position of F. We simply need to check it against line A'B'.
Thus, if F.y < 0 or F.y> B'.y, the line segments do not cross.
`x' = x cos a - y sin a`

`y' = y cos a + x sin a`

...but since F.x=0, sin(-a) = -sin(a), and cos(-a) = cos(a), the operation becomes much simpler:-
`F'.x = F.y * sin a`

`F'.y = F.y * cos a`

Then, translate the rotated F' by the position of A:-
`F'.x = F'x + A.x`

`F'.y = F'y + A.y`

... to derive the actual "world" position of the intersection point F, rather than relative to AB.
- Using the line segments AB and CD in the worked example:-AB is (-5,-2) to (1,2) CD is (-8,-2) to (2,1)
- The boundary boxes cross, so we proceed to translate so that A is at (0,0).
- Subtract A from B,C,D i.e. subtract (-5,-2)
- AB is now (0,0) to (6,4) CD is now (-3,0) to (7,3)
- Calculate length(AB) using Pythagoras. Length(AB) = 7.2111025
- Calculate sin(a) = B.x / length(AB) = 0.83205029433784372
- Calculate cos(a) = B.y / length(AB) = 0.55470019622522915
- Rotate AB and CD around (0,0) A'B' is (0,0) to (0,7.2111025) C'D' is (-1.66410059,-2.49615) to (1.38675,7.4884)
- C'D' is not co-linear or vertical, and crosses X=0, so calculate where it crosses.
- C'D' crosses X=0 at point F.
- F.Y = 2.9499964 (F.X = 0, for clarity)
- Check if F.Y is between 0 and B'.Y or 7.2111025. It is, so the line segments
cross.*do* - Rotating F the opposite way, and translating by -A, we calculate the intersection point(-2.5454545,-0.3636363740)

public struct ConstantValue { internal const double SmallValue = 0.00001; } public class Point2D { private float X; private float Y; public Point2D(double src_x, double src_y) { this.X = (float)src_x; this.Y = (float)src_y; } public Point2D(float src_x, float src_y) { this.X = src_x; this.Y = src_y; } public float X { set { this.X = value; } get { return this.X; } } public float Y { set { this.Y = value; } get { return this.Y; } } } public class LineSeg2D { private Point2D m_Start; private Point2D m_End; public LineSeg2D(Point2D start, Point2D end) { this.m_Start = startPoint; this.m_End = endPoint; } // returns true if intersection, and returns position // if a buffer is supplied (intersect_point) // public bool CheckIntersect(Point2D intersect_point, LineSeg2D other_line) { //check if points are same if ( this.m_End.X == other_line.m_End.X && this.m_End.Y == other_line.m_End.Y && this.m_Start.X == other_line.m_Start.X && this.m_Start.Y == other_line.m_Start.Y ) { //same other_line - mark as crossing if (intersect_point != null) { intersect_point.X = this.m_End.X; intersect_point.Y = this.m_End.Y; } return (true); } if ( this.m_End.X == other_line.m_Start.X && this.m_End.Y == other_line.m_Start.Y && this.m_Start.X == other_line.m_End.X && this.m_Start.Y == other_line.m_End.Y ) { //same other_line - mark as crossing if (intersect_point != null) { intersect_point.X = this.m_End.X; intersect_point.Y = this.m_End.Y; } return true; } //allow end points to coincide if ( this.m_End.X == other_line.m_Start.X && this.m_End.Y == other_line.m_Start.Y ) { return false; } if ( other_line.m_End.X == this.m_Start.X && other_line.m_End.Y == this.m_Start.Y ) { return false; } //check line1 is not a point if ( this.m_End.X == this.m_Start.X && this.m_End.Y == this.m_Start.Y ) { //line1 is a point return false; } //check line2 is not a point if ( this.m_End.X == this.m_Start.X && this.m_End.Y == this.m_Start.Y ) { //line1 is a point return false; } //get the magnitude of line1 double line1_dx = this.m_Start.X - this.m_End.X; double line1_dy = this.m_Start.Y - this.m_End.Y; double line1_mag = Math.Sqrt((line1_dx * line1_dx) + (line1_dy * line1_dy)); //shift line2 relative to line1 START POINT double line2_sx = other_line.m_End.X - this.m_End.X; double line2_sy = other_line.m_End.Y - this.m_End.Y; double line2_fx = other_line.m_Start.X - this.m_End.X; double line2_fy = other_line.m_Start.Y - this.m_End.Y; double sin = line1_dx / line1_mag; double cos = line1_dy / line1_mag; //rotate //x' = x cos f - y sin f //y' = y cos f + x sin f double line2a_sx = (line2_sx * cos) - (line2_sy * sin); double line2a_sy = (line2_sy * cos) + (line2_sx * sin); double line2a_fx = (line2_fx * cos) - (line2_fy * sin); double line2a_fy = (line2_fy * cos) + (line2_fx * sin); //check if co-linear if (Math.Abs(line2a_sx) < ConstantValue.SmallValue && Math.Abs(line2a_fx) < ConstantValue.SmallValue ) { //line2 lies on the Y axis if (line2a_sy > line2a_fy) { double t = line2a_sy; line2a_sy = line2a_fy; line2a_fy = t; } if (line2a_sy > line1_mag) { //line2 is ABOVE line1 return false; } if (line2a_fy < 0) { //line2 is BELOW line1 return false; } //lines are co-linear and DO interesect if (intersect_point != null) { intersect_point.X = this.m_End.X; intersect_point.Y = this.m_End.Y; } return true; } //ensure line2 crosses Y axis if (line2a_sx < 0 && line2a_fx < 0) { //both ends are BELOW x=0 return false; } if (line2a_fx > 0 && line2a_sx > 0) { //both ends ABOVE y=0 return false; } //check if line2a is all if (line2a_sy < 0 && line2a_fy < 0) { return false; } //check if line2a is all >mag1 if (line2a_sy >line1_mag && line2a_fy > line1_mag) { return false; } //check if line2a is parallel if (Math.Abs(line2a_sx - line2a_fx) < ConstantValue.SmallValue) { return false; } //now calculate where line2a crosses Y axis //using "similar trianges" double ry = ((line2a_fy - line2a_sy) * line2a_sx) / (line2a_fx - line2a_sx); ry = line2a_sy-ry; //ry is where it crosses x=0; if (ry < 0 || ry > line1_mag) { //crosses Y axis OUTSIDE of line1 return false; } if (intersect_point != null) { // calculate intersection point by roating (0,ry) // by the reverse of the original // rotation, and adding to line1 start point // intersect_point.X = (float)((ry * sin) + this.m_End.X); intersect_point.Y = (float)((ry * cos) + this.m_End.Y); } return true; } }

Please refresh the page and try again.