How to find maximum number of intersectionS through set of line segments [closed]
Suppose I am given number of lines segments in Cartesian coordinate system.Each line is given as [x0,y0] and [x1,y1].Algorithm should find a perpendicular that cross maximum number of lines. In this example it crosses four lines:
What开发者_运维问答 algorithm can do it with minimum complexity?(i would prefer c++ but some kind of pseudo code is OK too)
P.S The point to think about is when several lines start/end in the same x coordinate
Thank you.
- Convert each line to a interval of [x_start,x_end] for each segment.
- Create a datastructure that contains a flag for whether it is a start or end point, as well as the point value.
- Sort all the points and then iterate through them incrementing a counter when you hit a start point and decrementing a counter when you hit an end point. Keep track of the maximum value.
- Repeat with the Y values if desired.
O(n lg n) time complexity
If you want perpendicular, then here y
aren't needed. The algorithm is following.
- Sort lines to x0 be lower-equal to x1
- put all points to seperate array in sorted orden and with point store a flag which tells if the point is start or end of line
Run on array and get the segment which belong in maximal number of given intervals
vector<pair<double, unsigned char> > points; // (point, flag) pairs //read [x0, x1]s to points, be sure that x0 <= x1 (swap them otherwise) //0 for x0, 1 for x1 sort(points.begin(), points.end()); int ans = 0; int curstate = 0; for(int i = 0; i < points.size(); ++i) { if(points[i].second == 0) ++curstate; else --curstate; ans = max(ans, curstate); }
Iterate through the combinations of the existing lines. Build a list for each iteration containing all the other lines that are not perpendicular to the current line. Sort the lists into descending order by size. The (first) list with the largest size will be the solution. It will contain a list of lines that are crossed. There are an infinite number of lines that would be solutions. Send some of your salary to me as a royalty ;)
精彩评论