Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

find point where barycentric weights have a specific value

Tags:

geometry

I have triangle: a, b, c. Each vertex has a value: va, vb, vc. In my software the user drags point p around inside and outside of this triangle. I use barycentric coordinates to determine the value vp at p based on va, vb, and vc. So far, so good.

Now I want to limit p so that vp is within range min and max. If a user chooses p where vp is < min or > max, how can I find the point closest to p where vp is equal to min or max, respectively?

Edit: Here is an example where I test each point. Light gray is within min/max. How can I find the equations of the lines that make up the min/max boundary?

example

a = 200, 180
b = 300, 220
c = 300, 300
va = 1
vb = 1.4
vc = 3.2
min = 0.5
max = 3.5

Edit: FWIW, so far first I get the barycentric coordinates v,w for p using the triangle vertices a, b, c (standard stuff I think, but looks like this). Then to get vp:

u = 1 - w - v
vp = va * u + vb * w + vc * v

That is all fine. My trouble is that I need the line equations for min/max so I can choose a new position for p when vp is out of range. The new position for p is the point closest to p on the min or max line.

Note that p is an XY coordinate and vp is a value for that coordinate determined by the triangle and the values at each vertex. min and max are also values. The two line equations I need will give me XY coordinates for which the values determined by the triangle are min or max.

It doesn't matter if barycentric coordinates are used in the solution.

like image 924
NateS Avatar asked Nov 28 '13 17:11

NateS


People also ask

How do you find the barycentric coordinates of a point?

To compute the position of this point using barycentric coordinates we use the following equation (1): P=uA+vB+wC. where A B and C are the vertices of a triangle and u, v, and w (the barycentric coordinates), three real numbers (scalars) such that u+v+w=1 (barycentric coordinates are normalized).

Are barycentric coordinates unique?

Barycentric coordinates were introduced by August Ferdinand Möbius in 1827. They are special homogenous coordinates.

How do you find barycentric coordinates in 3D?

The barycentric coordinates can be computed for a point with respect to a simplex (Section 3.8) of any dimension. For instance, given a tetrahedron specified by the vertices A, B, C, and D, the barycentric coordinates (u, v, w, x) specify a point P in 3D space, P = uA + vB + wC + xD with u + v + w + x = 1.


1 Answers

The trick is to use the ratio of value to cartesian distance to extend each triangle edge until it hits min or max. Easier to see with a pic:

enter image description here

The cyan lines show how the triangle edges are extended, the green Xs are points on the min or max lines. With just 2 of these points we know the slope if the line. The yellow lines show connecting the Xs aligns with the light gray.

The math works like this, first get the value distance between vb and vc: valueDistBtoC = vc - vb

Then get the cartesian distance from b to c: cartesianDistBtoC = b.distance(c)

Then get the value distance from b to max: valueDistBtoMax = max - vb

Now we can cross multiply to get the cartesian distance from b to max: cartesianDistBtoMax = (valueDistBtoMax * cartesianDistBtoC) / valueDistBtoC

Do the same for min and also for a,b and c,a. The 6 points are enough to restrict the position of p.

like image 108
NateS Avatar answered Oct 31 '22 16:10

NateS