前言
本来想把前面说的问题解决了再来写博客的，但解决方法是找到了，可我整不明白从哪里改，时隔太久，有点看不懂自己设置的数据结构，还是先写篇博客自己重温一下吧。
visual.py
可视化思路
顾名思义，可视化就是是否能够看到是否可视，之所以看不到是因为被遮挡被盖住，可视化的另一个含义就是能够直线到达（不用转弯），一个点能够直线到达另一个点，就表明这两点间是没有障碍物的，一个点对于另一个点是可视的。
一堆可视的连续点就可以组成一条可视的线，这条线的两端和观测点连接就构成了可视的区域，同时产生一个角度。我们将两个这样的可视区域进行重叠，得到新的可视区域应当是图中紫色阴影部分，而不是两个可视区域的并集。
对于这种情况，我给出的解决方法是比较两条可视的线距离观测点的远近，近处的必然覆盖远处的可视区域，这样的逻辑就复合客观事实了。
我将这种抽象的可视点组成的可视线具体化为下面两种情况，用障碍物来代替它们：
第一种情况最好理解，就不做阐述；第二种情况稍稍有些特殊，但是我们抽象可视线的概念是为了得到可视区域，因此在第二种情况下，障碍物之外的原可视区域就是实际的可视区域。
为了方便作图和理解，我仍用可视线的概念来讲解，当可视线足够多，就生成了足够多的可视区域，它们重叠在一起，形成了一个360°的不规则的可视区域，同时还产生了下图红色区域的绝对可视区域（没有任何障碍物遮挡的某角度范围）
此时，在这张图中，任何一个新添加的点落在了可视区域里，那么该点对于观测点就是可视的，就是可以直线抵达的；反之该点就是不可视的，不可直接到达的。
而我们路径规划算法所需要的，就是地图上的每个特殊点（障碍物顶点、起点、终点）的所有可视点（障碍物顶点）的字典集合。
为了满足这个需求，我们需要找出一个“可视线”作为障碍物的分割可视与非可视的线，比较每个点与观测点的距离是不是小于观测点与可视线上点的距离，是，该点就可视；否，该点就不可视。
通俗的来讲，就是判断一个障碍物的几个顶点是否被它前面的障碍物所遮盖，为什么是障碍物顶点呢，因为障碍物顶点是路径规划所需要走的点，是规划出来的路径的拐点，路径规划算法采用的是类狄克斯特拉算法。
数据预处理
main.py 传入的数据是列表：[障碍物点集,障碍物点集,...] 数据结构是： [[(x1,y1),(x2,y2),(x3,y3),(x4,y4)],[...],[...],...]
数据经过 visual.py 处理之后，传出的数据时一个字典：{障碍物顶点:[可视点,可视点,可视点,...],...} 数据结构是：{(x0,y0):[(x1,y1),(x3,y3),...],(x1,y1):[(x0,y0),...],...} ，传出的字典给 solution.py 进行路径规划处理
下面就来给大家解释一下是具体的实现步骤：
main 函数
传入的是所有障碍物顶点的二维列表，传出的是所有障碍物顶点的可视点集的一个字典。那么程序势必要对所有障碍物顶点进行遍历，对于任何一个正在被遍历的顶点，我们都要对除它自身外的其他所有顶点进行是否可视的判断，然后就能生成正在被遍历的顶点的可视点集了。逻辑如下：
一定要看注意哦！
因此 main 函数代码如下，它接收三个参数：起始点start、终止点end、障碍物顶点二维列表class_allpoints，函数中的 generateInterval 和 judgeVisualPoints 是我另外定义的用于生成障碍物区间与判断是否可视的函数
def main(start, end, class_allpoints):
#将二维列表class_allpoints转换成一维列表allpoints，并加入start
allpoints = [i for each in class_allpoints for i in each]
graph = dict()
if start not in allpoints:
allpoints.append(start)
#遍历所有“障碍物顶点”（一维列表allpoints）
for this_point in allpoints:
pop_allpoints = None
#深度拷贝一个不包含this_points的其他障碍物顶点列表，并遍历它，判断是否可视
for each in class_allpoints:
for i in each:
if i == this_point:
#采用深度拷贝
pop_allpoints = copy.deepcopy(class_allpoints)
pop_allpoints[class_allpoints.index(each)].remove(i)
break
if pop_allpoints:
break
pop_allpoints = pop_allpoints if pop_allpoints else copy.deepcopy(class_allpoints)
data = generateInterval(this_point, pop_allpoints)
graph[this_point] = judgeVisualPoints(this_point, pop_allpoints, data[0], end)
return graph
- 为了得到含有起始点终止点的“障碍物顶点”列表，我声明了
allpoints来盛放 - 又拷贝了一个
pop_allpoints障碍物顶点列表，用以产生某个点的障碍物区间，这个列表拷贝自class_allpoints，但它不包含观测点this_point，它就是逻辑图中蓝色的点集。 - 值得提醒的是，
pop_allpoints是一个二维列表，以障碍物为单位，与class_allpoints不同的是不含观测点this_point，重要的事情所两遍。 - 在拷贝时一定要采用深度拷贝，因为普通的拷贝只是将两个引用指向了同一个对象，对任何一个引用做删减修改都会导致另一个引用产生不可逆变化，毕竟修改的是同一个对象。
- 一定要把 main 的代码结合逻辑图一起看哦，逻辑图就是框架。
generateInterval 函数
这段代码写的有点乱，而且发现里面还有一些冗余代码，而且算法也不够普适，打算后面再重新写。大家将就着看，我把具体的逻辑给大家讲清楚：
- 规定了一个角度概念[-90°,270°)
- 对某个障碍物的四个顶点，计算其与观测点的角度，通过比较得出最大范围（最大的障碍物区间范围）并记录
- 存在特殊的情况，障碍物横跨-90°（在观测点正上方，如图右示），进行特殊处理，将障碍物拆分成两个障碍物，保证不存在横跨-90°的障碍物存在
- 对所有的障碍物进行2、3的操作
- 返回所需数据
def generateInterval(this_point, pop_allpoints):
angleANDdistance = list()
for each in pop_allpoints:
min_y = None #用于记录特殊情况下最底边到 该点 的距离
maxTmp = [None,None,None]
minTmp = [None,None,None]
for point in each:
tmp = (math.degrees(math.atan((point[1]-this_point[1])/(point[0]-this_point[0]))) if (point[0]-this_point[0]!=0) else -90 if (point[1]-this_point[1]>0) else 90)
tmp = tmp + 180 if point[0]-this_point[0]>0 else tmp #认为定义了角度的范围是[-90,270)，从正北方向逆时针转
#在遍历的基础上进行变量比较得到 最大和最小
maxTmp = [point,tmp,math.sqrt((point[1]-this_point[1])**2+(point[0]-this_point[0])**2)] if (maxTmp[1]==None or tmp > maxTmp[1]) else maxTmp
minTmp = [point,tmp,math.sqrt((point[1]-this_point[1])**2+(point[0]-this_point[0])**2)] if (minTmp[1]==None or tmp < minTmp[1]) else minTmp
#对跨-90°的区间进行分开处理。拆分成两个障碍物，保证不存在跨越270°到-90°区间的障碍物。
if maxTmp[1]-minTmp[1] > 180 and (maxTmp[1]!=270 and minTmp!=0 or minTmp!=-90 and maxTmp!=180): #存在一种特例，当障碍物在起始点的正上方左右时，max_angle-min_angle不能表示障碍物区间
#对这种情况进行单独处理，一旦有点触发了这种情况（这里的特殊情况排除了特殊点为正上方障碍物的下面两个端点），就执行特殊代码，执行完后直接跳出该层循环，对下一个障碍物进行处理
#直接得到最大点和最小点（相对于角度而言）
maxPoint = (min(point[0] for point in each),min(point[1] for point in each))
minPoint = (max(point[0] for point in each),min(point[1] for point in each))
#为了和上面的一般情况统一，这里也用maxTmp和minTmp
maxTmp = [maxPoint,
(math.degrees(math.atan((maxPoint[1]-this_point[1])/(maxPoint[0]-this_point[0]))) if (maxPoint[0]-this_point[0]!=0) else -90),
math.sqrt((maxPoint[1]-this_point[1])**2+(maxPoint[0]-this_point[0])**2)]
minTmp = [minPoint,
(math.degrees(math.atan((minPoint[1]-this_point[1])/(minPoint[0]-this_point[0])))+180 if (minPoint[0]-this_point[0]!=0) else 270),
math.sqrt((minPoint[1]-this_point[1])**2+(minPoint[0]-this_point[0])**2)]
min_y = min(point[1] for point in each) #特殊情况下障碍物最底边距 该点 的距离
break
#对一般和特殊情况的最后一次分离处理，生成我们需要的区间
if min_y:
#将特殊情况下障碍物的区间 分开，因为其包含无穷大,所以也是从无穷大分开的
angleANDdistance.append([minTmp[1:],[270,min_y-this_point[1]]])
angleANDdistance.append([[-90,min_y-this_point[1]],maxTmp[1:]])
else:
angleANDdistance.append([minTmp[1:],maxTmp[1:]])
return [angleANDdistance,angleANDpoint]
judgeVisualPoints 函数
这个函数内涵了 __IsInIntervals 私有函数，整个函数的逻辑是：
- 对于那些落在障碍物区间上的点，给所落在对应区间的这个障碍物做弧，通过比较距离来判断点是否可视
- 对于那些没落在所有障碍物区间上的点（比如终止点），那么它一定是可视的
def judgeVisualPoints(this_point, pop_allpoints, angleANDdistance, end):
visualPoints = list()
sequentialPoints = sorted([i for each in pop_allpoints for i in each]+[end], key=lambda x:(x[0]-this_point[0])**2+(x[1]-this_point[1])**2)
for point in sequentialPoints:
#对新计算的角进行数据处理
angle = (math.degrees(math.atan((point[1]-this_point[1])/(point[0]-this_point[0]))) if (point[0]-this_point[0]!=0) else -90 if (point[1]-this_point[1]>0) else 90)
angle = angle + 180 if point[0]-this_point[0]>0 else angle
#用与判断点是否在区间，不再就返回false，在就返回所在区间对应的原始数据
tmp = __IsInIntervals(angle, angleANDdistance)
if tmp:
distance = (angle-tmp[0][0])/(tmp[1][0]-tmp[0][0])*(tmp[1][1]-tmp[0][1])+tmp[0][1]
if math.sqrt((point[1]-this_point[1])**2+(point[0]-this_point[0])**2) < distance:
visualPoints.append(point)
else:
visualPoints.append(point)
return visualPoints
def __IsInIntervals(angle,Raw_intervalsList):
#一个排序，把Raw_intervalsList按照最近距离进行排序(最远距离不行！！【如果最近距离也有问题的话，可以选择对全部区间遍历一遍，时间基本差不多吧、】)，以保证算法依据人的想法正确运行，避免出现不可视点被加入可视点集
#因为总是前面的障碍物挡住后面的障碍物，这才导致某些点不可视
Raw_intervalsList.sort(key=lambda x: x[0][1] if x[0][1]<x[1][1] else x[1][1])
for each in Raw_intervalsList:
intervalsList = (each[0][0],each[1][0])
if angle>intervalsList[0] and angle<intervalsList[1]:
return each
else:
continue
return False
问题
通过上面这个图，我们一定已经看出了这个程序所存在的问题，那就是这个画弧的部分
画弧的机制可以去看一下[大创]一步一步写路径规划并绘图可视化 I 的最后一张图。
我们可以看到弧线以内的区域未必都是真的可视，比如图中红色区域，就是不可视的，但是一旦有点落在这个区域，将被程序认为是直接可视的，可以直接直线到达，那么就会出现上一篇总博中出现的问题：
解决方案
那么针对于此，我给出的解决方案是去掉画弧，改成画对角线，也是一种抽象。毕竟障碍物本身就是不可视的，没有另外一个障碍物的顶点会落在本障碍物内部，那么对角线就完全可以充当可视与不可视的界线，还很合理（这么想着，只要是障碍物内部的一条最长的线就可以充当界线）
在一篇博客上发现了现成的方法，秉承拿来主义，复习了一下高中知识，拿来就用了。
#障碍物对角线 解决可视点问题
def GeneralEquation(first_x,first_y,second_x,second_y):
# 一般式 Ax+By+C=0
# from http://www.cnblogs.com/DHUtoBUAA/
A=second_y-first_y
B=first_x-second_x
C=second_x*first_y-first_x*second_y
return A,B,C
def GetIntersectPointofLines(x1,y1,x2,y2,x3,y3,x4,y4):
# from http://www.cnblogs.com/DHUtoBUAA/
A1,B1,C1=GeneralEquation(x1,y1,x2,y2)
A2, B2, C2 = GeneralEquation(x3,y3,x4,y4)
m=A1*B2-A2*B1
if m==0:
print("无交点")
else:
x=(C2*B1-C1*B2)/m
y=(C1*A2-C2*A1)/m
return x,y
只要我提供四个点的坐标，就可以得到焦点的坐标，然后就可以比较距离，解决可视与不可视问题了。
最后
改写代码后，成功解决了之前的bug
自此，visual.py 的讲解和修改就结束了。
转载请注明出处：https://www.cnblogs.com/dragonbean/p/13443642.html