MathGroup Archive 2006

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: Reconstructing data points from a InterpolatingFunction object
  • Next by Date: Bugs--Limit bug in version 5+ ?
  • Previous by thread: Graphics--triangle intersection
  • Next by thread: Re: Graphics--triangle intersection