Find the Vertices of a Triangle from Set of Points

Question

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.

Answer 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.

Answer 2

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.