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?

  • \$\begingroup\$ You should possibly have this pic copyrighted! \$\endgroup\$
    – mlvljr
    Feb 15, 2012 at 13:55
  • \$\begingroup\$ 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. \$\endgroup\$
    – MSalters
    Nov 20, 2012 at 11:18

3 Answers 3


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".

  • \$\begingroup\$ 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? \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 at 16:21
  • \$\begingroup\$ 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. \$\endgroup\$
    – bummzack
    Feb 9, 2011 at 16:43
  • \$\begingroup\$ 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? \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 at 16:46
  • \$\begingroup\$ 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 \$\endgroup\$
    – bummzack
    Feb 9, 2011 at 17:03
  • \$\begingroup\$ 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. \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 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).

  • \$\begingroup\$ 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. \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 at 16:37
  • \$\begingroup\$ Btw are you some kind of wizard in intersection math, you also answered my 3D question didn't you? \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 at 16:42
  • \$\begingroup\$ I'm sorry I couldn't understand the edit 2 that you posted. \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 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.

  • \$\begingroup\$ 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. \$\endgroup\$
    – Kevin Boyd
    Feb 9, 2011 at 16:22
  • \$\begingroup\$ @Kevin, sorry, you didn't specify actionscript in the question. \$\endgroup\$ Feb 9, 2011 at 19:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .