Hello

i have to solve a mathematical problem
can any one tell me how shud i go for it ???????
i have coordinates of 2 points
i also have coordinates of 4 points which forms a square.
i have to write a program to find out whether the line formed by given 2 points intersects the
square formed by rest 4 points.
can anyone give me any idea to solve it ??????????

Thank you

if any coordinates of the square are in the boundaries of the coordinates of the line then the line intersects that square

if any coordinates of the square are in the boundaries of the coordinates of the line then that doesn't mean always that line intersects that square.This case is not applicable always.

can u elaborate a bit on this.

If the line segment intersects the square, it must intersect one of the two line segments between opposite corners of the square. Thus if v1, v2, v3, and v4 are the vertices of the square (in order, going around the square), then you need to check if your line segment intersects either the line segment v1v3 or the line segment v2v4.

__________________
www.blake-foster.com

Hmmm...
I don't believe that is adequate to determine intersection of a line segment with a square.

I drew a square and its diagonals and scribbled a few example lines that illustrate my point, and I attached the drawing to this post

My observations:

1. I don't think that intersection with a diagonal is a necessary condition for intersection with a side of the square.

2. I don't think that inequalities involving coordinates of the end points of the line and coordinates of the vertices will tell the story either. (Unless, that is, the sides of the square are aligned with the coordinate system, in which case it's pretty easy to do it this way.)


Without getting into some interesting aspects of computational geometry (convex hulls, dot products, etc.), for the general (non-axis-aligned square) I think one could start by determining whether the given line segment intersects at least one of the sides of the square.

I have a question: What is the definition of a "line segment intersecting with a square"? What if the line segment is contained totally inside the square? Does that count? Or does "intersection of a line segment with a square" imply intersection of the given line segment with one or more of the line segments that make up the sides of the square? (I assume that two line segments are said to intersect if they have at least one point in common.)

A final question (maybe already answered by the answer to the previous question): Is there a difference between a "line segment intersecting a square" and a "line segment colliding with a square"? I think that game programmers are more likely to use the "collision" terminology.

Regards,

Dave

Attached Images

Intersections.pdf (3.1 KB, 18 views)

Hmm, good point, it always help to draw a picture. I was only thinking of the case where both endpoints are outside of the square.

Try checking intersections with the diagonals, and also checking if one endpoint is inside the square.

__________________
www.blake-foster.com

hey thanks for considering all different combination for this problem
well i want to clear here that lenght of the line is more than the diagonal of the square
i mean in my case line will be always more than the square
as u suggested even i was thinking like determining whether the given line segment intersects at least one of the sides of the square or not.
but i am not getting how to find out whether a line intersects a line segment
i mean i know how to find out a point where 2 lines intersects each other or not, but in this case i have to find out whether a line intersect a segment or not
is thr any such formula for it
or can u tell me how should i go for it.
plz elaborate a bit.


ya and line colliding with square is also considered as intersection in this case.
even if line just passing through any of the vertices can also be considered here as an intersection.

Here's an algorithm (in pseudocode) straight out of my algorithms text:


It returns true if and only if the segment p1p2 intersects the segment q1q2.

If you use floating point numbers, you should use a threshold when testing for equality. In other words, rather than testing if a == b, test if a - epsilon < b < a + epsilon, where epsilon is your threshold.

__________________
www.blake-foster.com