java - 如何判断两点之间是否没有任何障碍物

Question

我目前正在尝试组合一种算法，通过该算法我可以知道平面中两个定义点之间是否存在障碍物。

这是一个示例图像。

我们可以从图像中看到点 1、2、3 和 6 都可以从原点访问。第 4 点和第 5 点不是。你穿过多边形。

我使用的代码如下。 pStartPoint 和 pEndPoint 是从原点到相关点的直线。该函数检查所有边缘以查看直线是否穿过边缘。

public double GetSlopeOfLine(Point a, Point b){

    double x =  b.y - a.y;
    double y = b.x - a.x;

    return (x / y);
}

public double GetOffsetOfLine(double x, double y, double slope){
    return (y - (slope * x));
}

public boolean IsPointAccessable(Point pStartPoint, Point pEndPoint){

    //Define the equation of the line for these points. Once we have slope and offset the equation is
    //y = slope * x + offset;

    double slopeOfLine = GetSlopeOfLine(pStartPoint, pEndPoint);
    double offSet = GetOffsetOfLine(pStartPoint.x, pStartPoint.y, slopeOfLine);

    //Collision detection for each side of each obstacle. Once we get the point of collision, does it lie on the 
    //line in between the two points? If so, collision, and I can't reach that point yet. 

    for (Iterator<Obstacles> ObstacleIt = AdjustedObstaclesList.iterator(); ObstacleIt.hasNext();) {

        Obstacles pObstacle = ObstacleIt.next();

        int NumberOfEdges = pObstacle.getPoints().size();

        for(int i=0; i<NumberOfEdges; i++){

            //Get Edge[i];
            int index = i;
            Point pFirstPoint = (Point)pObstacle.getPoints().get(index);
            if(i >= NumberOfEdges - 1)
                index = 0;
            else
                index = i+1;

            Point pNextPoint = (Point)pObstacle.getPoints().get(index);

            double slopeOfEdge = GetSlopeOfLine(pFirstPoint, pNextPoint);
            double offsetEdge = GetOffsetOfLine(pNextPoint.x, pNextPoint.y, slopeOfEdge);

            int x = Math.round((float) ((-offSet + offsetEdge) / (slopeOfLine - slopeOfEdge)));
            int y = Math.round((float) ((slopeOfLine * x) + offSet));

            //If it lies on either point I could be looking at two adjacent points. I can still reach that point. 
            if(x > pStartPoint.x && x < pEndPoint.x && y > pStartPoint.y && y < pEndPoint.y &&
               x > pFirstPoint.x && x < pNextPoint.x && y > pFirstPoint.y && y < pNextPoint.y){

                return false;
            }
        }
    }
    return true;
}

如果线穿过并且在 pStartPoint 和 pEndPoint 之间找到线交叉的点，我假设无法到达 pEndPoint。

这个函数不起作用，我想知道它是否与原点不在左下角而是在左上角以及我的窗口的(宽度，高度)位于底部这一事实有关正确的。因此坐标平面被弄乱了。

我的脑子一定很乱，因为我想不出如何对此进行调整，如果这真的是我的错误，因为我似乎无法修复错误。我认为通过将每个乘以 -1 来调整斜率和偏移量可能是解决方案，但这似乎不起作用。

我的解决方案正确吗？我的代码在检查交点时看起来是否正确？是否有更好的解决方案来查看某个点是否可以访问。

在此之后还有下一步，如果我现在位于多边形的一个点上，一旦我确定哪些点可以访问。例如，从点 1 开始，哪些点可以在不穿过多边形的情况下访问？

Answer 1

首先，我想说的是，使用斜率来完成这类任务是可行的，但也很困难，因为它们非常不稳定，从负无穷大到无穷大的变化非常大点的小变化。这是一个略有不同的算法，它依赖于角度 而不是坡度。使用它的另一个优点是坐标系在这里并不重要。它是这样的(我尽可能多地重用了您现有的代码):

public boolean IsPointAccessable(Point pStartPoint, Point pEndPoint) {

    //Collision detection for each side of each obstacle. Once we get the point of collision, does it lie on the 
    //line in between the two points? If so, collision, and I can't reach that point yet. 

    for (Iterator<Obstacles> ObstacleIt = AdjustedObstaclesList.iterator(); ObstacleIt.hasNext();) {

        Obstacles pObstacle = ObstacleIt.next();

        int NumberOfEdges = pObstacle.getPoints().size();

        for(int i=0; i<NumberOfEdges; i++){

            //Get Edge[i];
            int index = i;
            Point pFirstPoint = (Point)pObstacle.getPoints().get(index);
            if(i >= NumberOfEdges - 1)
                index = 0;
            else
                index = i+1;

            Point pNextPoint = (Point)pObstacle.getPoints().get(index);

            // Here is where we get a bunch of angles that encode in them important info on 
            // the problem we are trying to solve.
            double angleWithStart = getAngle(pNextPoint, pFirstPoint, pStartPoint);
            double angleWithEnd = getAngle(pNextPoint, pFirstPoint, pEndPoint);
            double angleWithFirst = getAngle(pStartPoint, pEndPoint, pFirstPoint);
            double angleWithNext = getAngle(pStartPoint, pEndPoint, pNextPoint);                

            // We have accumulated all the necessary angles, now we must decide what they mean. 
            // If the 'start' and 'end' angles are different signs, then the first and next points
            // between them. However, for a point to be inaccessible, it also must be the case that
            // the 'first' and 'next' angles are opposite sides, as then the start and end points
            // Are between them so a blocking occurs. We check for that here using a creative approach

            // This is a creative way of checking if two numbers are different signs.
            if (angleWithStart * angleWithEnd <= 0 && angleWithFirst * angleWithNext <= 0) {
                return false;
            }

        }
    }
    return true;
}

现在，剩下要做的就是找到一种计算由三个点形成的符号角的方法。快速谷歌搜索产生了这种方法(来自 this SO 问题):

private double getAngle(Point previous, Point center, Point next) { 
   return Math.toDegrees(Math.atan2(center.x - next.x, center.y - next.y)-
                    Math.atan2(previous.x- center.x,previous.y- center.y));
}

现在，这种方法在理论上应该可行(我正在测试以确保如果我发现角度符号或类似问题有任何问题，我会编辑我的答案)。我希望你明白我的想法，并且我的评论能很好地解释代码，但如果你想让我进一步阐述，请留下评论/问题。如果您不了解算法本身，我建议您拿出一张纸并按照算法查看到底发生了什么。希望这对您有所帮助!

编辑:为了希望帮助更好地理解使用角度的解决方案，我画了一张图，其中包含 start、end 的四种基本情况code>, first, next 是可以定向的，附在这个问题上。抱歉草率，我画得相当快，但理论上这应该使想法更清晰。