Определить, находится ли точка на вершинах многоугольника

Учитывая координаты многоугольника, Я нашел много алгоритмов для определения, находится ли точка в многоугольнике - например: [1] и [2]. Но ни один из этих алгоритмов не может определить, находится ли точка на вершинах этого многоугольника. Например, у меня есть многоугольник:Определить, находится ли точка на вершинах многоугольника

|---------------------| 
|      | 
|      | 
|---------------------|

Моя точка находится в правом верхнем углу. Мне нужен алгоритм, который говорит мне, находится ли точка внутри многоугольника. Как я могу это сделать?

источник

2013-07-08 Irgendw Pointer

Как определяются ваши полигоны? Предположительно, у вас нет координат вершин; вы работаете с изображением многоугольника? – beaker

Нет изображения. У меня есть координаты многоугольника и координаты моей точки. В большинстве случаев эта точка лежит на вершине многоугольника. И у меня всегда есть простые полигоны. –

Проверьте свою терминологию (вершину) и согласованность вопроса. «если точка лежит на вершинах этого многоугольника« vs »« находится ли точка внутри многоугольника vs », эта точка лежит на вершине многоугольника». –

Просто нашли решение прямо здесь. Это очень легко, и код от [1] имеет a и b уже реализован. Дополнительную информацию по исходному коду можно найти here.

const float EPSILON = 0.001f; 

bool IsPointOnLine(Point linePointA, Point linePointB, Point point) 
{ 
    float a = (linePointB.y - linePointA.y)/(linePointB.x - linePointB.x); 
    float b = linePointA.y - a * linePointA.x; 
    if (fabs(point.y - (a*point.x+b)) < EPSILON) 
    { 
     return true; 
    } 

    return false; 
}

источник

2013-07-09 09:14:39

Каково отношение к вопросу в сообщении? –

Этот код довольно плох в отношении изотропии: он проверяет вертикальное расстояние до линии, возвращает неправильные результаты для почти вертикальных линий и крушения для вертикалей. –

За исключением проблемы с вопросами, связанными с плавающей точкой , не точное совпадение, но достаточно близко, тот же алгоритм должен работать для обоих.
Просто выберите точку внутри многоугольника, создайте сегмент тестовой линии от контрольной точки до внутренней точки, а затем для каждого сегмента в многоугольнике определите, пересекает ли сегмент тестовой линии этот сегмент многоугольника. Чтобы считать как пересекающийся, граф пересекает открытый на одном конце многоугольного сегмента и закрыт на другом конце, т. е. если пересечение точно такое же, как начало многоугольника, подсчитайте его, но если оно точно такое же, как и конечная точка, не считайте Это. Вам нужно сделать это так, чтобы, когда тестовый сегмент пересекается с вершиной многоугольника, вы должны считать его только пересечением одного из двух сегментов по обе стороны от вершины.

Тогда, если контрольная точка находится внутри многоугольника, число пересечений будет четным числом, если оно снаружи, это будет нечетное число.

источник

2013-07-08 13:45:53

Определить, находится ли точка на вершинах многоугольника

ответ

Смежные вопросы