简单的算法（伪code）对于线段相交 [英] Simple algorithm (pseudo-code) for line segment intersection

问题描述

我试图解决这个问题，但我坚持就如何使这项工作。我会后的问题，然后解释在哪里，我在里面。

I am trying to solve this question, but I am stuck on how to make this work. I will post the question, and then explain where I am in it.

给定一组的水平线段和总大小为n的垂直线的，我们要计算由每个垂直线相交的水平段的数量。该算法应该是复杂度为O（N * logn）时间，并应通过排序来实现，由一个线性扫描以下。一个水平段由两个x坐标和y坐标指定时，由单个指定的垂直线X坐标。输出是数字数组计数[升]，每个垂直线升

Given a set of horizontal line segments and vertical lines of total size n, we want to compute the number of horizontal segments intersected by each vertical line. The algorithm should be of complexity O(n*logn), and should be achieved by sorting, following by a linear scan. A horizontal segment is specified by two x-coordinates and a y-coordinate, while a vertical line is specified by a single x-coordinate. Output is an array of numbers count[l], one for each vertical line l.

有关的排序，我想我会排序由线完成最早的（即最小的第二个X坐标，或在一条垂直线上的情况下，只是它的一个X坐标），让我有一个整套通过所有的线线性进程。我只是困惑，下面是如何排序的线性扫描应该发挥出来。如果任何人有任何提示，技巧或准则，我会AP preciate了！

For the sorting, I would think I would sort the entire set by which line finishes earliest (i.e. smallest second x-coordinate, or in the case of a vertical line, just its one x-coordinate) so that I have a linear progression through all of the lines. I am just confused as to how the linear scan following the sorting should be played out. If anyone has any hints, tips, or guidelines, I would appreciate it!

PS：这是实践的中期，因此，虽然它不一定功课，我仍然会标记为这样

PS: This is practise for a midterm, so while it's not necessarily homework, I will still mark it as such.

推荐答案

这个问题可以写其他方式：

The question can be written otherwise:

的Foreach水平线段（X1，X2），找到所有相交它的垂直线。你可以做到这一点的分类垂直线得到了一组位置x。

Foreach horizontal segment (x1,x2), find all the vertical lines that intersect it. You can do that by sorting the vertical lines getting a set of position x.

现在，运行在一套X的二进制搜索和位置X1，让我们把它的位置P1。用同样的方法X2，P2。交点为给定的段的数量等于P2-P1

Now, run a binary search and position x1 in the set of x's, let's call its position p1. Do the same for x2, p2. The number of intersection for the given segment equals p2-p1.

做到这一点对所有的横向链段。

Do that for all the horizontal segements.

排序垂直细分领域将采取O（KLOG（K））。每个搜索是O（日志（k））的完成，为每个段进行了两次：O（MLOG（K））。其中k是的垂直线数和m的水平段的数量。 N = M + K> M，K为此，整体复杂度为O（nlogn）。

Sorting the vertical segments will take O(klog(k)). Every search is done in O(log(k)) and is done twice for each segment: O(mlog(k)). Where k is the number of vertical lines and m the number of horizontal segments. n = m+k > m,k therefor, the overall complexity is O(nlogn).

这篇关于简单的算法（伪code）对于线段相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！