x-y coordinates of points on Polygon

[Sallygreen]

Hey guys

I would be highly grateful if anyone could give me ahint how to calculate the x-y coordinates of any point on Polygon, as I am applying a numerical method which goes on the boundaries so at any lenght I need to find the corresponding coordinates in 2-dimension

[NickThissen]

I think we're going to need more information here... The (x,y) coordinates of the points of a polygon define that polygon so I have no idea what you mean by calculating these points... You need more information, you cannot simply take a random polygon (without knowing how it looks) and calculate the positions of the corners.

[Sallygreen]

hey daer
yes you right I have the 5 vertices of the polygon, so I know their x-y coordinates but the matter I am implementing a numerical method on the boundary which reduce the problem from 2 -dim to one dim i.e. insted of having (x,y) I have element s on the boundary, and at some point I need to determine the x-y coordinates for the points between the vertices, as I need them to calculte another stuff in my code.......

[NickThissen]

By 'element s on the boundary' do you mean that you have a parametrization
x(s) = ...
y(s) = ...

If so, I assume this is a piece-wise defined parametrization, right? Can you show it?

Or if you have no clue what I'm talking about, can you clarify because I still don't understand exactly what you have and what you want.

[Sallygreen]

yeah I am implementing the Boundary element method on the boundary of a polygon geometry so at given length s I need to find the corresponding coordinates x, y as I need to find the length of any segment join a chosen point on the boundary with other selected point..........hope that clarify the things..

[NickThissen]

I'm not familiar with the 'boundary element method', nor do I understand what s is. Is it the length of a line from the origin to a point on the polygon? Is it the length of one side of a polygon?

[Sallygreen]

I'm not familiar with the 'boundary element method', nor do I understand what s is. Is it the length of a line from the origin to a point on the polygon? Is it the length of one side of a polygon?

I guess you do not need to worry about any idea of BEM because it turns out to geometry matter, yes s it is the length of a line from the origin to a point on the polygon ...and at any length we should have the corresponding x-y but how can we find them

[NickThissen]

If s is simply the length from origin to a point (x,y) on the polygon then it is impossible to find x and y unless you have some more information.

Imagine s to be the length of a line from the origin to any point (x,y). Since s is a known quantity and thus constant, any point (x,y) on the circle around the origin with radius s could be the point you are looking for.

If you know something more about the shape of the polygon however, the point(s) (x,y) would be the points of intersection between the circle and the polygon.


I ask again:
Do you have a parametrization for x and y as functions of s? That is, do you have two formulas like the following:
x(s) = ... (some function of s)
y(s) = ... (some function of s)

If so, all you need to do is plug s into these equations and you have (x,y)!

[Sallygreen]

appreciate ur time Nick, sorry if I had confused you s is simply the length from the first vertix of the polygon to a point (x,y), all the information I have the equation of the line where the point lie, and I do not have any parametrization, to simplify the problem imagine we have a square drown in 2 dim and we have the vertices poits and we need to find the (x,y)coordinates of each point

[NickThissen]

So you have the equation(s) for the polygon (which would consist of a number of straight lines)?

Then that is all you need! You don't even need s.

For the square example:
Suppose you have a square with vertices (0,0), (1,0), (1,1) and (0,1). Then you want to find the (x,y) coordinates of any point on that square?
Well, it depends on where you are on the square. If you are at the line between (0,0) and (1,0) then the (x,y) coordinates are given by the equation of that line:
y = 0 (for x = 0 to 1)

If you are at the line between (1,0) and (1,1) it would be:
x = 1 (for y = 0 to 1)


As you may see, the points (x,y) are all simply lines. y = 1 is a line, and x = 1 is also a line. The only further thing is that the lines are not 'defined' beyond your polygon. Eg in the case of the square, in the line y = 0, x can only go between 0 and 1 (else you would be outside the square!). For a polygon the lines would be a little more complicated (y = ax + b for example) and range of x would be determined by the vertices.

[jemidiah]

s is simply the length from the first vertix of the polygon to a point (x,y)

This could either mean, given vertex 1 as (x1, y1), s = dist(v1, (x, y)) = Sqrt((x1^2-x^2)+(y1^2-y^2)) for some point (x, y)--that is you take the distance between v1 and (x, y) "as the crow flies" to get s. Or, it could mean you take the distance traveled along the outline of the polygon for some point (x, y) on the polygon--that is, distance "walking along the polygon" starting at v1 and stopping at (x,y) to get s. In that case, Nick's guesses that s is parameterizing the perimeter were right.


