Во-первых, я хотел бы сказать, что использование уклонов для такого рода задач выполнимо, но также сложно из-за того, что они очень изменчивы в том смысле, что они могут переходить из отрицательной бесконечности в бесконечность с оченьнебольшое изменение в точке.Вот немного другой алгоритм, который основывается на углах , а не на склонах.Еще одним преимуществом использования этого является то, что системы координат здесь не имеют большого значения.Это выглядит так (я повторно использовал столько существующего кода, сколько смог):
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;
}
Теперь все, что осталось сделать, - это найти метод, который вычисляет угол со знаком, образованный тремя точками.Быстрый поиск в Google дал этот метод (из этого ТАКого вопроса):
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, first и next могли бы ориентироваться и приложить его к этому вопросу.Извините за неряшливость, я нарисовал ее довольно быстро, но теоретически это должно прояснить идею.
