Skip to main content
Software Engineering

Return to Answer

replaced http://stackoverflow.com/ with https://stackoverflow.com/
Source Link
Community Bot
Community Bot
  • 1

I assume you have the (X, Y) coordinates of each point in your graph.

Determining if two line segments intersect is a solved problem - see How do you detect where two line segments intersect?How do you detect where two line segments intersect?

All (as if!) you need do is make a list of your line segments, then for each segment determine if it intersects with any segment further down the list (if you've already determined that segment 1 does not intersect segment 3, there's not point in testing if segment 3 intersects segment 1)

If you have thousands of points this is going to be an expensive and slow process unless you put some thought into weeding out line segments that couldn't possibly intersect.

I assume you have the (X, Y) coordinates of each point in your graph.

Determining if two line segments intersect is a solved problem - see How do you detect where two line segments intersect?

All (as if!) you need do is make a list of your line segments, then for each segment determine if it intersects with any segment further down the list (if you've already determined that segment 1 does not intersect segment 3, there's not point in testing if segment 3 intersects segment 1)

If you have thousands of points this is going to be an expensive and slow process unless you put some thought into weeding out line segments that couldn't possibly intersect.

I assume you have the (X, Y) coordinates of each point in your graph.

Determining if two line segments intersect is a solved problem - see How do you detect where two line segments intersect?

All (as if!) you need do is make a list of your line segments, then for each segment determine if it intersects with any segment further down the list (if you've already determined that segment 1 does not intersect segment 3, there's not point in testing if segment 3 intersects segment 1)

If you have thousands of points this is going to be an expensive and slow process unless you put some thought into weeding out line segments that couldn't possibly intersect.

Source Link
Dan Pichelman
Dan Pichelman
  • 13.8k
  • 8
  • 44
  • 73

I assume you have the (X, Y) coordinates of each point in your graph.

Determining if two line segments intersect is a solved problem - see How do you detect where two line segments intersect?

All (as if!) you need do is make a list of your line segments, then for each segment determine if it intersects with any segment further down the list (if you've already determined that segment 1 does not intersect segment 3, there's not point in testing if segment 3 intersects segment 1)

If you have thousands of points this is going to be an expensive and slow process unless you put some thought into weeding out line segments that couldn't possibly intersect.