//point_list->pos is a 2d vector with the vertex's coordinates.
//vec is a 2d vector
//* is the dot product
//ms is a 2d vector with the coordinates of the point in the polygon
float affect[point_list.size()];
float total_dot=0.0f;
for (int i=0;i<point_list.size();i++)
{
vec tpos(point_list->pos-ms);
affect=1.0f/(tpos*tpos);
total_dot+=affect;
}
for (int i=0;i<point_list.size();i++)
{
affect/=total_dot;
}
//if i were to recalculate where the point would be, it would look something like:
vec pos(0.0f,0.0f);
for (int i=0;i<point_list.size();i++)
{
pos+=point_list->pos*affect;
}
effect of polygon on a point
Author
I'm trying to find out what effect each vertex in a polygon would have on a point in a polygon. To better explain this, pretend there's a point inside a convex polygon. The position of the point relates to all of the vertices that make up the polygon. If i calculate the effect each vertex has on the point, i can recalculate where that point on the polygon will be if the polygon moves or rotates by summing up all of the vertex coordinates * their effect.
For instance, if in a polygon with N vertices, if the point was on the center of mass of those vertices, then the effect each vertex would have on the point would be 1/N. If the point was directly on top of a vertex, that vertex would have an effect 1 on the point, and all the rest would have an effect of 0.
I realize that i could calculate the angle between the point and 2 vertices of the polygon, and then use those 2 vertices to reconstruct where the point would be, but i need the effect that each vertex has to the point for other calculations in my program.
My first try, since i'm dealing with convex polygons, was to judge the effect of each vertex by the area between it, the point, and a neighboring vertex, but i couldn't find any way the area relates to it. My second try involved using the angles between the center of mass and each vertex, and the angle from the point to the center of mass, that didn't work either. My third try (as seen in the code below), was to center the polygon based on the point, and find the effect of each vertex based on the dot product of the shifted vertex. It comes close to what i want, but the farther away the point is from the center of mass or a vertex, the more innacurate the effect's get.
You really haven't defined a relationship between the position of the point and the position/weights of the vertices (i.e. center of mass). If you think about it, the more you run your algorithm, the more the point will keep moving and moving based on its changing inverse-squared distance will all the vertices. What you really want is something that tells you what the position of the point is as a function of the vertices, rather than how you should change the point based on its current position the position of the vertices, otherwise the position of the point isn't stable (it could eventually reach a stable position with enough iterations, but that's uncertain).
Author
Quote:
If you think about it, the more you run your algorithm, the more the point will keep moving and moving based on its changing inverse-squared distance will all the vertices.
I know that my algorithm is flawed, i was just showing my closest attempt to solving the problem.
Quote:
What you really want is something that tells you what the position of the point is as a function of the vertices
That sounds like what i'm looking for. Though, how do i go about finding the function of the vertices in relation to the point? The only mathemetical functions, such as y=f(x), i'm aware of are the linear and polynomial functions taught in my trig class.
Quote:Original post by flounder
That sounds like what i'm looking for. Though, how do i go about finding the function of the vertices in relation to the point? The only mathematical functions, such as y=f(x), i'm aware of are the linear and polynomial functions taught in my trig class.
In general, you can think of a function as something that takes some input and gives you an output. In your example, x is the input, f(x) is the function, and y is the output. So if the vertices are the input, the function does some stuff and somehow generates the point. Like with the center of mass formula, it takes all the vertices as input, weights them, adds them together, divides by the number of vertices, and gives you a result. However the function isn't something that you find, it's something that you choose beforehand, depending on how you want the point to behave as vertices move around. You could just as well divide your polygon into triangles, and use barycentric coordinates for each triangle. If you can put into words how you want the point to behave, we could probably point you in the direction of a good algorithm.
Author
In terms of an equation, the effect would look like: vertex[0]*a[0]+vertex[1]*a[1]+...vertex[n]*a[n]=point . Where vertex[n] and point are vectors, and a[n] is a scalar. The scalars would be calculated when the point is placed on the polygon. vertex[0]*a[0]+...vertex[n]*a[n]=new_position would give the position of the point if the polygon moved. If all the scalars were to be added up, they would equal 1, a[0]+...a[n]=1.
This means that all the vertices have some effect on how the position of the point will be recalculated, unless if the point lies on the border of the polygon, in that case only 1 or 2 vertice's have any effect. pic:
This means that all the vertices have some effect on how the position of the point will be recalculated, unless if the point lies on the border of the polygon, in that case only 1 or 2 vertice's have any effect. pic:
ok so if we rearange the equation you just gave we can get a matrix equation that you can solve for your a
now if your vertexes all lie on a plane then we have rank(vertex) = 2 and so you will have n - 2 degrees of freedom
now you have to use your constraints
that needs more explaining but i have to go so i'll leave it for someone else...
vertex[0] * a[0] + vertex[1] * a[1] + ... + vertex[n] * a[n] = point=> ( vertex[0] ) ( a[0] ) ( vertex[1] ) ( a[1] ) ( vertex[2] ) ( a[2] ) = point ( .... ) ( .... ) ( vertex[n] ) ( a[n] )=> vertex * a = pointnow if your vertexes all lie on a plane then we have rank(vertex) = 2 and so you will have n - 2 degrees of freedom
now you have to use your constraints
a[0] >= 0, a[1] > = 0, ..., a[n] >=0 and a[0] + a[1] + a[2] + ... + a[n] = 1that needs more explaining but i have to go so i'll leave it for someone else...
Actually, he'll have N - 3 degrees of freedom once you factor in the unit sum constraint. This makes sense, since if you have a pentagon and you remove two degrees of freedom you're left with a triangle, in which case there exists no more than a single solution using barycentric coordinates. In equation form:
The quick and easy way to find the weights is to find three vertices that form a triangle containing the point. Then find the barycentric coordinates of that point, which will be the weights of those three vertices. The other N - 3 vertices that aren't part of the triangle have weights of 0.
The quick and easy way to find the weights is to find three vertices that form a triangle containing the point. Then find the barycentric coordinates of that point, which will be the weights of those three vertices. The other N - 3 vertices that aren't part of the triangle have weights of 0.
Author
Quote:Original post by Zipster
The quick and easy way to find the weights is to find three vertices that form a triangle containing the point. Then find the barycentric coordinates of that point, which will be the weights of those three vertices. The other N - 3 vertices that aren't part of the triangle have weights of 0.
If i'm reading that correctly, even if the point is inside the polygon, only 3 vertices will have any weight. If the point is inside the polygon, i need it to fill the property that all vertice's have a weight (like the first polygon in the picture i posted).
After finding out what the barycenter is, the barycentric coordinates could also be described as what i'm trying to find, except for all the vertices rather than the 3 that could enclose it.
As Zipster said, you have a lot of freedom in assigning the weights. Why do you need all weights to be positive? You could do something like calculate the barycenter of the whole polygon, and then express your point in terms of the barycenter and the two "adjacent" vertices (those that form the line segment which intersects the ray from the barycenter containing the given point), but then again, it's simpler to use weights that are only non-zero for at most 3 vertices.
I mentioned that this was the easy way of determining a set of weights. Of course there are much more involved methods that require a fairly comprehensive knowledge of linear algebra and solving systems of equations. However in the end you have N - 3 degrees of freedom, meaning you're going to have to choose those values out of thin air. There is no rhyme or reason to how you choose the values, and worst of all is that it's possible to choose bad values that will break your constraints. I don't see why 0 isn't a good weight, you've depicted a case in your diagram where the point is on a border and three weights are 0.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
