# Avoiding Concave Polygons

In a vertex model, vertices in a lattice are modelled by a set of ODEs. A T1 transition is the following: when a certain edge becomes small enough (given a threshold), two cells stop being connected, while two other cells become connected, as shown here

Usually, in a vertex model, the new edge is taken to be perpendicular to the old one (and slightly longer). However, in some cases (specially when the tissue is stretched), this causes some cells to become concave. I wonder if we could avoid this. Instead of taking a perpendicular edge, defining a certain angle with respect to the previous edge seems to solve it for some cases:

Perhaps by determining such angle in terms of the slopes of the nearby edges we could generalize this idea, but I'm not too sure how to geometrically argue. For instance, consider 4 vertices $$v_1,v_2,v_3,v_4$$ and $$c_1,c_2$$ defining the following polygons

where $$c_m$$ is the midpoint of the line segment going from $$c_1$$ to $$c_2$$. When the angle chosen for the T1 transition is $$\pi/2$$, we get, for new vertices $$c_1',c_2'$$ and under the simplifying assumption that $$v_1,v_2,v_3,v_4$$ do not change,

However, when we pick a slightly noisier mesh, we get

Which yields at least one concave region (polygon defined by vertices $$v_1,v_3,c_1',c_2'$$). Using, again, the angle $$\pi/4$$, we get a better result

Naturally this concavity also depends on the length of the new edge, but I was wondering if it could be possible to construct it in such a way that we'd avoid concavity.

Note: The code for the above is given by:

