2

I have a set of cartesian x,y points which I know am fairly certain are on the edges of a triangle. What is the easiest way (either algebraically or algorithmically) to identify what the three vertices of the triangle are? The set of points may or may not include the vertices.

Edit: The set of points will have at least 100, probably more (depending on the case) points in it.

Richard
  • 123

2 Answers2

1

Build the convex hull of the set.

Then discard all sites that form a (quasi-)flat angle. There will be three to six vertexes left (depending on the number of corners in the set) and finding the three sides among them shouldn't be an issue.

In this particular case, the Jarvis march could be used alternatively to the Graham scan, as the convex hull is expected to count $6$ sites at most.

0

If none of the edges of a triangle and none of the vertices of this triangle sit on a straight line then this straight line has exactly two common points with the triangle if it has at least one common point with it.

Let your points be listed in an array. Let the points in the list denoted by $A_i$. Take the straight line determined by $A_1$ and $A_2$. If $A_k$ is the first point in the list that is on this straight line then you get the equation of a straight line belonging to an edge. If there is no such $A_k$ then the first two points in the list don't belong to one edge. If this is the case then take $A_1$ and $A_3$ an repeat the previous procedure. If there is no suitable $k$ then go on with $A_1$ and $A_4$. It is impossible that you go through the whole list and never find a suitable $A_k$ if we may assume that there are at least three points on each edge.

Having found the straight line belonging to one of the edges find the first point in the list that did not belong to the straight line already found. Place this point at the beginning of your list and start the whole procedure over again. You will find the equation belonging to another edge.

Repeat all this once again.

At the end you will have three straight lines whose intersection points will be the vertices of your triangle.

zoli
  • 20,452
  • This seems to be an $O(n^3)$ procedure, pretty expensive. –  Jul 06 '15 at 12:19
  • @YvesDaoust: I know that. But the question did not seem to be related to computation theory. Besides, it asked for the easiest way and not the "smartest" way. – zoli Jul 06 '15 at 12:29
  • 1
    The convex hull solution is both efficient and very easy to program. –  Jul 06 '15 at 12:37
  • @YvesDaoust: I don't dispute your priority : ). Furthermore, I am not a computer scientist. Third, I am glad that I've learned something. Just for fun, I will study the convex hull algorithm. – zoli Jul 06 '15 at 12:40
  • @YvesDaoust: BTW: What is the speed of the convex hull algorithm? – zoli Jul 06 '15 at 12:42
  • You need to first sort the points, which takes $O(n\lg(n))$, then the so-called Graham scan gives you the convex hull in linear time $O(n)$. Anyway, this instance of the problem is a little special in that it is known that the sites lie on the sides of a triangle. So in theory, a better approach should be the "Jarvis march", as it would perform in linear time $O(n)$ as well. –  Jul 06 '15 at 12:45
  • @YvesDaoust, THX. – zoli Jul 06 '15 at 12:50