2D Line intersection test:
 By: Christopher Bartlett
Take a look at Solutions Page for other solutions.

## Given:

• Two Line Segement.

## Asked to Write Code for following:

• How to test if lines intersect.

• none

## Steps to Solve:

1. Basic Idea is to test the triangles fromed by the end point of two line segments. Test the two triangles form by Line one to line two's end points. If first two checks are same clockness then there is no possible interect of line segement. If Clockness is different then check line two to one. If Clockness is different then Lines intersect.
2. check_tri_clock_dir does a determinate type calculation to find the clockness of a triangle made of the three point pass in. Could be Clockwise, CounterClockwise and Line (meaning the two line segements lie along the same line)
3. check_intersect return 1 for intersect and 0 for none.
4. CODE
Some Notes:

Only some code for now.

CODE
Code uses:

• Everything is adds, subtractions, and multiplies with no divides.
• ```// Start Code
// must include at least these
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define CLOCKWISE = -1;
#define COUNTER_CLOCKWISE = 1;
#define LINE = 0;

typedef struct fpoint_tag
{
float x;
float y;
} fpoint;

fpoint line1_pt1 = {0.0, 3.0};
fpoint line1_pt2 = {0.0, 0.0};
fpoint line2_pt1 = {2.0, 3.0};
fpoint line2_pt2 = {-2.0, 1.0};

int check_tri_clock_dir(fpoint pt1, fpoint pt2, fpoint pt3)
{
float test;
test = (((pt2.x - pt1.x)*(pt3.y - pt1.y)) - ((pt3.x - pt1.x)*(pt2.y - pt1.y)));
if (test > 0) return COUNTER_CLOCKWISE;
else if(test < 0) return CLOCKWISE;
else return LINE;
}

int check_intersect(fpoint l1p1, fpoint l1p2, fpoint l2p1, fpoint l2p2)
{
int test1_a, test1_a, test2_a, test2_a;

test1_a = check_tri_clock_dir(l1p1, l1p2, l2p1);
test1_b = check_tri_clock_dir(l1p1, l1p2, l2p2);
if (test1_a != test1_b)
{
test2_a = check_tri_clock_dir(l2p1, l2p2, l1p1);
test2_b = check_tri_clock_dir(l2p1, l2p2, l1p2);
if (test2_a != test2_b)
{
return 1;
}
}
retrun 0;
}

// End Code

```