如何通过组线段找到交叉点的最大数量 [英] How to find maximum number of intersectionS through set of line segments

问题描述

假如我行段在直角给定数量的坐标system.Each行给定为[X0，Y0]和[X1，Y1] .Algorithm应该找到一个垂直线的交叉最大数量。 在这个例子中它穿过四行：

什么算法能以最小的复杂性做吗？（我想preFER C ++，但某种伪code是也没关系）

PS思考的是，当几行开始/结束在相同的X坐标点

感谢你。

解决方案

1. 每一行转换为每个段一个区间[x_start，x_end]。
2. 创建一个包含标志是否为起点或终点，以及点值的数据结构。
3. 通过他们排序的所有的点，然后循环递增计数器，当你打一个起点和递减计数器，当你打的终点。跟踪的最大值。
4. 如果所需的Y值重复。

为O（n LG电子n）的时间复杂度

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.

解决方案

1. Convert each line to a interval of [x_start,x_end] for each segment.
2. Create a datastructure that contains a flag for whether it is a start or end point, as well as the point value.
3. 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.
4. Repeat with the Y values if desired.

O(n lg n) time complexity

这篇关于如何通过组线段找到交叉点的最大数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！