Very Computer

>Anyone know how to fit a triangle to a scattered set of points in a
>plane?

> >Anyone know how to fit a triangle to a scattered set of points in a
> >plane?

> Are you looking for a least-squares type of fit or are you looking for
> minimum area triangle containing the points?

>Least squares fit would be ideal, I'm really after a representative
>triangle. What I know about the points are that they should lie on the
>perimeter of the triangle. The full complement of data points includes
>those at the vertices however for a robust determination I must assume
>they may not always be present. Any help, pointers, ideas etc would be
>much appreciated.

> Here is an algorithm that should work (unless you have a random set of
> points that are not even related to a triangle).  It works in two steps, the
> first similar to a Hough transform and the second using a least squares fit
> by lines.  The first step is computationally expensive and requires some
> parameters to be specified by the application.  If speed is another
> requirement, let me know and I'll look at a way to make the first step more
> efficient.

> Algorithm.
>   1a. Compute the average of the data points, call this point C.
>   1b. Compute the largest distance RMAX between the data points and C.
>   1c. Create an NxM array of unsigned integers (N and M are user-specified).
>         Let Count(i,j) be the ij-th element of the array (0 <= i < N, 0 <= j
> < M).
>         Set R = i*RMAX/N and A = j*2*PI/M.  Count(i,j) is the number of
> sample
>         points that lie in the infinite strip whose width is W
> (user-specified) and
>         whose axis is the line tangent to the circle of radius R centered at
> C at
>         the point C+R*(cos(A),sin(A)).
>   1d. The goal is to find 3 pairs (i0,j0), (i1,j1), and (i2,j2) for which
> the Count
>         values are large local maxima.  One way of doing this is to
> threshold the
>         Count array (threshold value T is user-specified) and constructing a
> set
>         of binary regions for which Count(i,j) >= T (hopefully 3 regions).
> A good
>         choice for T is the number of expected samples to lie on each edge.
>   1e.  For each of the 3 regions, average (and round) the indices to get
> pairs
>         (i0,j0), (i1,j1), and (i2,j2).  Use each strip axis as the line
> containing a
>         triangle edge.  Find the points of intersection of the edges to get
> the
>         vertices of the triangle.
>   2.   You could also choose to do a "polishing" step by taking each strip
> and
>         fitting the data points in that strip by a line using orthogonal
> regression.
>         Then find the points of intersections of those lines to get the
> triangle
>         vertices.

> I've coded this up and it seems to work okay.  The expense is in computing
> the
> array (I had 48 data points sampled on a triangle, then randomly perturbed,
> and chose N = M = 256 and a suitable W and T).  If this algorithm suits your
> needs, let me know and I'll upload it to my web site.