Given the co-ordinates of several points, how to determine which segments are sides and which are diagonals

Question

My geometry text sometimes asks some question about a polygon defined by the coordinates of the vertices. For example, we might be given the coordinates of four points and asked whether they are the vertices of a rectangle. The model answer might involve checking whether the diagonals are congruent.

Each time I solve a problem like this I wonder whether it is necessary to graph in order to determine which segments will be sides and which will be diagonals. The students always assume that the points are stated in order, so that non-consecutive vertices lie on diagonals. And this is in fact how the problems always seem to turn out.

Is there an easy comparison of the coordinates that reveals where the sides and diagonals are?

Is there a set of n points that can be the vertices of more than one n-gon, so that two of these points will lie on either a side or a diagonal, depending on the order in which the points are named? Are some sets of points "ambiguous" in this way, and some sets unambiguous? Is that ambiguity also easily detected?

Answer 1

From the wording of your questions you silently assume that the points lie within a single plane. Then you could check any pair of points, deriving the being spanned line, whether all the remaining points lie on a single side of that line. If so the segment between those 2 points would be a part of the hull polygon; else that line segment would be internal. Note that also some of the provided points might lie within the internal of that hull!

When considering the same problem in any arbitrary dimensional setting, you first would have to detect the dimension d of the span of those points. Then you would have to consider any subset of d points instead, which again would define a containing hyperplane. Again you would have to check whether there are all remaining points on a single side thereof. This, if positive, would provide you one by one with the facets of the hull.

--- rk

Answer 2

Here is a general way to compare the coordinates which reveals the sides and diagonals of a convex n-gon, as well as the order of the points (if unknown).

Consider a square oriented anywhere on the Cartesian plane with points ABCD, which do not necessarily have to be named in order.

Each of these points can be described as a vector centered at the origin: $A$, $B$, $C$, $D$.

Since the coordinates are with respect to the origin, the vectors have components equal to the coordinates of the vertices:

Rewrite the coordinates of the vertices as vectors from the origin.

Now, we can choose an arbitrary vertex and relate the coordinates of the other vertices through vector subtraction. In my image, I use a random vertex, which happens to be point A, and write vectors which originate from A and point to the other vertices.

Recall that since our vectors point from O to A and O to B, then a vector which points from A to B will be equal to $(B - A)$ Likewise, a vector which points from A to C is $(C-A)$, and a vector which points from A to D is $(D-A)$.

Relate the line segments from our arbitrary vertex to the other vertices of the polygon in terms of vectors.

At this point, we can determine which sides of the square are sides and which is the diagonal by taking the magnitude of each of the vectors $\left\lVert(B-A)\right\rVert$, $\left\lVert(C-A)\right\rVert$, and $\left\lVert(D-A)\right\rVert$.

In a square, the two sides will have equivalent magnitude which is shorter than the magnitude of the diagonal. In the image above, $\left\lVert(C-A)\right\rVert$ > $\left\lVert(B-A)\right\rVert$ = $\left\lVert(D-A)\right\rVert$. So we can conclude that AC is a diagonal while AB and AD are sides.

Now, consider a regular hexagon oriented anywhere in the Cartesian plane. We can rewrite the coordinates of each vertex as a vector extending from the origin in the same manner as before. Then, we can choose an arbitrary vertex and relate the line segments from that vertex to all of the other vertices using vector subtraction as shown in the following image:

Relate the line segments from our arbitrary vertex to the other vertices of the polygon in terms of vectors.

Since this is a regular polygon, we can simply calculate the magnitude of each of these vectors (which represent the line segments from an arbitrary vertex to the remaining vertices). In the case of a hexagon, the diagonal will be the vector with the largest magnitude, while the sides will be the two vectors with the shortest magnitudes.

In my image, $\left\lVert(D-A)\right\rVert$ > $\left\lVert(C-A)\right\rVert$ = $\left\lVert(E-A)\right\rVert$ > $\left\lVert(B-A)\right\rVert$ = $\left\lVert(F-A)\right\rVert$, therefore, AD is the diagonal while AB and FA are sides.

Notice, however, that there are some vectors whose magnitudes are in between the maximum and minimum magnitudes. If you were to trace a path from A to D along the perimeter of the polygon, then these vectors represent the points which are between A and D along the perimeter.

