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
- Graphics--triangle intersection