Draw a polygon for a given set of waypoints or a line?

Question

The above fig show you a geoLine (1 - 11). Each point is a geo-cordinate.

For a given geoLine I need to draw a Polygon (A bounding box) like in the bove image.

This is to find any Point Of Interest (POI) like PARKING, FUEL, RESTURANT near that GeoLine (Path / WayPoints) (20 / 30 mtrs on each side of geoLine. Not more than 50 mtrs.)

I guess Elasticsearch has a function were in you can specify polygon points and it gives what comes inside that polygon. In order to do that i need all points of polygon like in above fig.

Can someone please tell me on how to approach this? Any explanation along with the code will be helpful.

WayPoints :

13.0489062,77.6037472 13.0493921,77.6028423 13.0494861,77.6017586 13.0491692,77.6010208 13.0482264,77.6010494 13.0472498,77.6010711 13.0461878,77.6011007 13.0454626,77.6010805 13.0446403,77.6011248 13.0438409,77.6010804 13.0438986,77.6017758 13.0438545,77.6030737 13.0439865,77.6040809 13.0439203,77.6056271 13.0438668,77.6066616 13.0436551,77.6077865 13.0434993,77.6088242 13.0432396,77.609767 13.0429808,77.6104908 13.0428103,77.6112412 13.0426729,77.6121114 13.0424444,77.6129859 13.0422521,77.6136721 13.0418346,77.6145997 13.0415062,77.6155134 13.0412306,77.6162379 13.0409749,77.6171142 13.0410531,77.6178208 13.0411159,77.618711 13.0411254,77.6195973 13.0410934,77.6203541 13.0412376,77.6215924 13.0412091,77.6223422 13.0410685,77.6234799 13.0404355,77.6241354 13.0398567,77.6245906 13.038993,77.6252223 13.0381411,77.6258873

EDIT: Language is JAVA.

Answer 1

Take two edges defined by three points P[n-1], P[n] and P[n+1], havings normals m1 and m2 respectively.

Let

Then the normals are

Now the distance of Q from P[n] along m0 is

So therefore

Where Q' is the polygon point on the other side.

---

EDIT: C implementation:

#include <stdlib.h>
#include <math.h>
#include "bmp.h"

typedef struct v { double x, y; } vec_t;
#define VECT(x, y) (vec_t){x, y}

vec_t v_add(vec_t a, vec_t b) { return VECT(a.x + b.x, a.y + b.y); }
vec_t v_sub(vec_t a, vec_t b) { return VECT(a.x - b.x, a.y - b.y); }
vec_t v_mul(vec_t v, double c) { return VECT(v.x * c, v.y * c); }
vec_t v_div(vec_t v, double d) { return v_mul(v, 1.0 / d); }
double v_dot(vec_t a, vec_t b) { return a.x * b.x + a.y * b.y; }
double v_mag(vec_t a) { return sqrt(a.x * a.x + a.y * a.y); }
vec_t v_nor(vec_t v) { return v_div(v, v_mag(v)); }
vec_t v_prp(vec_t v) { return VECT(-v.y, v.x); }

vec_t get_disp(vec_t i, vec_t j, vec_t k, double d)
{
    vec_t a = v_sub(j, i), b = v_sub(k, j);
    vec_t m1 = v_nor(v_prp(a)), m2 = v_nor(v_prp(b));
    vec_t m0 = v_nor(v_add(m1, m2));
    return v_mul(m0, d / v_dot(m0, m1));
}

void compute_polygon(vec_t* P, vec_t* Q, int N, double d)
{
    int T = 2 * N - 1;
    for (int i = 1; i < N - 1; i++)
    {
        vec_t M = get_disp(P[i - 1], P[i], P[i + 1], d);
        Q[i]     = v_add(P[i], M); 
        Q[T - i] = v_sub(P[i], M);
    }
    vec_t A = v_mul(v_nor(v_prp(v_sub(P[1], P[0]))), d);
    vec_t B = v_mul(v_nor(v_prp(v_sub(P[N-1], P[N-2]))), d);
    Q[0] = v_add(P[0], A); Q[T] = v_sub(P[0], A);
    Q[N - 1] = v_add(P[N - 1], B); Q[N] = v_sub(P[N - 1], B);
}

int iround(double c) { return (int)((c > 0.0) ? c+0.5 : c-0.5); }
void draw_line(bmp_t* i, vec_t a, vec_t b, int c)
{
    bmp_aux_draw_line(i, iround(a.x), iround(a.y), iround(b.x), iround(b.y), c);
}
void draw_dot(bmp_t* i, vec_t p, int c)
{
    bmp_aux_draw_dot(i, iround(p.x), iround(p.y), 3, c);
}

int main()
{
    const int N = 5;
    vec_t P[N], Q[2*N];
    P[0] = VECT(30, 30);
    P[1] = VECT(70, 150);
    P[2] = VECT(130, 170);
    P[3] = VECT(190, 240);
    P[4] = VECT(270, 190);
    compute_polygon(P, Q, N, 10.0);
    bmp_t* img = bmp_new(300, 300);
    for (int i = 0; i < N-1; i++)
    {
        draw_line(img, P[i], P[i+1], 0);
        draw_dot(img, P[i], 0x0000FF);
    }
    draw_dot(img, P[N-1], 0x0000FF);
    for (int i = 0; i < 2*N-1; i++)
        draw_line(img, Q[i], Q[i + 1], 0xEEEE00);
    draw_line(img, Q[0], Q[2*N-1], 0xEEEE00);
    bmp_write(img, "a.bmp");
    bmp_free(img);

    return 0;
}

Points at (30, 30), (70, 150), (130, 170), (190, 240), (270, 190).