Line segment in a triangle

How can开发者_如何学C we check if a line segment falls partially or fully inside a triangle?

Cheers.

Get the function for the line from the end points of the line segment. Check where this line crosses any of the sides of the triangle.

If any part of the line segment is inside the triangle, the line will either pass in through one side and out through another, or it will pass exactly along one side of the triangle and pass through two of it's corners.

If the line passes through the triangle, you compare the points where the line crosses the triangle sides (or corners) with the end points of the segment, to see if the segment is part of the line that crosses the triangle.

For checking if a line is fully inside a triangle, you need to check whether both end points of the line segment are located inside of the triangle. Checking if a point is inside of a triangle can be done using techniques described here.

Checking if a segment intersects the triangle partially is a bit more complex, since checking its end points may not be enough. There are two possible cases of partial intersection:

1. One end point is inside of the triangle, and the other isn't
2. Both end points are outside of the triangle, but the segment crosses at least one of the triangle sides.

Checking 1. can be done by this technique. Checking 2. can be done by algorithms that check whether two segments intersect. One example of how it can be done is here.

If one of the points of the segment is inside of the triangle => partially, if both are => fully

Point O is inside of the triangle if and only if the sum of angles AOB, BOC, COA equals 360 deg.

Cheers,

Gleb

Better algorithm follows:

Why not do this:

• If both end points of the line segment lie inside or on triangle, then line segment must lie on or inside triangle.

To check if a point lie inside triangle:

• Stand at the point, look at each vertex of the triangle
• If you look at each vertex in clockwise / anticlockwise direction then you are inside or outside