You seem to be saying you have two different types of information. First you said

I have the 5 vertices of the polygon, so I know their x-y coordinates

But then

all the information I have the equation of the line where the point lie

I'm not really sure what the second sentence means; it might be as Nick interpreted, meaning you have equations for the lines of the polygon (somehow). Finding the points of the polygon could be horrific in the general case, but I doubt this problem is meant to be that horrible.

So, I'm going to assume you have: (1) the vertices of the polygon as (xi, yi) points, where vi = the ith vertex = (xi, yi). (2) equations for each edge, paired with the vertices at the end points of that edge.

If this is right, could you tell us exactly what you need to find?



My best guess from

s it is the length of a line from the origin to a point on the polygon ...and at any length we should have the corresponding x-y but how can we find them

is that you want to find the points of intersection with the circle of radius s with the polygon. To do so, simply intersect each of your equations for the segments of the polygon with the equation for a circle of radius s, x^2+y^2=s^2. Note that you'll have to check if the intersection is actually on the edge segment between the two vertices. I'd be happy to give more details, but first want to know if this is really what you want.

[Sallygreen]

what I am saying is the same type of information cos{ I have the 5 vertices of the polygon, so I know their x-y coordinates }imply to {I have equations for the lines of the polygon]
Your guess is right s it is the length of a line from the first vertex to a point on the polygon ...and at any length we should have the corresponding x-y but how can we find them********I want to write a code which is going through the boundary of a polygon and we calculate the length from the first vertex..so at any given s how can I tell my program how to find its corresponding x, y.................... I couldn't get your idea about the circle but it seems to good idea.........hope things is clear

[jemidiah]

Alrighty, I'm pretty sure you want the distance s to be the distance you have to walk along the perimeter of the polygon to get to your next point, so you're parameterizing the polygon with a "length" parameter.

I'm going to assume you have the vertices of the polygon in clockwise order labeled v_1, v_2, v_3, ..., v_n for n different vertices (n vertices yields an n-gon). Let's call the line segments between pairs of vertices edges e_1 through e_n where

e_1=v_1->v_2,
e_2=v_2->v_3,
...,
e_n-1=v_n-1->v_n,
[e_n=v_n->v_n+1=v_n->v_1] // wrap around at the end

Call the length of these segments |ei| = distance(left to right endpoint) = |v_i+1 - v_i| = Sqrt((x_i - x_i+1)^2+(y_i - y_i+1)^2). When your distance s is in the range 0 to |e1|, you should be partway along e1; when s is in the range |e1| to |e1|+|e2|, you should be partway along e2, etc. In general, when s is in the range \Sum{j=1 to m of |ej|} to \Sum{j=1 to m+1 of |ej|}, you're on edge e_m+1.

It's pretty simple to write a function to check which edge you should be along. You'll also want to know how far along you are in that edge. For instance, if you're at s = |e1|/2, you're halfway along edge e1. If you're at s = |e1| + |e2| + |e3|/4, you're a quarter of the way along edge e3--that is, you've traveled from v1 through v2 and v3, and now you're a quarter of the distance from v3 to v4 away from v3.

Find out how far you are through the current edge e_m+1 by taking c = s - \Sum{j=1 to m of |ej|}; this will yield |e3|/4 in the above example, since you're on edge e3 (so you sum up till j=2, subtracting off |e1| and |e2|). Find the fraction of how far you are along that edge by dividing by |e_m+1|, so L = c/|e_m+1|. Again using the example, L = 1/4.

Now, do a linear interpolation along the edge e_m+1. This is most easily done parametrically. You go a fraction L of the distance between the edge vertices. I'm calling the edge vertices a and b, where e_m+1=a->b; you can find their index using the relations above. Then your final answer is x = x_a + (x_b-x_a)*L, y = y_a + (y_b-y_a)*L.


This, taken altogether, will give you a function where you input s and it outputs the (x, y) coordinates of the point you would get to if you walked s units along the perimeter of polygon, starting at v1, going clockwise.

A note on vertex indexing: you have to be sure you remember to let vertex indecies after the last index wrap around, so that v_n+1 is replaced by v_1. It's simple to do that in your code.

If I haven't answered the question you wanted please say so. Edit: also my idea about a circle used my other guess as to what you want to define s as. So, if the "walking along the edge" idea is good, ignore the circle.

[Sallygreen]

Brilliant Jemidiah, much thank for your time I will go with your fantastic hint, I will try to configure the code and I will be back if I get stuck