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/

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/

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

>plane?

minimum area triangle containing the points?

Dave Eberly

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

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

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

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

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

there will only be 23 points to consider) so any optimisations you could

suggest would help.

A small point but the line

should readQuote:> 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

1. How to determine if line intersects with triangle?

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

2. Looking for CrackerJack 3.0

3. Determine if a point is Inside/Outside/onEdge of Triangle

4. HELP ! ! ! !

5. Quick and dirty algorithm for determining pixel coverage of a triangle in 3d space

6. Troubles with RayPick (Direct3D Retained Mode)

7. determine whether triangles cover a cube?

9. How can I determine if two triangles are overlapping

10. Need to determine if point lies within triangle

11. How to determine z value of a triangle

12. Determining Triangle centers

13. Determining if a triangle is CCW or CW

5 post • Page:**1** of **1**