# How to label the intersection of edges in arbitrary four-sided shapes?

I have a very deep understanding of mathematics but have not read so many papers. Has anyone encountered a related problem?

I want to label four corners of four-sided shapes as top-left, top-right, bottom-right and bottom-left. The edges of these shapes are not parallel. It may seem a trivial task to label each corner, but there are shapes which is hard to find each corner. For instance, the following shape shows an example which is easy to be labelled. On the contrary, I have the following shape which is not easy to find out which corner is which of the mentioned. I'm aware of the approach which assigns top-left to the min(x+y) and bottom-right to max(x+y) but it is not appropriate due to the fact that I have shapes like the following shape. I don't know whether there is an approach to label these intersections correctly.

• what does it mean to label? – John Glenn Jul 17 '18 at 13:38
• Labelling means assigning each of the four mentioned points, like top-left, to each of the vertices. It's an ML term :) – Media Jul 17 '18 at 13:46

I think we can assume that the quadrilaterals you are interested in are convex because otherwise the naming of the corners would be very peculiar. Still, there will be cases where the naming will be problematic. Since we have a convex polygon, the corners are in circular order. For example, starting at the top-left corner and going clockwise, we encounter the top-right, bottom-right, and bottom-left corners, in that order. All we need to do is identity just one of the corners.

So first, find a corner with the maximum $y$ value. This corner has two adjacent corners and if one of these two corners has a greater $y$ value than the other corner, then the two corners with $y$ values greater than the remaining two corners will be on top. The top corner with smaller $x$ value will be on the left and the other corner on the right. Similarly for the remaining two bottom corners.

Note that there can not be three corners with the maximum $y$ value because of convexity which prevents three collinear corners. In case there is just one corner with the maximum $y$ value, and therefore on top, and if the two adjacent corners both have the same $y$ value, then you could choose the closest adjacent corner to also be on top.

Here is a summary. Suppose the $y$ values of the four corners in decreasing order are $A,B,C,D.$

• By convexity we can not have $A = B = C.$
• If $A = B > (C,D),$ then both $A$ and $B$ are on top.
• If $A > B=C > D,$ then $A$ and one of $B$ or $C$ are on top.
• If $A > B > (C,D),$ then both $A$ and $B$ are on top.
• Thanks for your response. Would you mind explaining more? – Media Jul 17 '18 at 13:51
• What parts need more explaining? – Somos Jul 17 '18 at 14:20
• Which point is going to be top-left? I guess if you consider the first shape you may have some points with equal y values. – Media Jul 17 '18 at 14:34
• "The top corner with smaller x value will be on the left and the other corner on the right". – Somos Jul 17 '18 at 14:38
• @Media The art of writing clearly and understandably is not an easy one. I am always trying to improve my writing. In many cases, feedback from readers is helpful and a motivator for improvement Thanks. – Somos Jul 17 '18 at 19:43

(In these circles the $x$-axis points to the right, and the $y$-axis points upwards.)

Singling out "top left" means the first vertex is where we begin to read the page of a book.

This amounts to the following rule: We are given four points $P_k$ by its coordinates $(x_k,y_k)$ $(1\leq k\leq 4)$, and it is assumed that they form a convex quadrilateral $Q$. If there is just one point $P_k$ with maximal $y_k$ this point is TL . If there are several points $P_k$ with maximal $y_k$ the leftmost of these is TL. Counting from TL clockwise give the following vertices of $Q$ the names TR, BR, BL.

• Thanks a lot for your responce. Please take a look at the last image. With what you have referred, the top right edge would be top left. – Media Jul 17 '18 at 17:00
• "where we begin to read the page of a book": that's a possible interpretation but there is not enough information in the question to be sure. – Yves Daoust Jul 17 '18 at 19:01

As you show by your examples, there is no well defined solution. In particular, for a perfect diamond shape, it is impossible to assign these labels.

The way to handle this difficulty is to understand why you are trying to assign the labels. And probably you will realize that you are not asking the right question.

Now I know that the problem at hand is to establish the correspondences of the four corners of the rectangle when seen in perspective.

I confirm that with just the coordinates of the corners this is impossible, because rotation up to a quarter turn is allowed.

Either you must make hypothesis on the possible pose. For instance if the rotation is small, the smallest $x+y$ indeed gives you the top-left corner. If the rectangle is very different from a square, and perspective remains reasonable, you can even tell larger rotations by determining the longest sides.

Other approaches is by using clues from the document, such as the direction of the rows of text. But telling upside-down document will require to perform OCR !

• @Media: what is the solution in case of a diamond ? And why ? – Yves Daoust Jul 17 '18 at 18:55
• @Media: the $x+y$ rule can fail. There are configurations with two points achieving the same sum. If you keep not telling what the purpose is, I can't help you. – Yves Daoust Jul 17 '18 at 18:59
• @Media: you will not find a satisfactory solution, believe me. The key is in the "why" you want this labeling. – Yves Daoust Jul 17 '18 at 19:03
• @Media: ML will be of no help, the problem is of a mathematical nature. My bet is that you just want to find correspondences. – Yves Daoust Jul 17 '18 at 19:05