3
$\begingroup$

Given variables $a_1$, $b_1$, $c_1$ and $a_2$, $b_2$, $c_2$ representing the vertices of two plane triangles, how might one specify the requirement for the two triangles to intersect as an objective in a mathematical programming solver such as CPLEX?

$\endgroup$
  • $\begingroup$ Are the $2$ triangles given? Is this a decision problem? Or an optimization problem? $\endgroup$ – Rodrigo de Azevedo Mar 28 '17 at 20:41
  • $\begingroup$ In the wider context, this is a decision problem: there are some additional constraints on the triangles. $\endgroup$ – NietzscheanAI Mar 30 '17 at 13:53
3
$\begingroup$

The first component you need is a function $orient(p_1,p_2,p_3)$ that computes the orientation between three point, i.e. that gives a positive number if there is a left turn between vectors $\overrightarrow{p_1 p_2}$ and $\overrightarrow{p_1 p_3}$ and a negative number otherwise (and zero if the three points are aligned):

$$ Orient(p_1,p_2,p_3) = det(\overrightarrow{p_1 p_2}, \overrightarrow{p_1 p_3}) = (x_2-x_1)(y_3-y_1) - (y_2-y_1)(x_3-x_1) $$

Then you can determine whether two segments $[p_1 p_2]$ and $[q_1 q_2]$ have an intersection:

$$ IsectSeg(p_1,p_2,q_1,q_2) = Orient(p_1,q_1,q_2) \times Orient(p_2,q_1,q_2) \le 0 \mbox{ and } Orient(q_1,p_1,p_2) \times Orient(q_2,p_1,p_2) \le 0 $$

In English: there is an intersection between $[p_1 p_2]$ and $[q_1 q_2]$ if $[p_1 p_2]$ straddles the supporting line $(q_1 q_2)$ and $[q_1 q_2]$ straddles the supporting line $(p_1 p_2)$.

You can also determine whether a point $p$ belongs to a triangle $q_1,q_2,q_3$ using:

$$ InsideTri(p,q_1,q_2,q_3) = (Orient(p,q_1,q_2) \times Orient(p,q_2,q_3) \ge 0) \mbox{ and } (Orient(p,q_2,q_3) \times Orient(p,q_3,q_1) \ge 0) $$

In English: $p$ is inside triangle $(q_1,q_2,q_3)$ if the orientation relative to the three edges $q_1 q_2$, $q_2 q_3$ and $q_3 q_1$ is the same.

Putting everything together, there is an intersection between both triangles if:

$$ IsectTri(p_1, p_2, p_3, q_1, q_2, q_3) = \exists i | InsideTri(p_i, q_1, q_2, q_3) \mbox{ or } \exists i | InsideTri(q_i, p_1, p_2, p_3) \mbox{ or } \exists i,j,k,l | IsectSeg(p_i, p_j, q_k, q_l) $$

In English: the two triangles have an intersection if one vertex of one triangle is inside the other triangle, or if there exists an intersection between the edges of the triangles. It is necessary to test for edges intersection (think for instance about two intersecting triangles that form a six-branches star that has no triangle vertex inside the other triangle)

Translated into a constraint, this gives a formula with inequality constraints combined with OR and AND operators (each of the 6 $Inside$ constraint yields two terms, and each of the 9 $IsectSeg$ constraint yields two terms as well). I am unsure of how to translate this into a way that can be understood by a constrained optimization software but there is probably a standard way of doing that.

There might be also a shorter / more elegant formulation (but I did not find it).

Note1: if you know in advance that the triangles are all oriented consistently (all clockwise, or all anticlockwise), then InsideTri() can be made simpler (just test the sign of the $Orient()$ relative to the three edge).

Note2: the asked question required a "mathematical programming" answer that could be expressed as a constraint in an optimization program. Now if what you want is simply determining whether two 2D triangles intersect (in a standard programming language that has execution flow and tests), there is a significantly faster approach that avoids some tests, see the 2D section in [1].

