# Vertex position problem for connected lines

I’m trying to generate a mesh to display connected segments representing street lines in a mini map. I have problem with vertex orientation that my math knowledge has hard time to resolve.

Let’s consider 3 points p0, p1 and p2.

I use this code to create the vertices from the segment between p0 and p1 (the same code is then used for the segment from p1 to p2):

height = 2.0f; // desired line thickness
vertices[0] = new Vector3(p0.position.x, p0.position.y - height / 2.0f, 0);
vertices[1] = new Vector3(p1.position.x, p1.position.y - height / 2.0f, 0);
vertices[2] = new Vector3(p0.position.x, p0.position.y + height / 2.0f, 0);
vertices[3] = new Vector3(p1.position.x, p1.position.y + height / 2.0f, 0);


The result looks like this:

Not that bad, except that the "thickness" of the line is not constant. If you look closely to the segment left and right borders, they are aligned (going from bottom to top). The problem comes from the “height” variable that is added or subtracted too naively to the positions.

What I’d like to have is something like this, with oriented borders / vertex.

However I don’t know how to proceed.

Any help or comment would be appreciated. Thanks for your time.

**** EDIT **** Thanks to @wondra's solution I managed to do what I needed to. Here is how:

    // Returns point of intersection
// TODO: check if lines are parallel
public Vector3 LineIntersection(Vector3 p1, Vector3 p2, Vector3 p3, Vector3 p4)
{
float ma = (p2.y - p1.y) / (p2.x - p1.x);
float mb = (p4.y - p3.y) / (p4.x - p3.x);

float ba = p1.y - (p1.x * ma);
float bb = p3.y - (p3.x * mb);

float x = -(ba - bb) / (ma - mb);
float y = ma * x + ba;

return new Vector3(x, y);
}

/// --- LOOPING THROUGH POINTS ---

// @wondra's solution
Vector2 dir = (sec_node.position - prim_node.position).normalized;
Vector2 perp = new Vector2(dir.y, -dir.x);

vertices[vert_idx]      = prim_node.position + (perp * -height / 2.0f);
vertices[vert_idx + 1]  = sec_node.position + (perp * -height / 2.0f);
vertices[vert_idx + 2]  = prim_node.position + (perp * height / 2.0f);
vertices[vert_idx + 3]  = sec_node.position + (perp * height / 2.0f);

if ( vert_idx > 4 )
{
int vert_idx_bis = vert_idx - 4;
vertices[vert_idx] = LineIntersection(vertices[vert_idx], vertices[vert_idx + 1], vertices[vert_idx_bis + 1], vertices[vert_idx_bis]);
vertices[vert_idx_bis + 1] = vertices[vert_idx];

vertices[vert_idx + 2] = LineIntersection(vertices[vert_idx + 2], vertices[vert_idx + 3], vertices[vert_idx_bis + 3], vertices[vert_idx_bis + 2]);
vertices[vert_idx_bis + 3] = vertices[vert_idx + 2];
}
/// --- END LOOP


Lets start with the easiest, the segment from p0 to p1. First of all you need the perpendicular direction to this segment. To do this get the "normal" direction first simply subtract one point from the other, then use the well-known trick to get perpendicular vector (swap coords and negate one):

Vec3 seg01_dir = (p1 - p0).Normalize();
Vec3 seg01_perp = new Vec3(seg01_dir.y, -seg01_dir.x, 0); //I assume 2d data(!)


Now you have all you need to get all 4 points of the segment rectangle, just offset endpoints by half of the desired width in perpendicular direction:

height = 2.0f; // desired line thickness
vertices[0] = p0 + (seg01_perp * (-height / 2.0f));
vertices[1] = p1 + (seg01_perp * (-height / 2.0f));
vertices[2] = p0 + (seg01_perp * (height / 2.0f));
vertices[3] = p1 + (seg01_perp * (height / 2.0f));


...this would cower your example but be aware: The corners of the line strip would be broken if you did something that simple - the actual positions of vertices[1] and vertices[3] depends on next segment!
To be more precise you need to find(same as above) all 4 corners for next segment first and then correct the adjacent vertices (for p0->p1 and p1->p2 those are vertices 1,3,4 and 6). In order to correct the coordinates you need to find the intersection between lines given by vertices 0 to 1 and 4 to 5 giving you correct position for vertices 1 and 4 (the "lower"/right joint next to p1"). Similarly the intersection of lines given by 2 to 3 and 6 to 7 gives correct position for vertices 3 and 6 (the "upper"/left joint next to p1"). Repeat for all joints.
note: I dont go into implementation details of the line intersection - there are plenty of good implementations around here

• Thanks a lot! I have edited my question to add your answer and the intersection computation. Nov 26, 2015 at 18:36
• @lvictorino one comment to the intersection code: make sure it works for inputs like p2.x - p1.x = 0(=zero division), it may cause unexpected behavior - not sure how Unity handles it. Nov 26, 2015 at 19:29