Question

Определить принадлежность точки заданному выпуклому многоугольнику. На паскаль абс, питон или с++

Answer 1

PascalABC.NET 3.4.0, сборка 1671 от 31.05.2018
Внимание! Если программа не работает, обновите версию!

begin
  var n:=ReadInteger('Число сторон многоугольника:');
  var xp:=new real[n];
  var yp:=new real[n];
  Writeln('Введите парами координаты вершин');
  for var i:=0 to n-1 do Read(xp[i],yp[i]);
  var (x,y):=ReadReal2('Введите координаты точки:');
  var (i,j,c):=(0,n-1,False);
  while i<n do begin
    if ((yp[i]<=y) and (y<yp[j]) or (yp[j]<=y) and (y<yp [i]))
      and (x<(xp[j]-xp[i])*(y-yp[i])/(yp[j]-yp[i])+xp[i]) then c:=not c;
    j:=i;
    i+=1;
    end;
  if c then Writeln('Внутри')
  else Writeln('Не внутри')
end.

Примеры
Число сторон многоугольника: 5
Введите парами координаты вершин
-5 2 2 6 7 3.1 4.3 -5 -6 -6
Введите координаты точки: 2.1 1.7
Внутри

Число сторон многоугольника: 5
Введите парами координаты вершин
-5 2 2 6 7 3.1 4.3 -5 -6 -6
Введите координаты точки: -2 5
Не внутри

Answer 2

Для определения принадлежности точки заданному выпуклому многоугольнику можно использовать алгоритм "лучей и отрезков" (Ray Casting Algorithm). Этот алгоритм заключается в том, чтобы провести луч из заданной точки в произвольном направлении и подсчитать количество пересечений этого луча с гранями многоугольника. Если количество пересечений нечётное, то точка находится внутри многоугольника, в противном случае — снаружи.

Вот пример кода на Python для проверки принадлежности точки выпуклому многоугольнику:

pythonCopy code
def is_inside_polygon(point, polygon):
    n = len(polygon)
    x, y = point

    # Проверка, находится ли точка справа от ребра
    def is_right_of_edge(p1, p2, test_point):
        x1, y1 = p1
        x2, y2 = p2
        return (x2 - x1) * (test_point[1] - y1) - (y2 - y1) * (test_point[0] - x1) < 0

    # Подсчет количества пересечений луча
    count = 0
    for i in range(n):
        p1, p2 = polygon[i], polygon[(i + 1) % n]
        if p1[1] == p2[1]:
            continue
        if y <= min(p1[1], p2[1]) or y > max(p1[1], p2[1]):
            continue
        if x > max(p1[0], p2[0]):
            continue
        if p1[1] == p2[1]:
            continue
        if x <= min(p1[0], p2[0]):
            if p1[1] > p2[1]:
                count += 1
        else:
            if is_right_of_edge(p1, p2, point):
                count += 1

    return count % 2 != 0

# Пример использования
polygon = [(0, 0), (2, 0), (2, 2), (0, 2)]
point_inside = (1, 1)
point_outside = (3, 1)

print(is_inside_polygon(point_inside, polygon))  # Вывод: True
print(is_inside_polygon(point_outside, polygon)) # Вывод: False

В этом примере polygon представляет собой список вершин многоугольника, а point — координаты точки, которую нужно проверить на принадлежность многоугольнику. Функция is_inside_polygon вернет True, если точка находится внутри многоугольника, и False, если точка находится снаружи.