flounder 100 Report post Posted October 7, 2006 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. //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[i]->pos-ms); affect[i]=1.0f/(tpos*tpos); total_dot+=affect[i]; } for (int i=0;i<point_list.size();i++) { affect[i]/=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[i]->pos*affect[i]; } 0 Share this post Link to post Share on other sites
Zipster 2393 Report post Posted October 7, 2006 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). 0 Share this post Link to post Share on other sites
flounder 100 Report post Posted October 7, 2006 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 verticesThat 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. 0 Share this post Link to post Share on other sites
Zipster 2393 Report post Posted October 7, 2006 Quote:Original post by flounderThat 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. 0 Share this post Link to post Share on other sites
flounder 100 Report post Posted October 7, 2006 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: 0 Share this post Link to post Share on other sites
Julian90 736 Report post Posted October 7, 2006 ok so if we rearange the equation you just gave we can get a matrix equation that you can solve for your a 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 freedomnow 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... 0 Share this post Link to post Share on other sites
Zipster 2393 Report post Posted October 7, 2006 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. 0 Share this post Link to post Share on other sites
flounder 100 Report post Posted October 8, 2006 Quote:Original post by ZipsterThe 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. 0 Share this post Link to post Share on other sites
Darkstrike 206 Report post Posted October 8, 2006 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. 0 Share this post Link to post Share on other sites
Zipster 2393 Report post Posted October 8, 2006 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. 0 Share this post Link to post Share on other sites
flounder 100 Report post Posted October 8, 2006 After some searching, i turned up this pdf, which finds exactly what i was looking for.Quote:Original post by DarkstrikeAs Zipster said, you have a lot of freedom in assigning the weights. Why do you need all weights to be positive?Well first of all i need this for a physics application. I'm using constrained particle bodies instead of rigid bodies for the actual physics. Traditionaly constraints can only be applied between 2 points, i want to be able to anchor constraints between multiple points, or bodies.Thanks for helping me anyway, since it probably seemed illogical that i wanted more information about the weights than i needed. 0 Share this post Link to post Share on other sites
Zipster 2393 Report post Posted October 8, 2006 Hey, that's not a bad method! I'm keeping that one around for reference [smile]As you can see, there a bunch of different methods for finding a set of weights depending on what you need them to be, since there is no unique set for any point. 0 Share this post Link to post Share on other sites