code.nosvamosdetapas.com

Wife, children, pet, luggage, GPS, water, air pressure, oil levels, ……. everything is packed and ready for your deserved holidays, and there you go for your trip to Paris. Of course, you wan’t to be there as soon as possible, but you will have to stop to eat, at least two times a day, and you have this bunch of places you’ve been told to be worth stopping because of the great food they serve. Oh yes, they’re good, but you won’t go 30 miles away from your route just to eat. If only you could know how far from your straight way those places are …

The problem

Draw a polygon that surrounds a (poly)line in such a way than the outer line that forms the polygon is a given distance from the former line.

First things first

I will use the same structure for the code and examples we’ve been using in older posts, so you’ll be quite confortable if you’ve been following us (if not, you should, they are worth reading).

A brief abstract for new readers. Every piece of code here is javascript, we use the GoogleMaps API and very basic stuff from prototype (you don’t need to know anything about prototype to understand this) we have a GMap2 object, an array of points (of interest), an extension on the GPolygon object to determine if a Gpoint is contained in a polygon, and a piece of code we run on body load to put everything together and to add the listeners we are using.

Drawing the line

This is not what the post is about, so very quickly, take a look at the code and you’ll understand it:

function addListeners(map){

//... other listeners...
GEvent.addListener(map, "click", onClick);
}

var points = $A(); //Points array to draw the polyline
var lineOverlay =null;   //The polyline

function onClick(overlay,point) {

 points.push(point);
 if(lineOverlay!=null)
 	map.removeOverlay(lineOverlay);
 if(points.length>1){
 	lineOverlay = new GPolyline(points,"#0000ff",2);
 	map.addOverlay(lineOverlay);
 }
}

Here comes the math

To draw a GPolygon I’m first gathering all the points in an array and then passing the array to the GPolygon constructor.

For each point of the former polyline, two points for the polygon will arise. Imagine that our line is quite vertical. Then some points will be situated on its right and some on its left. But this pair of points for each point from the polyline are not contiguous in the polygon, but simetrically situated on the array. Let’s say I have a line made up of four points, A, B, C and D, in that order. I will have two points from every of those, let name them A₁, A₂, B₁, B₂, C₁, C₂, D₁ and D₂. If I start drawing the polygon from the point A, this will be the layout of the polygon points in the array: [A₁, B₁, C₁, D₁, D₂, C₂, B₂,A₂].

Ok, now, how to figure out the polygon points? A little math will do the work. Let’s take the first two points, A, and B, to go for points A₁ and A₂.

I want to figure out the position of two points at each side of the first point situated over the rect that goes through this point (A) and which incline is perpendicular to the segment that joins the point with the next point in the polyline (B).

I know points A and B coordinates, (A_x, A_y) and (B_x, B_y), therefore I can find the incline of the rect that goes through them both with the formula:

m₁= A_y - B_y / A_x - B_x

and the incline of the perpendicular rect:

m₂= -1 / m₁

Coordinates of two points separated a given distance (d) over the rect that goes through point A with this last incline is a matter of trigonometry:

α = atan(m₂)

A_1x = A_x - d*cos(α)            A_1y = A_y - d*sin(α)

A_2x = d*cos(α) + A_x            A_2Y = d*sin(α) + A_y

As this A point is the first in the iteration, we will add A1 and A2 to the polygon points arrat straight away. Remember, A₁ as the first element and A₂ as the last one.

And the rects that go through this points paralels to the AB segment are:

r₁: y = m₁ (x-A_1x) + A_1y

r₂: y = m₁ (x-A_2x) + A_2y

Time to iterate. Once you are here, repeat the operations for segment BC, that is, calculate BC incline, its perpendicular, look for two points over that perpendicular, B₁ and B₂, situated a distance “d” away from B, and finally calculate the ecuations of the paralel rects to BC that go through those two points.

r₃: y = m₃ (x-B’_1x) + B’_1y

r₄: y = m₃ (x-B’_2x) + B’_2y

Be careful here! Those B’₁ and B’₂ points are not to be added to the gpolygon. The points we are looking for are what we get intersecting those rects with the ones from the previous iteration. This is about solving a system with two ecuations and two variables, isolating one of the variables and them using its value on one ecuation to calculate the other.

B_1x = (-m₃*B’_1x+B’_1y+m₁*A_1x-A_1y)/(m₁-m₃)         B_1y=m₃*(B_1x-B’_1x)+B’_1y

B_2x=(-m₃*B’_2x+B’_2y+m₁*A_2x-A_2y)/(m₁-m₃)          B_2y=m₃*(B_2x-B’_2x)+B’_2y

There you go, two more points to add. Remember that each of them go to one end on the array (for the B point, B1 would go to array[1] and B2 to array[array.length-2] (Do I need to say that javascript arrays are zero based? No I don’t…).

The hard work is already done, as this iterations will take you to the last point. For this last ones (D in our four points line example), you only need two points over the perpendicular, just as you did for the fisrt two. You already have the calculations for the incline of the perpendicular from last iteration, so you can straightly get the last pair of points (D1 and D2), which you will add to the array in the middle positions (this two will be contiguous).

If you get here and you understood everything, you won’t have any problem with the code, which is commented and is quite similar to what you’ve already read.

There’s always something tricky

When I first coded this, I spent several hours trying to figure out why I wasn’t working properly. The problem was that, sometimes, the lines of the polygon crossed their way of the line, and the “sometimes” happened to be when in a group of three points, they point in the middle was above of below the other two. Quite weird. Making some changes, What I obtained was that when in a group of three, if the point in the middle was the most left or right one, the lines crossed.

So, what did I do? Easy and miserable. I blame google for it and added a boolean “swapped” variable that I use to return the points where they should be before adding them to the array. You will clearly find and understand that also in the code.

What did I left behind

As the code is intended to be educational, there are some checks I didn’t do to keep it clear. I.e. keep in mind that horizontal segments will result in a division by zero when calculating the incline. Once you get that, mind it again to calculate the perpendicular. Same precautions must be taken when solving the ecuations system, as two consecutive segments with the same incline will result also in a division by zero error.

This aproach solves quite well the problem, but there are circunstances where you will find not the expected behaviours. That will happen, i.e. when you have segments in your line that are shorter than the distance you want the polygon to be drawn away.

Test it, download it, and leave me your comments.

Bookmark It