Polygon and line collision detection

[ofiras]

Hello everyone,
I have a problem that I couldn't solve. What I have to do is a
function that will get an array of points (the polygon), a point and
int variable that will represent a side I need to check. This function
has to check if the point will come across the polygon if it will go
in a certain direction (it can be 45 degrees up to the left or right).
The function must do this without checking every possibility in the
dot's course. The only solution I could think of what making a line
that goes through the dot, in 45 degrees up, and check if there is a
collision between the line and the polygon at the direction I want to
check.

This is a demonstration of what it has to do: http://i50.tinypic.com/2ez73nc.jpg
- in this case the function should return true.
http://i50.tinypic.com/xqc4mv.jpg - in this case the function should
return false.
(in both cases the line was to the left, but it can also be to the
right)

Is there anyone who knows how can I do it?
Please help,
Ofir.

 

[Family Tree Mike]

Hello everyone,
I have a problem that I couldn't solve. What I have to do is a
function that will get an array of points (the polygon), a point and
int variable that will represent a side I need to check. This function
has to check if the point will come across the polygon if it will go
in a certain direction (it can be 45 degrees up to the left or right).
The function must do this without checking every possibility in the
dot's course. The only solution I could think of what making a line
that goes through the dot, in 45 degrees up, and check if there is a
collision between the line and the polygon at the direction I want to
check.

This is a demonstration of what it has to do: http://i50.tinypic.com/2ez73nc.jpg
- in this case the function should return true.
http://i50.tinypic.com/xqc4mv.jpg - in this case the function should
return false.
(in both cases the line was to the left, but it can also be to the
right)

Is there anyone who knows how can I do it?
Please help,
Ofir.

Intersections between two lines is easy enough. That is how you solve
the problem. I don't understand the description though. Basically you
need to define a second point for the dot to travel through, so that you
can the line. I'm not understanding your definition of left and right,
nor 45 degrees up of left or right.

Once you define the points, then you can get two functions of y = mx + b
that must be equal, and solve for the coincidence point.

 

[ofiras]

Intersections between two lines is easy enough.  That is how you solve
the problem.  I don't understand the description though.  Basically you
need to define a second point for the dot to travel through, so that you
can the line.  I'm not understanding your definition of left and right,
nor 45 degrees up of left or right.

Once you define the points, then you can get two functions of y = mx + b
that must be equal, and solve for the coincidence point.

What I meant was that I have to check for interaction between the line
of the polygon and the part of line with the dot, where the X is
bigger/smaller than the X of my dot. Therefore, the solution you
suggested won't always work (for example, in this situation -
http://i50.tinypic.com/xqc4mv.jpg)
Thanks.
Ofir.

 

[RayLopez99]

What I meant was that I have to check for interaction between the line
of the polygon and the part of line with the dot, where the X is
bigger/smaller than the X of my dot. Therefore, the solution you
suggested won't always work (for example, in this situation -http://i50.tinypic.com/xqc4mv.jpg)
Thanks.

Dude just do a Hit Test. Google this. There's an enum parameter for
WPF that tests for intersection of any two Geometries (line, point and
rectangle are the most popular). QED.

DOn't reinvent the wheel if you don't have to.

RL

 

[Family Tree Mike]

What I meant was that I have to check for interaction between the line
of the polygon and the part of line with the dot, where the X is
bigger/smaller than the X of my dot. Therefore, the solution you
suggested won't always work (for example, in this situation -
http://i50.tinypic.com/xqc4mv.jpg)
Thanks.
Ofir.

But why did you choose that ray, (down-left) as opposed to up-right that
_would_ intersect the polygon. Down-right and up-left would intersect
as well.

 

[ofiras]

But why did you choose that ray, (down-left) as opposed to up-right that
_would_ intersect the polygon.  Down-right and up-left would intersect
as well.

@RayLopez99 - Thanks but I think it's not what I need. I did a small
research about "hit test" and from what I understood it only works
with graphics (well, that's what I found in Google). I need to do it
without having graphics.
I think I'm onto a solution (so simple, how didn't I think of it
before?!). I will make a line equation for the dot's course (looks
like y=-x+n) and than I will check for each two neighbor points in the
polygon if the line collides with the line between those two dots (by
checking if the X of the collision point is between the X's of the
points in the polygon). Then, to see if it is left or right to the dot
(this is what I didn't know how to do) I will check if the X of the
collision point is bigger/smaller than the dot's X. Yes, I know, I'm
stupid for not seeing it before (I even said that I need the X to be
smaller/bigger in one of my posts: P).
Thanks anyway (and sorry for being so misunderstood, I am not a native
speaker),
Ofir.

 

[AA2e72E]

You may want to study this:

http://alienryderflex.com/polygon/

 

[vanderghast]

To know if a line intercepts a polygon, in 3D, define a plane perpendicular
to the line as "the screen" and project the 2D polygon onto the screen. If
the projection of the line on the screen, a single point, is inside the
projected polygon, then the line intercepts the unprojected polygon too (in
its inside, or at its border). If the said line and the said initial
unprojected polygon are in the same plane, call it the "sheet of paper",
then we can limit the "screen" to its trace in the "sheet of paper", which
is a line. In this case, let lambda a running coordinate on that line, we
have the projection of the polygon lying between two limits, lambda_min and
lambda_max. If the interception of the line with the screen trace lies
between these two limits, then the line intercept the polygon.

As example, assume the line is ****horizontal*****. Lambda can be taken as
the y axis cord.


* P1
|
-------------- +
Y_max
*P2 | polygon | |
-------------- +
Y_min

|



Then, P1.Y is not between Y_max and Y_min, so the horizontal line through
P1 does not intercept the polygon.
P2.Y is between Y_max and Y_min, so the horizontal line
through P2 does intercept the polygon.


For a ***non-horizontal line***, someone can "rotate" the "sheet of paper"
through the point defining the start of the ray, so that the ray become
horizontal.


Note that a line is made of two rays. Or, given a ray, there is an
'complement-ray' which, by union, make a line. Knowing that a line
intercept something does not necessary say which of its two possible rays
intercept the same thing.



Vanderghast, Access MVP