Good Intersection Function
-
I'm looking for a function to check if 2 lines intersect. There are a few key factors to this. The project I am working on involves navigating around polygons by moving from vertex to vertex, but only to vertex's it can move in a straight line to without intersecting other lines. I've found a few functions online, except they always find an intersection ON the vertex, which I can't have, and they find an intersection when moving from 1 vertex to the other on the same polygon, parallel lines, which is an allowed move. Thanks Note - The project involves the intersect check, but that isn't the project, the project is to test AI algorithms to compare the results. (he's provided some Dr. Scheme code http://skipjack.cs.wwu.edu/~gmatth/index.html that does it, that I can't quite figure out how to convert to C# though I know the function I need to translate is (define intersect-lines?) The wisest of the wise may err. - Aeschylus Codito Ergo Sum - (I code, therefor I am) -- modified at 19:32 Sunday 9th October, 2005
-
I'm looking for a function to check if 2 lines intersect. There are a few key factors to this. The project I am working on involves navigating around polygons by moving from vertex to vertex, but only to vertex's it can move in a straight line to without intersecting other lines. I've found a few functions online, except they always find an intersection ON the vertex, which I can't have, and they find an intersection when moving from 1 vertex to the other on the same polygon, parallel lines, which is an allowed move. Thanks Note - The project involves the intersect check, but that isn't the project, the project is to test AI algorithms to compare the results. (he's provided some Dr. Scheme code http://skipjack.cs.wwu.edu/~gmatth/index.html that does it, that I can't quite figure out how to convert to C# though I know the function I need to translate is (define intersect-lines?) The wisest of the wise may err. - Aeschylus Codito Ergo Sum - (I code, therefor I am) -- modified at 19:32 Sunday 9th October, 2005
let's call your segment AB and CD, and let's use underline as vector notation. let's compute intersection! you should solve a & b so that A + a AB = C + b CD => a AB - b CD = C - D = DC very simple a * Num1 + b * Num2 = Num3 set of equations. In N dimensional space (N>2) it might have no solution (=> no intersection). and now, the segments (instead of just the line) intersect if 0 <= a <= 1 && 0 <= b <= 1 Next time try not to sleep during geometry lesson.... ;P (You could sleep during philosophy lessons, instead :zzz: ) -- modified at 20:27 Sunday 9th October, 2005