Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I had previously asked this for 3D but now I changed my strategy and would like to do the intersection in 2D.

The Rectangle is axis aligned and will always be in a fixed position, and has a constant shape and size, basically I want to clip the red areas of the triangles that extend outside the bounds of the rectangle The triangles could be in any position, shape or size, I my code I have a loop where I check the triangles one by one however I am still clueless about the math.

I have identified 5 cases of triangle rectangle intersection as shown here.Triangle Rectangle Intersections

How do I find the intersection points of the triangle and the rectangle?

share|improve this question
    
You should possibly have this pic copyrighted! –  mlvljr Feb 15 '12 at 13:55
    
The picture is not complete. Take e.g. the top left green polygon: it has 5 edges and doesn't include the corner of the rectangle. You can also draw a very similar triangle which does contain the corner of the rectangle, in which case the intersection has 4 edges. Similarly, the big triangle crosses opposite sides of the rectangle, but you can also draw a rectangle which crosses adjacent sides of the rectangle. –  MSalters Nov 20 '12 at 11:18

3 Answers 3

up vote 4 down vote accepted

The Sutherland-Hodgman polygon clipping algorithm should work just fine for triangle vs. rectangle clipping. You'll find some more information about clipping algorithms here. Or just search for "Sutherland Hodgman clipping".

share|improve this answer
    
would I get the coordinates of the new generated polygon from the algorithm? What would be the speed I have to perform clipping on a large number of triangles? –  Kevin Boyd Feb 9 '11 at 16:21
    
Not sure what you mean with "coordinates of the new generated polygon"... you'll get the clipped polygons. AFAIK Sutherland Hodgman is a very fast clipping algorithm but has some flaws (especially with concave polygons). But speed is relative. –  bummzack Feb 9 '11 at 16:43
    
I mean I the green areas in the figure above, I needed the coordinates for those. As far as concave polygons are concerned I wonder what they mean would the triangles be considered as concave polygons? –  Kevin Boyd Feb 9 '11 at 16:46
    
Yeah sure. You'll get all the coordinates of the polygons that are inside your rectangle. A triangle is convex, so there's no problem there. This is concave: en.wikipedia.org/wiki/Concave –  bummzack Feb 9 '11 at 17:03
    
Found another excellent link to the Sutherland-Hodgman sunshine2k.de/stuff/Java/SutherlandHodgman/… . Now I have 2 options, one by zacharmarz and the one that you suggested. –  Kevin Boyd Feb 9 '11 at 18:03

I think CGAL i too robust for such simple task. And Sutherland Hodgman clipping is usefull, when you have general polygon. But you have axis aligned box and you should make use of it.

So my opinion:

First case: Triangle and box are intersecting. You can figure it out by line-line intersection test (for example this: http://mathworld.wolfram.com/Line-LineIntersection.html but you can google it in many ways - also look at EDIT2 at the end of this answer). You make line from every edge of box and every edge of triangle. Then you find intersection of all combinations (there are 12 cases <- 3 (triangle) x 4 (box) edges).

If you find intersection point (IP), test, if IP lies between two vertices of triangle or somewhere else on line (created from triangle edge). If IP lies between vertices, then test, if IP's x and y coordinates lie in box x and y intervals (it's axis aligned) - it's green case on picture. If IP doesn't lie in both of it's intervals, then it's red case on picture. intersections

After this test, you should have several vertices, which define your new polygon created from triangle.

//EDIT: Oh. I forget, you have to take also every vertex from triangle for your new polygon, which lies in box (on picture there are two such vertices).

If no edge-edge intersection is found, you have to check two other cases:

Second case: Whole rectangle lies in triangle - your new points from triangle are just vertices of box.

Third case: Whole triangle is in box. Take original triangle as result.

I hope, this can work. It's not tested. Maybe you can use some heuristic and avoid of testing all possible edge-edge combinations.

//EDIT2: You should also make use of axis aligned box in line-line intersection test - just find y coordinate with given x constant (in case of vertical box edge) or find x coordinate with given y constant (in case of horizontal edge).

share|improve this answer
    
Seems to be good idea! I wonder how fast is it though, any speed optimizations you can think of? I also found sebleedelisle.com/2009/05/… and blackpawn.com/texts/pointinpoly/default.html don't know if I could build up something on these lines. –  Kevin Boyd Feb 9 '11 at 16:37
    
Btw are you some kind of wizard in intersection math, you also answered my 3D question didn't you? –  Kevin Boyd Feb 9 '11 at 16:42
    
I'm sorry I couldn't understand the edit 2 that you posted. –  Kevin Boyd Feb 9 '11 at 16:44

You may find the answer to your question here on Stack Overflow.

They suggest using CGAL which is a C++ library for Geometric Algorithms. You could also use C++'s Boost.Geometry for a solution as well.

share|improve this answer
    
I'm using a much dumber language(actionscript) and possibly I may not have the liberty of using these geometric algorithms. Possibly I might need to port them. –  Kevin Boyd Feb 9 '11 at 16:22
    
@Kevin, sorry, you didn't specify actionscript in the question. –  Stephen Furlani Feb 9 '11 at 19:31

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.