Thread: Problem calculating points to form appropriate shape in a computer implementation

1. Problem calculating points to form appropriate shape (for a computer implementation)

I am building a mapping software, and i have a problem in calculating specific points for building the roads. The way i build them is that i have the start and end point (all information is in x and y coordinates), the width of the road, and i can calculate the slope.

To draw the middle (dashed lines on the road) line is simple, it is from starting to ending point, but i am having problem finding the starting and ending points of the road boundaries (which has distance of width/2 above and below the middle line). Now if the road is completely horizontal, i simply can add width/2 in the y coordinate of the above boundary's starting and ending point, and subtract width/2 from the y coordinate of the starting and ending points to calculate the starting and ending points of the lower boundary. But i am stuck at how to find these points when the road is not horizontal or vertical, but tilted or diagonal (when ill need to add something to both x and y coordinates).

I can have the slope of the road, and slope of the perpendicular (on which the start points of both upper and lower boundary will lie), and i have the width, but how to continue from here?

I have attached an image to make the point clear.

Thanks in advance for the replies!

2. Re: Problem calculating points to form appropriate shape (for a computer implementati

If "m" is the slope of the middle line (I am assuming you mean the slope in the "Cartesian geometry" sense and not how the road slopes going up a hill!) then the slope of the line perpendicular to it is -1/m. If the coordinates of the point you are given are $\displaystyle (x_0, y_0)$, then the line perpendicular to the "road" is given by $\displaystyle y= -(1/m)(x- x_0)+ y_0$. The two desired points lie at width/2 from $\displaystyle (x_0,y_0)$ and so lie on a circle with center at $\displaystyle (x_0, y_0)$ and radius width/2. Such a circle has equation $\displaystyle (x- x_0)^2+ (y- y_0)^2= \frac{width^2}{4}$.

Replace y in that equation with $\displaystyle -(1/m)(x- x_0)+ y_0$ from the first equation and you have $\displaystyle (x- x_0)^2+ (1/m^2)(x- x_0)^2= (1+ 1/m^2)(x- x_0)^2= \frac{m^2+ 1}{m^2}(x- x_0)^2= \frac{width^2}{4}$

$\displaystyle (x- x_0)^2= \frac{m^2 (width)}{4(m^2+ 1)}$
$\displaystyle x- x_0= \pm\frac{m\sqrt{width}}{2\sqrt{m^2+ 1}}$
$\displaystyle x= x_0\pm\frac{m\sqrt{width}}{2\sqrt{m^2+ 1}}$
Take + for one point and - for the other. Of course, y for each point is given by $\displaystyle y= -(1/m)(x- x_0)+ y_0$.

3. Re: Problem calculating points to form appropriate shape (for a computer implementati

Thanks for reply. And roads are not uphill or downhill, it is the bird's eye view from the top, so the slope i was referring to is indeed the slope in Cartesian coordinate system.

There is one thing i forgot to mention: The design environment i am using has (0,0) at the top left corner of the drawing area, and x coordinate increase towards the right as usual but y coordinate increase downwards.

I respect the effort gone into the last post to answer my question, and I know I should have mentioned it earlier, but here most of the time we tell the computer what to do, and never go into calculations like this because they are done by algorithms written by someone else, but my application requires efficiency and speed, so for the first time, i have to give direct coordinates instead of high level instructions that are slow, and because of the fact that i never had to do it before, it completely forgot about the difference between the Cartesian coordinate system and the system that the computer implements to calculate location.

How much this change things?

4. Re: Problem calculating points to form appropriate shape (for a computer implementati

Ok, i have implemented the solution as it is, and despite the fact that the Y coordinate work in reverse, it is working perfectly.

Only one change that I have used is in the first equation (to calculate x), i have used width instead of square root of width, and it works perfectly, with the only difference being that to draw the upper boundary (considering the y coordinate increase downward) i had to add (instead of subtracting) to the original y, and to draw the lower boundary, i had to subtract from original y.

At a later stage, i'll have to calculate every point on these lines, in order to do hit testing to make sure that nothing is placed on top of the road, all of which will be done by calculations, so i need to know what is happening, as there'll be a lot of math later on. I request HallsofIvy to explain why the solution worked despite the fact that y coordinate works in reverse (and so the slope of the line that is tilted upward is negative)?