T1F = Function[{v1, v2, v3, v4, c1, c2, angT1},
vl = {v1, v2, v3, v4}; cl = {c1, c2};
cm = Midpoint[cl];
lv1c1 = {v1, c1}; lv2c2 = {v2, c2}; lv3c1 = {v3, c1};
lv4c2 = {v4, c2};
lv1v3 = {v1, v3}; lv1v2 = {v1, v2}; lv2v4 = {v2, v4};
lv3v4 = {v3, v4};
lc1c2 = {c1, c2};
lvc = {lv1c1, lv2c2, lv3c1, lv4c2, lc1c2};
lvcc = {lv1v3, lv1v2, lv2v4, lv3v4};
cln = With[{midPt = cm},
midPt + .5 Normalize[(# - midPt)] & /@
Flatten[RotationTransform[angT1, midPt] /@ {lc1c2}, 1]
];
c1n = cln[[2]]; c2n = cln[[1]];
lv1c1n = {v1, c1n}; lv2c1n = {v2, c1n}; lv3c2n = {v3, c2n};
lv4c2n = {v4, c2n};
lvcn = {lv1c1n, lv2c1n, lv3c2n, lv4c2n};
lc1nc2n = {c1n, c2n};

pl = {.18, .07};

gr1 = Graphics[{
Line /@ Join[lvc, lvcc],
PointSize[Large], Point /@ Join[vl, cl],
Text[
StringForm["\!$$\*SubscriptBox[\(v$$, $$$$]\)",
Position[vl, #][[1, 1]]], pl + #] & /@ vl,
Text[
StringForm["\!$$\*SubscriptBox[\(c$$, $$$$]\)",
Position[cl, #][[1, 1]]], pl + #] & /@ cl,
Red, PointSize[Large], Point[cm],
Red, Text["\!$$\*SubscriptBox[\(c$$, $$m$$]\)", pl + #] & /@ {cm}
}];
gr2 = Graphics[{
Line /@ Join[lvcn, lvcc],
Text[
StringForm["\!$$\*SubscriptBox[\(v$$, $$$$]\)",
Position[vl, #][[1, 1]]], pl + #] & /@ vl,
PointSize[Large], Point /@ vl,
Red,
Text[StringForm["c\!$$\*SubscriptBox[\('$$, $$$$]\)",
Position[cln, #][[1, 1]]], pl + #] & /@ cln,
Red, PointSize[Large], Point /@ cln,
Red, PointSize[Large], Point[cm],
Red,
Text["\!$$\*SubscriptBox[\(c$$, $$m$$]\)", pl + #] & /@ {cm},
Red, Line@lc1nc2n
}];

Grid[{{gr1, "\[LongRightArrow]", gr2}}]];

v1 = {0, 0}; v2 = {0, 3}; v3 = {2, 0}; v4 = {2, 3};
c1 = {1, 1}; c2 = {1, 2};
T1F[v1, v2, v3, v4, c1, c2, Pi/2]

v1 = {0.5, 1.2}; v2 = {0, 2.3}; v3 = {2.3, 2}; v4 = {1.7, 3};
c1 = {1.5, 1.9}; c2 = {.9, 2.2};
T1F[v1, v2, v3, v4, c1, c2, Pi/2]
T1F[v1, v2, v3, v4, c1, c2, Pi/4]

• @MarcoB I've edited the question to include a simplified version of the code. Please take a look Commented Oct 30, 2021 at 21:34
• Thank you for adding the code! Commented Oct 31, 2021 at 1:50

The logic might need some tweaking depending on the order of the points, but for these examples, it works. Essentially, replace the computation of the two new endpoints cln with the following:

cln = With[{midPt = cm},
midPt + .5 Normalize[(# - midPt)] & /@
Flatten[RotationTransform[\[Pi] -
Max[PlanarAngle[midPt -> lv1c1], PlanarAngle[midPt -> lv4c2]],
midPt] /@ {lc1c2}, 1]]


This works by realizing that we have to rotate $$\overline{c_1c_2}$$ at least "over" $$\overline{c_mv_1}$$ and $$\overline{c_mv_4}$$. We do this by computing $$\angle c_1c_mv_1$$ and $$\angle c_2c_mv_4$$, and taking their max. (We have to compute $$\pi-\theta$$ from that to account for your choice of connectivity of the resulting network, this could be removed if we computed $$\angle c_1c_mv_4$$ and $$\angle c_2c_mv_1$$ instead)

To improve it, the angle could be made a bit larger (so that the resulting edges are not straight).

The minimal angle required to make the other sides not concave is similarly given by $$\angle c_1c_mv_3$$ and $$\angle c_2c_mv_2$$. In total, we therefore can do

lv4c1 = {v4, c1};
lv1c2 = {v1, c2};
cln = With[{midPt = cm},
midPt + .5 Normalize[(# - midPt)] & /@
Flatten[RotationTransform[2 \[Pi] - Mean@{
Min[PlanarAngle[midPt -> lv3c1],
PlanarAngle[midPt -> lv2c2]],
Max[PlanarAngle[midPt -> lv4c1], PlanarAngle[midPt -> lv1c2]]
}, midPt] /@ {lc1c2}, 1]]


This computes the mean of the minimal and maximal angle by which we can rotate, resulting in the following:

To see why this works, consider the following:

Clearly, $$c_1$$ must be in $$\Delta c_mv_3v_4$$, so the rotation angle must be between the red and green one ($$\angle c_1c_mv_3$$ and $$\angle c_1c_mv_4$$). Same for $$c_2$$ in $$\Delta c_mv_2v_1$$ with angles $$\angle c_2c_mv_2$$ and $$\angle c_2c_mv_1$$.

• This is interesting and indeed I think guarantees me convexity. However, I'd like to define the threshold angle after which concavity is lost, if that's understandable. I could then take the mean angle of that interval. For example, in the first case, which is somewhat symmetric, that mean would be $\pi/2=(\theta+(\pi-\theta))/2$. But it's not so obvious in the other case. I suspect the slopes of the adjacent edges might be enough to determine that, but I'm not sure. Hope this was more or less clear. Commented Oct 31, 2021 at 0:12
• @samwolfe See the update Commented Oct 31, 2021 at 8:35
• Great! Thank you so much. I guess a future issue is to adjust the re-scaling factor of the new edge. Can't be small enough, otherwise the vertex model goes in a loop, and can't be too large, "destroying" the polygonal cells. But nonetheless your approach should solve it for most cases. Commented Nov 1, 2021 at 13:17