Fork me on GitHub

求折线段与直线的交点数

题目描述:
给定一个折线段,其由一个数组表示;例如数组[5,3,1,4]表示由[0,5] -> [1,3] -> [2,1] -> [3,4]构成的折线段。和一个整数,表示与X轴平行的直线;例如,2表示Y=2的直线,求折线段与直线的交点数,如果无穷的交点数用-1表示

输入:
[5,3,1,4], 2
输出:
2

思路:
有交点的地方,在Y轴方向差值之和不为正数。
特殊情况:点在直线上怎么办,折线与直线平行怎么办?

  1. 如果数组为空,没有交点返回0;
  2. 如果数组只有一个值,该点恰好在直线上,返回1;
  3. 如果线段[y1, y2]斜跨过直线,则(y1-value)*(y2-value)<0;
  4. 如果线段[y1, y2]恰好有一端在直线上,则(y1-value)*(y2-value)=0;
  5. 如果线段[y1, y2]两端都在直线上,则线段与直线重合,有无穷个交点,则(y1-value)==0 && (y2-value)=0,返回-1。

用C++实现了一个比较啰嗦的解法:

lines-intersection.cpplink
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/*=============================================================================
# Author: Hailin - https://fuhailin.github.io/lines-intersection/
# Email: hailinfufu@outlook.com
# Description: 求折线段与直线的交点数/
=============================================================================*/

#include <iostream>
#include <vector>
using namespace std;

int getSection(vector<int> vec, int val)
{
int sum = 0;
if (vec.empty())
return 0;
if (vec.size() == 1)
{
if ((vec[0] - val) == 0)
return 1;
else
return 0;
}
for (int i = 1; i < vec.size(); i++)
{
if ((vec[i] - val) * (vec[i - 1] - val) <= 0)
{
sum++;
if ((vec[i] - val) == 0)
sum--;
if ((vec[i] - val) == 0 && (vec[i - 1] - val) == 0)
return -1;
}
}
return sum;
}

int main(int argc, char const *argv[])
{
vector<int> test{5, 3, 2, 1, 3};
int res = getSection(test, 2);
cout << res << endl;
return 0;
}

您的支持将鼓励我继续创作!