This method only using the magnitude of the vectors is only sufficient for regular polygons, however, if the polygon is irregular yet convex, it is still worthwhile to calculate these magnitudes so that they can be used in the following analysis.

Consider an irregular yet convex hexagon oriented in the Cartesian plane. If we rewrite the coordinates of the vertices as vectors extending from the origin, we can choose an arbitrary vertex and rewrite the line segments from that vertex to the remaining vertices using vector subtraction as shown in the image:

Relate the line segments from our arbitrary vertex to the other vertices of the polygon in terms of vectors.

However, in this case, simply knowing the magnitude of the vectors will not be enough to determine which vertices are sides and which are diagonal, if any. Instead, we must use the fact that a convex polygon never "backtracks".

Consider if you draw a unit circle around a vertex and travel along the perimeter of the polygon, drawing rays in the direction of the vertex about which the unit circle is located. As you travel from 0 to the length of the perimeter, the projections of these rays onto the unit circle are monotonic, meaning they always go in one direction, never back tracking, even if the distance between the projections changes. This fact can be exploited to determine the order of the points by using the dot product.

The formula for the dot product for two vectors $u$ and $v$ can be rerranged to solve for the angle between two vectors by: $$\theta = cos^{-1}(\frac{u\cdot v}{\left\lVert(u)\right\rVert\left\lVert(v)\right\rVert})$$

We can use this equation to determine the angles between each of the rays extending from our arbitrary vertex to the other vertices in order to deduce the positions of the vertices relative to eachother.

Take an arbitrary vector representing the line segment from our vertex to any of the other vertices. Lets choose at random to use the line segment EA with the corresponding vector $(E-A)$ as a test.

We take the dot product of $(E-A)$ with all of the other vectors which represent the line segments from the arbitrary vertex to the remaining vertex, then divide by the product of their magnitude, finally taking the inverse cosine.

This results in angles which describe the angles between our test ray, $(E-A)$, with the other rays. The maximum and minimum angles represent the rays whose corresponding line segments are directly adjacent to the test vertex.

If there are no negative angles or all negative angles, than the test ray happens to be the vector representing the line segment of one of the sides adjacent to your test point.

If there are some negative angles and some positive angles, then realize that the most negative and most positive angles represent the sides adjacent to the test vertex. If you want, you can take subtract the most negative angle from each of the angles in order to normalize them (make them all positive).

If you want to see if there is a point diagonal to your test point, then you can take $(\frac{\theta_{max} - \theta_{min}}2)$, which represents the angle bisecting the line segments adjacent to your test point. The ray with this angle is diagonal to the test vertex. Note that this method right here only determines if a point is diagonal to our test point A, from which we drew our rays.

In order to find the longest total distance between any two of the vertices, you can use the law of cosines using the information calculated so far. For example, our test point was A, but if you wanted to know the distance between B and E, you can perform a SAS (side-angle-side) law of cosines calculation because you know the lengths of the line segments AB, which is $\left\lVert(B-A)\right\rVert$, and AE, which is $\left\lVert(E-A)\right\rVert$, as well as the angle between them $\left\lvert\theta_4\right\lvert + \left\lvert\theta_3\right\lvert + \left\lvert\theta_2\right\lvert$.

I wont perform the calculation here, but you can perform this SAS law of cosines measurement for each of the possible combinations of vertices and determine which is the longest.

Answer 3

I'm not totally clear whether this post is a question or an answer, but as I discussed this topic today it all seemed so clear.

Why won't this do the trick?

First, let's assume that the four given points include no three co-linear points. Then, let's choose to name the points clockwise from 12:00.

1. Choose (for the first point) that point with the greatest y-value. If there is a tie for this distinction (if two points have the same y-value and the other two points have smaller y-values) then of the two points tied for first, prefer the one with the smaller x-value.

2. Choose (for the second point) any remaining point with the y-value of the first point; and if there is none, choose the remaining point with the greatest x-value. If there is a tie for this distinction, then of the two points tied for first, prefer the one with the greater y-value.

3. Choose (for the third point) any remaining point with the x-value of the second point; and if there is none, choose the remaining point with the smaller y-value. If there is a tie for this distinction, then prefer the one with the greater x-value.

4. Choose (for the fourth point) the one remaining point.

Will that always identify the sides correctly, making the odd-number points the endpoints of one diagonal?