1
$\begingroup$

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:

enter image description here

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.

Thanks in advance!

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:

enter image description here

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:

enter image description here

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:

gpb.googlecode.com/files/DRAWER3.zip

Update:

if anyone wants the updated code, here it is:

http://pastebin.com/WqQEnpma

  • 0
    @GamErix: I don't see a square root. You would then get $\displaystyle\frac{(x,y)}{x^2+y^2}$2012-12-06

2 Answers 2

1

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}$enter image description here

  • 0
    it works, thank you, #myFault2012-12-06
0

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''$.

  • 0
    I've looked your answer at the afternoon, it had like 3 lines of text. It seems that escalated pretty quickly.2012-12-06