unique description of a convex quadrilateral

Question

I’m looking for a unique way to describe a convex quadrilateral. The common way to express a quadrilateral is to give the four vertices: $[(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)]$. The problem I have is that if we know that we are looking for a convex quadrilateral, the order of the points doesn’t matter and thus $[(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)]$ describes the same quadrilateral than $[(x_2, y_2), (x_1, y_1), (x_3, y_3), (x_4, y_4)]$. Is there a better notation for a convex quadrilateral?

Answer 1

A way is to define a total order on $\mathbb{R}^2$ so the order of the points $p_1, \ldots, p_4$ is determined. For example $(x_1, y_1) < (x_2, y_2) \iff (x_1 < x_2)$ or $(x_1 = x_2, y_1 < y_2)$. Then the representation is $(p_1, \ldots, p_4)$ with $p_1 < p_2 < p_3 < p_4$.

A worst(?) way (I don't know if the neural network will be able to learn this representation) is: point of intersection of the diagonals, the angle between the $x$ axis and the "first" (counterclockwise, for example) diagonal, the angle between diagonals, length of the first diagonal , length of the second diagonal.

As TonyK noted in a comment, this kind of representation is not really robust. Using a loss similar to the Jaccard distance might be more useful than a $L^p$ loss between vertices.

To better understand if the second representation can be actually used in real life applications, it might me interesting to study how "non-rectangular" bounding boxes are represented. Maybe a study of the literature about regionlets can help you.

Answer 2

For a convex quadrilateral, an unordered set of four points $\{(x_1,y_1),(x_2,y_2), (x_3,y_3), (x_4,y_4) \}$ defines a quadrilateral uniquely, so this notation is fine.

For a concave quadrilateral however, four points do not determine the quadrilateral uniquely, so you can do a couple of things.

1) You can order the points $((x_1,y_1),(x_2,y_2), (x_3,y_3), (x_4,y_4) )$ and define the quadrilateral they represent by starting at the first point, then drawing a line to the second, then to the third, to the fourth, and then back to the first. or,

2) You can represent the edges of the quadrilateral (but this is a bit longer) in the form $\{ \{(x_1,y_1), (x_2,y_2)\},\{(x_2,y_2), (x_3,y_3)\},\{(x_3,y_3), (x_4,y_4)\},\{(x_4,y_4), (x_1,y_1)\} \}$. (You only need to store 3 edges in fact, as the last will be uniquely determined)

Answer 3

Make sure to order the four vertices in the same traversal order (it is a simple matter to determine the convex hull of four points). Doing so, you reduce the number of permutations from $24$ to $4$.

---

To describe the quadrilateral, you need 8 parameters, as there are 8 degrees of freedom. The following ones are order independent:

• coordinates of the centroid (the mass can be uniform, uniform along edges or concentrated at vertices);

• higher order moments;

• coordinates of the intersection of the diagonals;

• area;

• perimeter;

• shortest and longest side;

• shortest and longest diagonal;

• ratios of the above;

• directions of the above segments (in range $[0,\pi)$).

Answer 4

As the answers here show, there doesn't seem to be an elegant representation of quadrilaterals that gives you a simple expression for the difference between them. So brute force is probably the best solution. But it's not so expensive. Here is how I would do it:

1. Get the quadrilaterals in clockwise form, $ABCD$ and $EFGH$.

2. We define the distance between $ABCD$ and $EFGH$ to be $$|A-E|^2+|B-F|^2+|C-G|^2+|D-H|^2$$ (the squaring makes the arithmetic much simpler). So this is $$(x_A-x_E)^2+(y_A-y_E)^2+(x_B-x_F)^2+(y_B-y_F)^2+(x_C-x_G)^2+(y_C-y_G)^2+(x_D-x_H)^2+(y_D-y_H)^2$$ $$=\sum_{i\in\{A,B,C,D,E,F,G,H\}}(x_i^2+y_i^2)-2(x_Ax_E+y_Ay_E+x_Bx_F+y_By_F+x_Cx_G+y_Cy_G+x_Dx_H+y_Dy_H)$$ The nice thing about this is that the sum of squares is independent of the choice of $EFGH$. So you only need to compute it once.

3. Compute the above for the four quadrilaterals $EFGH, FGHE, GHEF,$ and $HEFG$. Take the minimum. And in fact if all you need to know is which is the best, you don't even need to compute that sum of squares.

I realise that step 1 is not as simple as all that, whatever Yves Daoust says. Can you assume that your neural network outputs quadrilaterals in clockwise form? Or at least in consecutive (i.e. clockwise or anticlockwise) form? If not, let me know in the comments, and I will try to expand step 1.