3

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:

sample line construction

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?

sample detail

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);
3
  • 1
    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/…
    – user30184
    Aug 17, 2015 at 6:07
  • @user30184 Great reference. If I am able to understand and implement it, I will post it as answer.
    – Redoute
    Aug 17, 2015 at 7:27
  • 1
    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.
    – whuber
    Aug 17, 2015 at 15:02

2 Answers 2

2

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.

3
  • 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.
    – Redoute
    Aug 17, 2015 at 7:32
  • 1
    @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.
    – dpmcmlxxvi
    Aug 17, 2015 at 15:07
  • 2
    +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.
    – whuber
    Aug 17, 2015 at 15:16
1

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.

enter image description here

6
  • 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
    – Redoute
    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.
    – Rob Skelly
    Aug 16, 2015 at 17:29
  • Averaging produces incorrect solutions.
    – whuber
    Aug 17, 2015 at 15:12
  • Is it always incorrect? (Not being sarcastic.)
    – Rob Skelly
    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.
    – whuber
    Aug 17, 2015 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.