PDA

View Full Version : Moving a point inside a triangle


Cableguy
08-07-2003, 04:34 PM
Hello peeps,

I'm a trying to program something but I'm stuck on this: given a triangle defined by three points, say A B and C, and a 'free' point inside the triangle, D, what is the formula to move that point D when I move A B or C?

What I need is the correct way to calculate the proportions between distances A-D, B-D, C-D and their new values after the points move.

At the moment my formula to move D is qA*aA+qB*bB+qC*cC where qA etc are quotients 0-1, stating the proportion of each distance, and aA etc are the distances between the old and new triangle corner point positions.

I calculate the quotients for each D-to-corner distance with 1-(AD/(AD+BD+CD)) to get the qA, and likewise for qB and qC.

This doesn't work right - can someone point me in the right direction? Thanks in advance.

Space Penguin
08-07-2003, 05:04 PM
You didn't explain what you were trying achieve really. Specifically, how does the point D relate to the triangle? Where should it be located, once the triangle is transformed?

I assume that you mean UV coordinates. If that's the case, I can help.

Define two vectors thusly:
U = C - A
V = B - A

Then find real numbers t, s such that:
D = A + t*U + s*V

Now remember t and s, and transofrm the triangle (i.e. move points A, B and C).
Calculate U and V again, as defined above.

D should be easy to set. Just use the formula above with the new values of U and V, and old values of t and s.

In a way, U and V change when the triangle points move, and t and s change when D moves.

Cableguy
08-07-2003, 05:34 PM
Thanks for that!

To answer your question re D location after triangle points move, D should move accordingly, in proportion to its original distances from the triangle points. (You can assume D is on the triangle plane.) So if C moves a great distance but A and B don't move, and D is close to A, then D will not move much.

It looks like your solution assumes as much. How do I calculate t and s values? I must be stupid, I can't work it out! :scream:

MDuffy
08-07-2003, 05:47 PM
You can do a search online or through your books for "barycentric coordinates". It will give you a (u,v) coordinate for center point D in your triangle ABC. Then you transform ABC as you like, and you can use (u,v) to calculate D again. Essentially u and v are weights applied to two of your corner verts, and the third weight for the third corner is (1 - u - v).

D = (1 - u - v)A + uB + vC

where u >= 0, v >= 0, and and u + v <= 1

Here's a webpage that describes how to solve for them:

http://mathworld.wolfram.com/BarycentricCoordinates.html


Cheers,
Michael Duffy
mduffy@ionet.net

Cableguy
08-07-2003, 06:16 PM
Originally posted by MDuffy

D = (1 - u - v)A + uB + vC

where u >= 0, v >= 0, and and u + v <= 1


MDuffy, is your formula compatible with that offered by Space Penguin:

D=A+t*U+s*V ?

In other words, are your U and V values the same as his? If they are, then I think I can solve it:

D = (1-(C-A)-(B-A))*A+(C-A)*B+(B-A)*C

[EDIT]That's obviously wrong, the two formulas define u & v differently...still looking for a solution.[EDIT]

The Wolfram page you linked to is interesting but I can't see a way to a solution there.....I'm too slow!

UrbanFuturistic
08-08-2003, 03:12 AM
OK, here's a diagram to accompany Space Penguin's post.

http://www.zen27875.zen.co.uk/UVVectors.jpg

If you don't understand how it relates then you need to learn a tad more about vector graphics.

regards, Paul

Cableguy
08-08-2003, 06:48 AM
Thanks odubtaig, the graphic illustrates the concept nicely. I don't think I had a problem understanding Space Penguin's explanation, just couldn't work out how to calculate s and t given the known values - I'm math challenged!

In the meantime I have found a solution using barycentric coordinates MDuffy talked about - where u v and w values are defined as weights equaling the ratio of area covered by each subtriangle defined by the point inside the main triangle. Because the weights total 1, they can be thought of as a coordinate system, a source of confusion for me at first.

So the formula is quite simple because a triangle area can be got with a cross product of two of its vectors.

My code in C4D Coffee is then:

xyz(a,b,c,d) // a b c are pts of tri, d the point inside it
{
var cp = vlen(vcross(a-b,c-b));
var u = vlen(vcross(b-d,c-d))/cp;
var v = vlen(vcross(a-d,c-d))/cp;
var w = vlen(vcross(a-d,b-d))/cp;

println("u: ",u,", v: ",v,", w: ",w);
println("total: ",tostring(u+v+w));
println("original d: ",d);

d = u*a + v*b + w*c;

println("new d: ",d);
}

This function is just working proof, nothing is actually moved, but if you moved a b or c, d would move accordingly.

Hope this helps someone else!

Space Penguin
08-08-2003, 09:57 PM
I guess you've got a neat solution already.

Still, just to complete this thing... If you want to find s and t, here's what you do:

We have: D = A + t*U + s*V

And suppose:
D = (Dx, Dy)
A = (Ax, Ay)
U = (Ux, Uy)
V = (Vx, Vy)

We gather:
1. Dx = Ax + t*Ux + s*Vx
2. Dy = Ay + t*Uy + s*Vy

Now you have two independent equations and two variables. Easy to solve.

A step further:
t = (Dx - Ax - s*Vx) / Ux

Use this in the second equation...
s = (Dy - Ay - (Dx - Ax - s*Vx)*Vy/Ux) / Uy

Now, isolate s in the left side:
s = (Dy - Ay - Dx*Vy/Ux + Ax*Vy/Ux) / (Uy - Vx*Vy/Ux)

And you're done. (Use this s value in the equation where t was isolated to find t).

It's a lot more elegant if you use vector algebra.
It's not that messy for the computer though, since it doesn't need to know all the math. Just the most-final equations.

Cableguy
08-09-2003, 02:21 PM
That's great, Space Penguin, thank you. It's all much clearer once you've shown that x and y values can be treated separately. I've already got a solution, but your method will be useful in other problems.

You mention that it would be more elegant with vector algebra - is it possible to get s and t values that way? If it's not too much hassle, how would you do it? I guess you're talking about cross product or dot product and such like, functions that are available in the C4D Coffee language I'm using, so I wouldn't mind seeing how to do it that way.

Anyhow, you've been very helpful, thank you very much.

CGTalk Moderation
01-15-2006, 08:00 PM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.