Задача (сложность - средняя)

@Schulzkafer · Регистрация: 31.12.2019

Студворк — интернет-сервис помощи студентам

Помогите, пожалуйста, решить задачу.
Inside Block
При планировании города, важно понимать и оценивать границы различных городских структур. Парки, озера или жилые кварталы могут быть представлены, как многоугольники и описаны с помощью координат в прямоугольной системе координат. Нам нужна программа, чтобы определять находится ли определенная точка внутри многоугольника или снаружи.

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

(Прикрепил изображения снизу)
Для примера на левом изображении показан многоугольник описанный, как ((2,1),(1,5),(5,7),(7,7),(7,2)) и точка в (2,7). И результат -- False.
На правом изображении точка находится на линии и считается, как внутри. Результат -- True.

Входные данные: Два аргумента. Координаты многоугольника, как кортеж (tuple) кортежей с двумя числами в каждом. Координаты проверяемой точки, как кортеж двух чисел.

Выходные данные: Данная точка внутри многоугольника или нет, как булево значение (bool).

Примеры:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
isInside([[1, 1], [1, 3], [3, 3], [3, 1]],
 [2, 2]) == true
isInside([[1, 1], [1, 3], [3, 3], [3, 1]],
 [4, 2]) == false
isInside([[1, 1], [4, 1], [2, 3]], [3, 2]) == true
isInside([[1, 1], [4, 1], [1, 3]], [3, 3]) == false
isInside([[2, 1],
  [4, 1],
  [5, 3],
  [3, 4],
  [1, 3]],
 [4, 3]) == true

Как это используется: Эта концепция используется для распознания изображений. Но также это пригодится в картографическом ПО.

Предусловия:
all(x ≥ 0 and y ≥ 0 for x, y in polygon)
point[0] ≥ 0 and point[1] ≥ 0

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function isInside(a, b) {
    // your code here
    return undefined;
}
 
// These "asserts" are used for self-checking
assert.equal(isInside([[1, 1], [1, 3], [3, 3], [3, 1]],
 [2, 2]), true);
assert.equal(isInside([[1, 1], [1, 3], [3, 3], [3, 1]],
 [4, 2]), false);
assert.equal(isInside([[1, 1], [4, 1], [2, 3]], [3, 2]), true);
assert.equal(isInside([[1, 1], [4, 1], [1, 3]], [3, 3]), false);
assert.equal(isInside([[2, 1],
  [4, 1],
  [5, 3],
  [3, 4],
  [1, 3]],
 [4, 3]), true);
assert.equal(isInside([[2, 1],
  [4, 1],
  [3, 2],
  [3, 4],
  [1, 3]],
 [4, 3]), false);
assert.equal(isInside([[1, 1],
  [3, 2],
  [5, 1],
  [4, 3],
  [5, 5],
  [3, 4],
  [1, 5],
  [2, 3]],
 [3, 3]), true);
assert.equal(isInside([[1, 1],
  [1, 5],
  [5, 5],
  [5, 4],
  [2, 4],
  [2, 2],
  [5, 2],
  [5, 1]],
 [4, 3]), false);

@Iverycool · 08.06.2020, 19:29

Schulzkafer, хорошие задачки вы находите!
По началу пытался как-то сам попробовать, но затем понял, что здесь чистая математика и загуглил

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function isInside(p, point) {
    let result = false;
    let j = p.length - 1;
    for (let i = 0; i < p.length; i++) {
        if ((p[i][1] < point[1] && p[j][1] >= point[1] || p[j][1] < point[1] && p[i][1] >= point[1]) &&
            (p[i][0] + (point[1] - p[i][1]) / (p[j][1] - p[i][1]) * (p[j][0] - p[i][0]) < point[0]))
            result = !result;
        j = i;
    }
    return result;
}
 
