CODEWITHSUNDEEP
algorithmgeometry
SalysBruoga
SalysBruoga

Reputation: 1045

Counter number of groups of connected line segments

I am trying to solve the following problem: say we are given a bunch of line segments with some start and end coordinates. All of them are either horizontal or vertical. I am trying to come up with an algorithm to count the number of components in the given set of segments. A component is a set of line segments, where each segment intersects with at least one other segment (or in other words, it is possible to get from any point of any segment to any point on any other segment). Is it possible to do this better than the obvious O(N^2) solution?

Upvotes: 0

Views: 59

Answers (1)

MBo
MBo

Reputation: 80187

You can use line sweep algorithm (1) (2) to look for intersections.
Use these intersections to make clusters of segments with union-find algorithm.

Note that this approach might be quadratic when intersection count is high (about O(N^2)).

Upvotes: 1

Related Questions