## Determine a best fit triangle

### Determine a best fit triangle

Hi,

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

Thanks

Shiddhartha Nandy
Applied Imaging International
http://www.aicorp.com/

### Determine a best fit triangle

>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?

Dave Eberly

### Determine a best fit triangle

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

Regards
Shiddhartha Nandy

### Determine a best fit triangle

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

Dave Eberly

### Determine a best fit triangle

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

Yep that would be great. Yes speed is an issue (although on average
there will only be 23 points to consider) so any optimisations you could
suggest would help.

A small point but the line

Quote:>  Set R = i*RMAX/N and A = j*2*PI/M.  Count(i,j) is the number

Set R = i*RMAX/(N-1) and A = j*2*PI/(M-1).  Count(i,j) is the number

thanks
Shiddhartha Nandy
Applied Imaging International

I have a 3D model. For each triangle and quad that makes up the model, I
want to compute its normal and emanate the normal outward to see if it
intersects with any other element. I can compute the normal fine, but I am
just not sure how to proceed. Can someone show me (or provide link) how to
perform the intersection operation with a triangle and with a 4 sides
polygon?

thanks,

brian