# Construct curve of equal distance from two straight lines

Given two straight lines defined by two points each, I want to get the line which separates points nearer to line a from points nearer to line b. The attached PostGIS code is an example case, it finds points of equal distance by creating a lot of buffers around the lines and intersecting them:

Is there an algorithm to calculate this line more direct, without sampling points or rastering?

I thought the line for this example would have a linear central part, but the dots are placed slightly under that line. Are they placed correctly?

``````CREATE TABLE tv_lines1 (
id text PRIMARY KEY,
geom geometry(linestring, 4326)); -- set meaningless CRS for easy handling in QGIS
INSERT INTO tv_lines1 (id, geom)
SELECT 'a', ST_SetSRID(ST_MakeLine(ST_Point(0.0, 0.0), ST_Point(30.0, 0.0)), 4326);
INSERT INTO tv_lines1 (id, geom)
SELECT 'b', ST_SetSRID(ST_MakeLine(ST_Point(16.0, 2.0), ST_Point(40.0, 12.0)), 4326);
CREATE INDEX ON tv_lines1 USING gist (geom);

-- create buffers in Steps of 0.1
CREATE TABLE tv_buffers (
line_id text,
size float,
geom geometry(linestring, 4326),
PRIMARY KEY (line_id, size));
INSERT INTO tv_buffers (line_id, size)
SELECT
id,
generate_series(1, 1000) / 10.0
FROM tv_lines1;
UPDATE tv_buffers bf
SET geom = ST_ExteriorRing(ST_Buffer(l1.geom, size))
FROM tv_lines1 l1
WHERE l1.id = bf.line_id;
CREATE INDEX ON tv_buffers USING gist(geom);

-- find intersections
CREATE TABLE tv_intersections (
id SERIAL PRIMARY KEY,
distance float,
geom geometry(point, 4326));
INSERT INTO tv_intersections (distance, geom)
SELECT
bf1.size,
(ST_DUMP(ST_Intersection(bf1.geom, bf2.geom))).geom
FROM tv_buffers bf1, tv_buffers bf2
WHERE bf1.line_id = 'a' AND
bf2.line_id = 'b' AND
bf1.size = bf2.size;
CREATE INDEX ON tv_intersections USING gist(geom);
``````
• You are doing something like Voronoi diagram for two line segments. Perhaps this article gives some thoughts to you voronoi.com/wiki/images/7/76/… Aug 17, 2015 at 6:07
• @user30184 Great reference. If I am able to understand and implement it, I will post it as answer. Aug 17, 2015 at 7:27
• Your readers might appreciate this question better if they are reminded that the solution consists of a line segment and two rays connected by portions of two parabolas. BTW, the dots look placed correctly. If the blue line just above it is intended to pass through the midpoints of two blue line segments (and has the equation you have written), then it definitely is incorrect. The correct formula is y = x/5 - 56/25. Aug 17, 2015 at 15:02

How about partitioning your space into 9 regions and imposing the equal distance criteria separately in each. For example,

For line segment #1, partition the space into 3 regions

1. Points whose projection along the line segment normal actually fall on the line segment. Call it `C1`.
2. Points whose projection along the line segment normal fall to the left of the line segment (i.e., they land on the imaginary line extending from the segment but not on the segment itself). Call it `L1`.
3. Same as Region 2 but the points land to the right. Call it `R1`.

Repeat the above for line segment #2. Call its regions `C2`, `L2`, and `R2`.

The intersection of all combinations of these regions gives you 9 distinct regions where the equation for the distance from a point in that region to both line segments can be computed analytically. For example, for regions `C1` and `C2` the equations are computed analytically to their respective segment. For regions `L1`, `R1`, `L2`, and `R2` the distance is the distance to the closest end-point to their respective segment.

You can compute these distances analytically and combine the answers from all 9 regions.

• As far as I understand you suggest a form of rastering, which I want to avoid. In my second picture the blue lines show the intersection of regions C1 and C2 and the resulting dividing line, correct? However, the more challenging parts are the curves outside this region. Aug 17, 2015 at 7:32
• @Redoute No, you don't have to raster at all. You can solve the problem analytically. It just takes a little algebra. You know the line segment end-points, which gives you the regions I describe above. It is just a matter of writing down the inequalities and solving the equations in each region. As far as your example, outside that region I think the problem is easier. Because you only have, at most, one point-to-line equation and the other is point-to-end-point equation, just set them equal to each other. Aug 17, 2015 at 15:07
• +1 This is a good approach. The proposed partition is based on the nature of the closest points on the line segments and thereby reduces the problem to up to nine Voronoi problems involving either two points, two line segments (in both cases, the solution will be a line segment or line), or a point and a line segment (where the solution is a portion of a parabola: use the point-directrix definition). Moreover, a GIS already contains the code to create this partition, which is really where the hard work is done, so it's a nice way to exploit existing capabilities. Aug 17, 2015 at 15:16

You can take an average of each pair of end points and draw a line between them. Say the left two points have ID 1 and 2,

``````WITH t AS (
SELECT avg(ST_X(geom)) as x, avg(ST_Y(geom)) as y
FROM test
WHERE gid in (1, 2)
) INSERT INTO test (geom)
SELECT ST_SetSRID(ST_MakePoint(t.x, t.y), 4326) FROM t;
``````

That creates a new point midway between them. Do the same for the right hand pair, then draw a line between them. If the locations of the endpoints are important, you can maybe trim the line once you've created it.

• No, this is not what I want. Look at the example, where the line between the averages will cross line b. !line crosses line b Aug 16, 2015 at 17:18
• Yeah, I see what you mean. You could easily create new endpoints by locating a point on line A that is closest to the endpoint of line B (and the reverse at the other end), and then use the averaging method, but you might want a more general solution. Aug 16, 2015 at 17:29
• Averaging produces incorrect solutions. Aug 17, 2015 at 15:12
• Is it always incorrect? (Not being sarcastic.) Aug 17, 2015 at 16:47
• The only situation in which it is correct is when the two segments are reflections of each other around some axis. Aug 17, 2015 at 19:24