Stack Overflow
Stack Overflow

Questions tagged [line-segment]

90 questions
442
votes
56 answers

Shortest distance between a point and a line segment

I need a basic function to find the shortest distance between a point and a line segment. Feel free to write the solution in any language you want; I can translate it into what I'm using (Javascript). EDIT: My line segment is defined by two…
Eli Courtwright
  • 186,300
  • 67
  • 213
  • 256
27
votes
9 answers

The algorithm to find the point of intersection of two 3D line segment

Finding the point of intersection for two 2D line segments is easy; the formula is straight forward. But finding the point of intersection for two 3D line segments is not, I afraid. What is the algorithm, in C# preferably that finds the point of…
Graviton
  • 81,782
  • 146
  • 424
  • 602
12
votes
2 answers

Find overlap between collinear lines

Given two collinear line segments AB and CD, how do I find if they overlap? How do I locate the start and end points of the overlap? Below is the approach I am using. I am first ensuring that A < B and C < D. if(pa < pc){ if(pc < pb){ if(pd <…
Agnel Kurian
  • 57,975
  • 43
  • 146
  • 217
9
votes
3 answers

Bentley-Ottmann Algorithm Implementation

Is there any existing Bentley-Ottmann Algorithm Implementation/library in C# or Java?
Sam
  • 933
  • 5
  • 14
  • 26
8
votes
1 answer

Identify all co-linear line segments (in matlab)

I have posted a related but not the same question here https://stackoverflow.com/questions/8279698/measuring-length-of-dna-fibers-from-an-image-of-single-molecules Background: I have many images that look like this: I would like to identify all…
Lee Sande
  • 457
  • 5
  • 15
8
votes
1 answer

Connect an even number of nodes without intersection

I have two sets of n nodes. Now I want to connect each node from one set with another node from the other set. The resulting graph should have no intersections. I know of several sweep line algorithms (Bentley-Ottmann-Algorithm to check where…
Soift
  • 167
  • 7
6
votes
3 answers

Outermost Polygon from a set of Edges

Suppose I have a set of 2d line segments that are all connected. I need an algorithm that finds the outermost segments in the set. That is, the minimal subset that bounds the same region. Note: this is not the same as finding the convex hull of the…
Charles Taylor
  • 686
  • 6
  • 23
5
votes
1 answer

Distance from a point to a line segment in 3d (Python)

I am looking for Python function that would compute distance from a point in 3D (x_0,y_0,z_0) to a line segment defined by its endpoints (x_1,y_1,z_1) and (x_2,y_2,z_2). I have only found solution for 2D for this problem. There are solutions to…
Sanya Pushkar
  • 180
  • 1
  • 16
5
votes
2 answers

Sorting and grouping array of line segments that describes polygons

I'm parsing some data, given as an array of line segments that describe several closed, arbitrary shapes/polygons. These shapes can be concave. Here's a simplified example of what I'm looking at: However, the data I'm provided has the segments in…
interloper
  • 71
  • 8
4
votes
5 answers

Line Segment container for fast Ray intersection? (2D)

I have a ray, I need to find the closest line segment that it hits. I think it's possible to do this in O(log n) time if I sort the line segments first, but I can't remember how to sort them... I think some sort of tree would work best, but how do I…
mpen
  • 272,448
  • 266
  • 850
  • 1,236
4
votes
2 answers

Segmenting overlapping thick lines on a binary image

I do have a binary image as shown below after applying various preprocessing and detection pipelines onto original image. As seen in the picture there are actually 2 runways (tarmacs) for planes which are crossing each other on an intersection…
colt.exe
  • 708
  • 8
  • 24
4
votes
1 answer

How do I break a non-straight line into even segments?

I have a non-straight line defined by a series of x, y coordinate points. I could draw a straight line on-screen directly between these points with no problem. Unfortunately, I have to draw the line in segments of equal length. Here is an…
jpwrunyan
  • 530
  • 5
  • 22
4
votes
1 answer

Matlab - Failures of function to detect collisions between line segments and circle

Many questions exist already covering how to detect collisions between a line segment and a circle. In my code, I am using Matlab's linecirc function, then comparing the intersection points it returns with the ends of my line segments, to check that…
chrisb2244
  • 2,940
  • 22
  • 44
4
votes
3 answers

Algorithm to Find Overlapping Line Segments

n4------------------n3--------------------n2--n1 | | | | | | | P1 | | | | | | | n6--n5 | …
magneticMonster
  • 2,373
  • 6
  • 30
  • 46
3
votes
3 answers

Trying to find an algorithm to detect rectangles in images

At the moment I have detected edges in an image and I am planning to extract line segments from the edges using a hough transform. Once I have the segments I am planning on finding corners where two segments cross over. Is there an algorithm that…
jzz
  • 93
  • 1
  • 1
  • 5
1
2 3 4 5 6