# Calculating 2D positions from a curve?

I am with quite a dylema here, as I need this for a game (so I am going to transform the given answers into programming code) to make a polygon around a curved line. from each line segment I have the X and Y positions, not I need to calculate all the X,Y positions around the curve like this:

The black dots are the known XY coordinates and the purple ones are the ones I want to calculate.

Please explain step-by-step how to calculate the XY of each purple point?

The order of the points has to create a polygon, so an calculation in this order would also be nice.

Edit: The red line IS the bisector of the angle between three black points (or two blue lines) and the distance between a purple dot and a black dot is 5.0.

Edit:

I created a program (source code here) thanks to the first answer but there is a little problem:

As you can see the polygon line cross themselves which shouldn't happen...

tomorrow I'm going to try to program answer #2 or wait till answer #1 will be updated.

Thanks to everyone for their time and efford!

Edit:

Created the program from answer #2 and the same problem persists :(

This is the result:

The red dots are the "purple points" on one side and the blue dots are the "purple points" on the other side of the curve, at least they supposed to be.

You can see on the image that the theory is missing something.

But what?

Update:

Here is more user-friendly source code:

pastebin.com/BJss8D5x

and the program itself:

Update:

if anyone wants the updated code, here it is:

http://pastebin.com/WqQEnpma

-
What criteria do the purple dots have to satisfy, otherwise they could be arbitrarily chosen? E.g. Eqidistant from the black points; the gradient must be the same between connected purple points as the same two black points, etc. –  Daryl Dec 5 '12 at 21:00
the distance between a purple dot and the parent (black) dot is constant, let's say 5.0 units. (the width of the highways in the game isn't even 10 but ok :P ) –  user51593 Dec 5 '12 at 21:03
Since the red and blue $\times$'s are not the same distance from the vertices of the path, I guess that the code is not unitizing when computing $u$ and $r$. Are you dividing by $\sqrt{x^2+y^2}$ in both $u$ and $r$? –  robjohn Dec 6 '12 at 13:05
I do have this in the function u: Return P / ((P.X * P.X) + (P.Y * P.Y)) ' (1) || line 47 here: pastebin.com/BJss8D5x –  user51593 Dec 6 '12 at 13:10
@GamErix: I don't see a square root. You would then get $\displaystyle\frac{(x,y)}{x^2+y^2}$ –  robjohn Dec 6 '12 at 14:30

First, define a couple of functions on points $(x,y)$ $$u((x,y))=\frac{(x,y)}{\sqrt{x^2+y^2}}\tag{1}$$ $u$ untizes $(x,y)$, and $$r((x,y))=u((y,-x))\tag{2}$$ $r$ unitizes and rotates $(x,y)$ by $90^\circ$.

Given three consecutive black points, $\{p_{k-1},p_k,p_{k+1}\}$, the two purple points on either side of $p_k$ would be $$p_k\pm5.0\,r(u(p_{k+1}-p_k)-u(p_{k-1}-p_k))\tag{3}$$ For the endpoints or for points where $u(p_{k+1}-p_k)=u(p_{k-1}-p_k)$, then the two purple points are either $$p_k\pm5.0\,r(p_{k+1}-p_k)\tag{4}$$ or $$p_k\pm5.0\,r(p_{k-1}-p_k)\tag{5}$$ Use $(4)$ when there is no $p_{k-1}$, or $(5)$ when there is no $p_{k+1}$, or either one when both $p_{k-1}$ and $p_{k+1}$ exist, but $u(p_{k+1}-p_k)=u(p_{k-1}-p_k)$.

Let me compute the purple points of the lower left corner of the path.

Digitizing the image gives these points \begin{align} p_{k-1}&=(355.669,371.368)\\ p_k&=(54.677,370.827)\\ p_{k+1}&=(205.173,296.12) \end{align} with $17.0$ as the distance from black to purple point.

Then \begin{align} u(p_{k-1}-p_k)&=(0.999998,0.001797)\\ u(p_{k+1}-p_k)&=(0.895711,-0.444636)\\ r(u(p_{k+1}-p_k)-u(p_{k-1}-p_k))&=(-0.973784,0.227476)\\ p_k+17.0\,r(\dots)&=(38.123,374.694)\\ p_k-17.0\,r(\dots)&=(71.231,366.96) \end{align} Here is where the purple points should go:

$\hspace{2cm}$

