Re: Graphics--triangle intersection

*To*: mathgroup at smc.vnet.net*Subject*: [mg66573] Re: [mg66549] Graphics--triangle intersection*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Sat, 20 May 2006 04:47:54 -0400 (EDT)*References*: <200605190740.DAA12894@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

On 19 May 2006, at 16:40, cvs at myonline.be wrote: > Hi, > > I'm new to Mathematica. I would like to solve following problem. > > I have a number of overlapping triangles. In the intersection of > all triangles, I want to draw the biggest triangle possible. > > Sounds simple ? Could this be solved in mathematica ? > > Any help is appreciated. > > Thanks > > > Any algorithm that solves this kind of problem can be implemented in Mathematica. Therefore the question is not really about Mathematica but about finding a suitable algorithm. Implementing such an algorithm in Mathematica will be no harder and probably easier than in most other programming languages. I have not given the question of finding an algorithm much thought but a pretty obvious though probably not the most efficient way comes to my mind. The basic idea is this. The intersection of a family of triangles is going to be a convex polygon in the plane: in fact any convex polygon can be represented in this way. So first we have to find the coordinates of the vertices of this polygon. One can then prove that the largest triangle (meaning, I suppose, the triangle with the largest area contained in the polygon) will have two have as its vertices some of the vertices of the polygon. We can simply list all possible triples of vertices of the polygon, compute the area of each of the corresponding triangles and choose the one with the largest area. So, to construct a complete algorithm one needs a way to determine the vertices of the convex polygon that is the intersection of a family of triangles. At the moment the way of doing this that comes to my mind is somewhat complicated and probably not very efficient; I am sure there are easier ones. The way I am thinking of involves first representing each triangle as the set of simultaneous solutions of three linear inequalities in two variables. We can combine these inequalities and apply either Reduce or CylindricalDecomposition, to obtain a cylindrical system of inequalities. From that one can work out the coordinates of the vertices. If this sounds too abstract here is a quick illustration. Consider for example the system of inequalities: ineq = {0 ² y, x + y ² 1, x ³ 0, y ² x, y ³ x/2, x + y > 1/2}; It represents a convex polygon, which you can see as follows: << Graphics`InequalityGraphics` gr = InequalityPlot[ineq, {x}, {y}, AxesOrigin -> {0, 0}] The cylindrical decomposition of ineq is given by: CylindricalDecomposition[ineq, {x, y}] (Inequality[1/4, Less, x, LessEqual, 1/3] && Inequality[(1/2)*(1 - 2*x), Less, y, LessEqual, x]) || (Inequality[1/3, Less, x, LessEqual, 1/2] && x/ 2 <= y <= x) || (1/2 < x < 2/3 && x/2 <= y <= 1 - x) || (x == 2/3 && y == 1/3) The x coordinates of the vertices can be read of immediately form the boundaries of the inequalities; the corresponding y coordinates would have to be worked out (I have once written and posted code to do this). As I wrote above, there are probably much more efficient ways to do this that ought to be well known to people with better knowledge of computational geometry than mine. Andrzej Kozlowski Tokyo, Japan

**References**:**Graphics--triangle intersection***From:*cvs@myonline.be