CODEWITHSUNDEEP
computational-geometryeuclidean-distanceanalytic-geometry
Lori
Lori

Reputation: 1422

Analytic geometry, ordering vertices of triangle to capture shortest and second shortest sides

If I have x and y coordinates for triangle corners A, B, and C, I want to know which of the six orderings of {A, B, C} put the shortest side of the triangle between the first two vertices in the ordering, and the second shortest side between the last two. I know how to solve this, but not in a way that isn't clumsy and inelegant and all around ugly. My favorite language is Ruby, but I respect all of them.

Upvotes: 0

Views: 110

Answers (2)

user1196549
user1196549

Reputation:

  1. As the third side of a triangle cannot be deduced from the other two, you must compute the three distances.

  2. As the three points may require to be permuted in one of six ways, you cannot work this out with a decision tree that has less than three levels (two levels can distinguish at most four cases).

Hence, compute the three distances and sort them increasingly using the same optimal decision tree as here: https://stackoverflow.com/a/22112521/1196549 (obviously their A, B, C correspond to your distances). For every leaf of the tree, determine what permutation of your points you must apply.

For instance, if you determine |AB|<|CA|<|BC|, you must swap A and B. Solve all six cases similarly.

Doing this you will obtain maximally efficient code.

If you are completely paranoid like I am, you can organize the decision tree in such a way that the cases that require a heavier permutation effort are detected in two tests rather than three.

Upvotes: 1

MyStackRunnethOver
MyStackRunnethOver

Reputation: 5275

Here's how I would do it: let's take a triangle with sides x, y, and z, such that l(x) <= l(y) <= l(z). Then, let x', y', and z' be the vertices opposite to x, y, and z, respectively.

Your output will be y', z', x' (if you draw out your triangle, you'll see that this is the order which achieves your requirement). So, the pseudocode looks like:

  1. For points a, b, c each with some coordinates (x, y), calculate the length of the segment opposite to each point (e.g. for a this is segment bc)
  2. Order a, b, c by the length of their opposing segment in the order of [2nd longest, longest, shortest]
  3. Return

Does this make sense? The real work is mapping to the euclidean distance between the opposing points. If you get stuck, update your question with your code and I'm happy to help you work it out.

Upvotes: 1

Related Questions