Как найти, находится ли точка внутри многоугольника с помощью Racket

Question

Я работаю над проектом, который, учитывая определенную координату широты и долготы, выводит окрестности, в которых находится точка. У меня есть координаты широты и долготы, которые делают до границ нескольких кварталов в пределах города. Я должен прочитать данные о соседстве из файла, а также прочитать контрольные точки из файла. Я использую язык программирования Racket.

До сих пор я мог читать файлы и создавать список точек для каждого района, и теперь я застрял. Я хотел создать многоугольник для каждой окрестности, а затем метод, который проверяет, находится ли точка внутри этого многоугольника. Однако я не могу понять, как это сделать с помощью Racket.

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

Answer 1

На данный момент я не буду публиковать код, потому что я не хочу решать домашнюю работу/задание. Тем не менее, я отправлю некоторые подсказки.

Посмотрите на следующую картину:

Как мы можем знать, что C между краями OA и OB и D является снаружи? Это просто: мы сравниваем некоторые углы: если угол между OC и OA меньше, чем угол между OB и OA, тогда C явно приближается к OA, чем OB is.

Теперь, как мы получаем угол, зная только некоторые векторы? Мы можем использовать косинус, который является монотонным: он уменьшается с увеличением аргумента. Таким образом, косинус угла между OC и OA больше, чем косинус угла между OB и OA, что в свою очередь больше, чем косинус угла между OD и OA.

Следующий шаг - выяснить, как вычислить косинус. Продукт векторной точки помогает: это значение является косинусом угла больше, чем произведение длины операнда. То есть:

cos(OC; OA) = dotproduct(OC; OA)/(length(OA) * length(OC)) 

DotProduct в 2D прост:

dotproduct(OC; OA) = (C.x - O.x) * (A.x - O.x) + (C.x - O.x) * (A.x - O.x) 

Объединяя все выше, вы должны иметь простой тест, чтобы проверить, является ли ваша точка находится в той же ситуации, как C или D : ближе к одному краю, чем предыдущий край или нет.

Теперь вам нужно будет повторить это для каждого края многоугольника, и все готово. Вы можете сделать это с помощью fold, если тест является предикатом.

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

Вторая нота: На рисунке, что произойдет, если D или C или оба ниже OA линии?Подумайте об этом и проверьте, не означает ли это дополнительные изменения вышеописанного метода fold.

Последнее примечание: Через несколько недель я отправлю полный код для этого, предполагая, что задание закончено. Кроме того, в то время я отвечу на вопрос в вышеупомянутой записке.