3
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ The order of the points certainly does matter if the quadrilateral is concave. (I assume by simple you mean non-self-intersecting, so concave quadrilaterals are simple.) $\endgroup$ – TonyK Jul 25 at 17:13
  • $\begingroup$ We may be able to help more if you edit the question to provide some context. Why do you need a unique way to describe these non-intersecting quadrilaterals? $\endgroup$ – Ethan Bolker Jul 25 at 17:17
  • $\begingroup$ Oh yes you are right! I’m only dealing with convex quadrilateral though, I edited my question, thanks! $\endgroup$ – Neabfi Jul 25 at 17:17
  • $\begingroup$ The representation of the polynomial will be used as the output of a neural network. For now I’m computing all the possible losses (the L1 distances (vertex-wise ) between the ground truth polynomial and all the permutations of the vertices of the predicted polynomial) and I take the smallest one. $\endgroup$ – Neabfi Jul 25 at 17:20
  • 2
    $\begingroup$ There is a smell of XY question. If your need is to find the best matching between two quadrilateral, you should ask that question, which seems easier. $\endgroup$ – Yves Daoust Jul 25 at 18:02
1
$\begingroup$

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)$).

$\endgroup$
  • $\begingroup$ A nice list. I'm assuming that by "shortest side," you mean "length of shortest side" (although the vector (mod $\pm 1$) along the side is also order independent). I have one concern, which is that the direction of the shortest and longest diagonal are not well-defined for rectangles (because the two diagonals are equal in length, so either could be the "shortest"). If the OP wants a continuous map to the space of representations, this could be a problem. $\endgroup$ – John Hughes Jul 25 at 19:03
  • $\begingroup$ @JohnHughes: right, there is no perfect solution (and I do mean length of…) $\endgroup$ – Yves Daoust Jul 25 at 19:04
  • $\begingroup$ What do you mean by "determine the convex hull"? What would be the output of such a determination? $\endgroup$ – TonyK Jul 27 at 14:37
  • $\begingroup$ @TonyK: ordered vertices. $\endgroup$ – Yves Daoust Jul 27 at 17:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The trouble with your first suggestion is that it is very sensitive to small changes: if $A$ and $B$ have nearly the same $x$-coordinate, then $A,B,C,D$ can become $B,A,C,D$ if $A$ or $B$ change only slightly. This is no good for scoring the output of a neural network. (Not that I have a better suggestion.) $\endgroup$ – TonyK Jul 25 at 17:45
  • $\begingroup$ @TonyK Maybe the loss shouldn't be a distance between the points, but something like Area(predicted $\cup$ ground truth) - Area(ground truth $\cap$ predicted) (the IoU en.wikipedia.org/wiki/Jaccard_index). But your comment is really important! $\endgroup$ – dcolazin Jul 25 at 17:50
  • $\begingroup$ Your second method has the same drawback: the choice of "first" diagonal is sensitive to small changes. $\endgroup$ – TonyK Jul 25 at 18:08
  • $\begingroup$ @TonyK and again, you are right! $\endgroup$ – dcolazin Jul 25 at 18:10
  • $\begingroup$ OP did not ask for a continuous mapping to the representation. $\endgroup$ – John Hughes Jul 25 at 18:20
0
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ The quadrilateral is known to be convex. $\endgroup$ – Yves Daoust Jul 25 at 17:58

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.