Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a couple of questions regarding finding the intersection of triangles. I have a system of 16 projectors that all have slightly different color gamuts. The color gamuts are represented by a triangle in the CIE chromaticity space. Here is a picture showing a few color gamuts in chromaticity space. color gamut

I need to restrict the lager gamut projectors so that all the projectors have the same gamut. I need to find the "greatest common gamut". Which I think boils down to finding the intersection of all 16 gamuts and drawing a triangle between the 3 vertices of the resulting polygon that are closest to the RGB "corners" of chromaticity space.

Is there a closed-form solution to finding the intersection of several triangles? Also I am assuming the intersection operator is associative right? ie ( A int B int C) = ( (A int B) int C ) = ( A int (B int C))? Sorry I don't know how to do the symbols :( Also does anyone know of functions or libraries in Matlab / Octave to find the intersection of polygons? Sorry if I used the wrong terminology anywhere I am not very knowledgeable when it comes to math.

share|improve this question
    
Any ideas at all? –  vanattab Dec 29 '12 at 23:11
add comment

1 Answer

up vote 1 down vote accepted

There are lots of algorithms for computing the intersection of two convex polygons. For example, O'Rourke et al.'s 1982 paper "A new linear algorithm for intersecting convex polygons" (also described in the book Computational Geometry in C, and online in Amar Mukherjee's lecture notes on Intersection Problems), or Toussaint's 1985 paper "A simple linear algorithm for intersecting convex polygons" (which is available online).

Alternatively, you can use a polygon clipping approach, such as the Sutherland-Hodgman algorithm. The Wikipedia article has nice pseudocode, so this might be easier to implement for you. Clipping can give you duplicated vertices, but I don't think that's a problem for your application.

In either case, you start with the first triangle, intersect/clip it with the second triangle, intersect/clip the resulting polygon with the third triangle, and so on. In the end you get the polygon that is the intersection of all of them, because yes, intersection is associative. (Clipping of convex polygons is the same, apart from the duplicated vertices.)

share|improve this answer
add comment

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.