[1] https://hal.inria.fr/inria-00072100

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ many thanks for such a comprehensive reply. With respect to your final point about `consistent orientation': since the variables I want to provide for the MP solver are the vertices $p_i$, AFAIK, I can't guarantee any ordering on them. $\endgroup$ – NietzscheanAI Sep 12 '15 at 10:02
2
$\begingroup$

Let plane triangle $\mathcal T_i$ have vertices $\mathrm a_i, \mathrm b_i, \mathrm c_i \in \mathbb R^2$. Let $\Delta_2$ be the standard $2$-simplex.

If two plane triangles do intersect, i.e., $\mathcal T_1 \cap \mathcal T_2 \neq \emptyset$, then there exist $\eta_1, \eta_2 \in \Delta_2$ such that

$$\begin{bmatrix} | & | & |\\ \mathrm a_1 & \mathrm b_1 & \mathrm c_1\\ | & | & |\end{bmatrix} \eta_1 = \begin{bmatrix} | & | & |\\ \mathrm a_2 & \mathrm b_2 & \mathrm c_2\\ | & | & |\end{bmatrix} \eta_2$$

Thus, the triangle intersection problem can be reduced to linear programming. Choosing an arbitrary objective function, say, the zero function, we have a linear program in $(\eta_1, \eta_2)$

$$\begin{array}{ll} \text{minimize} & \mathrm 0_3^T \eta_1 + \mathrm 0_3^T \eta_2 \\ \text{subject to} & \begin{bmatrix} | & | & |\\ \mathrm a_1 & \mathrm b_1 & \mathrm c_1\\ | & | & |\end{bmatrix} \eta_1 - \begin{bmatrix} | & | & |\\ \mathrm a_2 & \mathrm b_2 & \mathrm c_2\\ | & | & |\end{bmatrix} \eta_2 = \mathrm 0_2\\ & 1_3^T \eta_1 = 1\\ & 1_3^T \eta_2 = 1\\ & \eta_1, \eta_2 \geq 0_3\end{array}$$

If the linear program is infeasible, then the intersection of the two triangles is empty.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you clarify what you mean by the | symbols in the matrices? $\endgroup$ – NietzscheanAI Sep 30 '16 at 15:04
  • $\begingroup$ @NietzscheanAI The |'s merely emphasize that $\mathrm a_i, \mathrm b_i, \mathrm c_i$ are column vectors, not scalars. $\endgroup$ – Rodrigo de Azevedo Oct 1 '16 at 2:00
  • $\begingroup$ While elegant and interesting, I am unsure it answers the initial question because I do not think that "the problem being feasible" can be turned into a constraint for CPLEX, is there a way of doing that ? (I'd be interested !) $\endgroup$ – BrunoLevy Mar 28 '17 at 9:29
  • $\begingroup$ @BrunoLevy Can't CPLEX solve linear programs? If a linear program is infeasible, can't CPLEX find it out? I never used CPLEX. I know that MATLAB's linprog returns exitflag=-2 if infeasible. $\endgroup$ – Rodrigo de Azevedo Mar 28 '17 at 12:07
  • $\begingroup$ @Rodrigo de Azevedo Certainly it can, but I think that the question was: how can I optimize an objective function F(a1,b1,c1,a2,b2,c2) subject to constraint C: there is an intersection between triangles (a1,b1,c1) and (a2,b2,c2) (instead of answering the question "is there an intersection ?"). Can your formulation do that ? (it would be nice, because it's more elegant !) $\endgroup$ – BrunoLevy Mar 28 '17 at 20:06
1
$\begingroup$

For each triangle edge, add a linear constraint corresponding to the equation of the line containing the edge such that the other point is on the correct side.

For example, if the line containing the edge $a_1b_1$ is given by $L(x,y)=0$, then add the constraint $L(c_1)L(x,y) \ge 0$.

$L(x,y)$ is given by $((x,y)-a_1) \times (b_1-a_1)$, where $\times$ is the 2-dimensional vector product.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ But I think that there are several non-trivial combination of relative "correct sides", for instance one triangle can be completely inside the other, or there can be one vertex of one triangle inside the other one. There is even a configuration where no triangle vertex is inside the other one (two intersecting triangles forming a 6-branches star). $\endgroup$ – BrunoLevy Sep 10 '15 at 21:30
  • $\begingroup$ @BrunoLevy - if it's clear to you how the above should be modified in the light of your comment, would you be kind enough to add it as an answer? $\endgroup$ – NietzscheanAI Sep 12 '15 at 6:59
  • $\begingroup$ @lhf - I believe there are a number of possible interpretations of `2D vector product' (e.g. stackoverflow.com/questions/243945/…). Could you kindly be explicit about the definition? $\endgroup$ – NietzscheanAI Sep 12 '15 at 7:32
  • $\begingroup$ @user217281728, I have entered an answer (it is not very elegant, but I did not find a shorter formula) $\endgroup$ – BrunoLevy Sep 12 '15 at 9:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.