Calculate the polygon surrounding a multipoint line

Question

I am trying to compute a polygon that surrounds a line connecting multiple points (e.g. GPX track). The figure below shows an example with a track as a red line, and the desired polygon - blue.

As a simplification, red dots are denoted by x and y - not in latitude / longitude.

How to calculate such an environment (blue polygon) if I have only a list of three points indicating the path?

Partial solutions (for example, for only two points) or hints about math libraries (in Java) that provide algorithms for such a calculation will also take me one step further.

Further assumptions:

• The track is free.

Update: Using the approach presented by Rogach and Ksan, I ran into some problems if the angle between the lines is less than 90 degrees or more than 270 degrees: As you can see, the polygon falls into itself, which leads to a serious problem.

From my point of view, using java.awt.geom.Area is the best approach:

My solution (based on Rogach code):

For each line connecting the two points of the track, I compute the surrounding polygon. Subsequently, I add (area union) the computed polygon to the area that does all the necessary calculations for me. Since Area strictly uses the “or” algorithm when adding new polygons, I don’t have to worry about the “self-intersections” of the polygon, as shown in the update above.

 Area area = new Area(); for (int i = 1; i < points.size(); i++) { Point2D point1 = points.get(i - 1); Point2D point2 = points.get(i); Line2D.Double ln = new Line2D.Double(point1.getX(), point1.getY(), point2.getX(), point2.getY()); double indent = 15.0; // distance from central line double length = ln.getP1().distance(ln.getP2()); double dx_li = (ln.getX2() - ln.getX1()) / length * indent; double dy_li = (ln.getY2() - ln.getY1()) / length * indent; // moved p1 point double p1X = ln.getX1() - dx_li; double p1Y = ln.getY1() - dy_li; // line moved to the left double lX1 = ln.getX1() - dy_li; double lY1 = ln.getY1() + dx_li; double lX2 = ln.getX2() - dy_li; double lY2 = ln.getY2() + dx_li; // moved p2 point double p2X = ln.getX2() + dx_li; double p2Y = ln.getY2() + dy_li; // line moved to the right double rX1_ = ln.getX1() + dy_li; double rY1 = ln.getY1() - dx_li; double rX2 = ln.getX2() + dy_li; double rY2 = ln.getY2() - dx_li; Path2D p = new Path2D.Double(); p.moveTo(lX1, lY1); p.lineTo(lX2, lY2); p.lineTo(p2X, p2Y); p.lineTo(rX2, rY2); p.lineTo(rX1_, rY1); p.lineTo(p1X, p1Y); p.lineTo(lX1, lY1); area.add(new Area(p)); } 

Answer 1

As I can see, this problem is similar to the problem of polygon buffering.

I think the following approach may help you:

• For each segment of your track, find two lines: one to the left and one to the right.
• Then, iterate over your selected lines and resolve intersections. For example: http://img25.imageshack.us/img25/7660/temprhk.png
• Add the caps to the ends and you're done! :)

And some code:

Moving a line to the left:

 Line2D l; double indent; // distance from central line double dx = ln.getX2() - ln.getX1(); double dy = ln.getY2() - ln.getY1(); double length = ln.getP1().distance(ln.getP2()); double newX1 = l.getX1() - indent*(dy/length); double newY1 = l.getY1() + indent*(dx/length); double newX2 = l.getX2() - indent*(dy/length); double newY2 = l.getY2() + indent*(dx/length); Line2D leftLine = new Line2D.Double(newX1, newY1, newX2, newY2); 

To move it to the right, change “+” to “-” and vice versa in the last 4 lines of code.

About working with intersections - if two segments of a line intersect, you simply display the intersection point. If they do not, the situation is a little more complicated - you, of course, can get the intersection, but in the case of a quick turn there will be strange flashes. I inserted an arc segment in a similar situation, but the code will be large and scattered, so I cannot insert it here.
Or, you can do as you show in the picture - just connect the end points.

<h / "> And by the way, if speed is not a big problem, you can use an even better way - for each track line find the left and right lines, add caps, pack it all in Path2D , then create an Area from Path2D.
In this case, you can make this “line with caps” the intersection of three areas: a rectangle, the points of which are only the end points of the right and left lines, and two circles with centers on the original segment of the track end.

When you compute areas for all rows, just cross them using the Area add () method.

This approach applies only to any situations, even self-intersections and breaks in the track.

Answer 2

See my answer to a similar question: "How to draw a diagram around any line."

The same idea as Rogach is here, but perhaps the various drawings and explanations will help clarify it.

Answer 3

If you don't want to write code for buffering as described by Rogach, JTS can do the magic for you. See the developer's guide for more information.

Answer 4

Half-baked sentence: calculate the normal to each segment. Then, for each vertex V_i interpolate the normals from their adjacent segments to get n_i (normalize it again) and add two vertices to V_i +/- a*n_i , where a is some scale factor.

If you join these points, you will not get exactly your blue polygon, but that might be enough.

You may need to keep track of which side the new peaks are on. If you can close the curve without self-intersections, this will become a point in the polygon for each vertex.