-
will try this tomorrow (~thursday 4p.m. GMT+1) –  user51593 Dec 6 '12 at 1:36
It should work. Note that $u(p_{k+1}-p_k)=u(p_{k-1}-p_k)$ only when the path folds back on itself. –  robjohn Dec 6 '12 at 1:54
I have recreated your theory and the same problem exists on the south-west part of the XY coordinate system. what could the reason be? here is the source: click and this is the program: zip downoad –  user51593 Dec 6 '12 at 11:48
@GamErix: I haven't been able to look through your code, but I have gone through the computations for one point of your problematic path. I get different purple points. –  robjohn Dec 6 '12 at 12:59
it works, thank you, #myFault –  user51593 Dec 6 '12 at 13:49

Assumption: the "red" line is the bisector of the angle between two black lines. The distance between the black and purple dots is $d$.

Suppose that the vector $u_k$ joins the $k^{th}$ and$(k+1)^{th}$ black dots. Then the vector $b_k$ defined as $b_k\cdot\left(u_k+u_{k+1}\right)=0$ bisects the angle between the two vectors. This can be normalised as $n_k=\dfrac{b_k}{\|b_k\|}$. So $n_k$ is a unit vector parallel to the red line at the $(k+1)^{th}$ point.

If the $(k+1)^{th}$ point is $B_{k+1}=(x_{k+1},y_{k+1})$, then the corresponding purple points would be $B_{k+1}+dn_k$ and $B_{k+1}-dn_k$.

At the endpoints, the red line is perpendicular to $u_0$ or $u_n$, which requires that you find $n$ vectors satisfying $n\cdot u_0=0$ for the first black point. Then similarly for the last black point.

Note that $u_k=B_{k+1}-B_k$.

Added example: The points $A(0,0),\,B(10,10),\,C(10,15),\,D(15,15)$.

Matching the points with the description I used above: $B_0=A=(0,0),\,B_1=B=(10,10),\,B_2=C=(10,15)\text{ and }B_3=D=(15,15)$. The distance of the purple points from the black points is $d=5$.

1. Determine each $u_k$. $$u_0=B_1-B_0=(10,10)-(0,0)=(10,10)\\ u_1=B_2-B_1=(10,15)-(10,10)=(0,5)\\ u_2=B_3-B_2=(15,15)-(10,15)=(5,0)$$

2. Determine each bisector $b_k$ and unit bisector $n_k$ $$b_0\cdot(u_0+u_1)=b_0\cdot(10,15)=0\Rightarrow b_0=[-15,10] \text{ (or [15,-10])} \\\quad n_0=\frac{b_0}{\|b_0\|}=\frac{(-15,10)}{\sqrt{325}}\approx(-0.83,0.55)\\ b_1\cdot(u_1+u_2)=b_1\cdot(5,5)=0\Rightarrow b_1=[-5,5] \\\qquad n_1=\frac{b_1}{\|b_1\|}=\frac{(-5,5)}{\sqrt{50}}\approx(-0.71,0.71)$$

3. Determine the purple points $P'$ and $P''$. Near $B_1$, the purple points are $P'=B_1+dn_0=(10,10)+5(-0.83,0.55)=(5.84,12.77)$ and $P''=B_1-dn_0=(10,10)-5(-0.83,0.55)=(14.16,7.23)$.

Similarly, near $B_2$, we get $P'=(10,15)+5(-0.71,0.71)=(6.46,18.54)$ and Similarly, near $B_2$, we get $P''=(10,15)-5(-0.71,0.71)=(13.54,11.46)$.

1. At the start point, find a unit vector perpendicular to $u_0$ i.e. $n\cdot u_0=0\Rightarrow n=(-0.71,0.71)$. Then $P'=(0,0)+5(-0.71,0.71)=(-3.54,3.54)$ and $P''=(3.54,-3.54)$.

2. Similarly, at the end point $n\cdot u_2=0\Rightarrow n=(0,1)$, so that $P'=(15,15)+5(0,1)=(15,20)$ and $P''=(10,15)$.

The list of all points is then those in each $P'$ and $P''$.

-
let's say I have a list of XY points of the curve (black points): A(0,0) -> B (1000,1000) -> C(1000,1500) -> D(1500,1500). how would I calculate the positions of the purple dots assuming one purple dot is 5 units away from the black dot and the red lines are bisectors? In the program I have the black dots are indexed ([0,Amount_of_black_dots], 0 is connected to 1, 1 to 2, etc) and the XY positions are known. –  user51593 Dec 5 '12 at 21:19
I will add in an example. –  Daryl Dec 5 '12 at 21:30
okay :) can't wait to see it hehe. –  user51593 Dec 5 '12 at 21:49
also could you explain part 2. a bit, especially the = 0 => part –  user51593 Dec 5 '12 at 22:09
thanks :) 8char –  user51593 Dec 5 '12 at 22:27