console.log(isInside([[1, 1], [1, 3], [3, 3], [3, 1]], [2, 2]), true);
console.log(isInside([[1, 1], [1, 3], [3, 3], [3, 1]], [4, 2]), false);
console.log(isInside([[1, 1], [4, 1], [2, 3]], [3, 2]), true);
console.log(isInside([[1, 1], [4, 1], [1, 3]], [3, 3]), false);
console.log(isInside([[2, 1], [4, 1], [5, 3], [3, 4], [1, 3]], [4, 3]), true);

@Schulzkafer · 08.06.2020, 20:16 **[ТС]**

я гуглил как-то неправильно, у меня в 7 раз больше вашего решения получилось, и то не правильно)))
пока я не разобрался, можете подсказать как вот тут доработать? (задачник выдал экстрапроверки и выдал false тут(см. снимок) :

@Iverycool · 08.06.2020, 21:10

Schulzkafer, вот так будет работать:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function isInside(p, point) {
    let result = false;
    let j = p.length - 1;
    for (let i = 0; i < p.length; i++) {
        if ((p[i][1] === point[1] && p[i][0] === point[0]) || ((p[i][1] < point[1] && p[j][1] >= point[1] || p[j][1] < point[1] && p[i][1] >= point[1]) &&
            (p[i][0] + (point[1] - p[i][1]) / (p[j][1] - p[i][1]) * (p[j][0] - p[i][0]) < point[0])))
            result = !result;
        j = i;
    }
    return result;
}
 
console.log(isInside([[1, 1], [1, 3], [3, 3], [3, 1]], [2, 2]), true);
console.log(isInside([[1, 1], [1, 3], [3, 3], [3, 1]], [4, 2]), false);
console.log(isInside([[1, 1], [4, 1], [2, 3]], [3, 2]), true);
console.log(isInside([[1, 1], [4, 1], [1, 3]], [3, 3]), false);
console.log(isInside([[2, 1], [4, 1], [5, 3], [3, 4], [1, 3]], [4, 3]), true);
console.log(isInside([[1, 1], [1, 3], [3, 3], [3, 1]], [1, 1]), true);

@Schulzkafer · 08.06.2020, 21:19 **[ТС]**

Спасибо! (вот 14е extra выдало еще false, если сможете, подправьте, пожалуйста
(хотя конечно, тут я сам уже должен это сделать, но чтоб открыть другие задания, мне нужно это решить на опред.время, поэтому быстрее с вами))

@diadiavova · 09.06.2020, 08:36

Вообще, задача довольно известная, ей даже статью в википедии посвятили
Задача о принадлежности точки многоугольнику — Википедия

Новые блоги и статьи Все статьи Все блоги /
Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .	Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .

Задача (сложность - средняя)

Решение

Решение

Решение

@Schulzkafer 82 / 50 / 2 Регистрация: 31.12.2019 Сообщений: 418
	08.06.2020, 20:16 [ТС]
	я гуглил как-то неправильно, у меня в 7 раз больше вашего решения получилось, и то не правильно))) пока я не разобрался, можете подсказать как вот тут доработать? (задачник выдал экстрапроверки и выдал false тут(см. снимок) : Миниатюры 0

@Schulzkafer 82 / 50 / 2 Регистрация: 31.12.2019 Сообщений: 418
	08.06.2020, 21:19 [ТС]
	Спасибо! (вот 14е extra выдало еще false, если сможете, подправьте, пожалуйста (хотя конечно, тут я сам уже должен это сделать, но чтоб открыть другие задания, мне нужно это решить на опред.время, поэтому быстрее с вами)) Миниатюры 0

@diadiavova 7261 / 2608 / 745 Регистрация: 11.04.2015 Сообщений: 4,155 Записей в блоге: 43
	09.06.2020, 08:36
	Сообщение было отмечено Schulzkafer как решение Решение Вообще, задача довольно известная, ей даже статью в википедии посвятили Задача о принадлежности точки многоугольнику — Википедия 1