Привет!
Скажите пожалуйста как решить задачу ниже:
дан n-угольник (заданы координаты его вершин, сам он лежит на плоскости). И даны координаты точки. Определить лежит ли эта точка на какой-либо из сторон многоугольника.
Спасибо!
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 7 | nor | 155 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.09.2024 22:21:32 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Пробежимся по всем сторонам многоугольника и проверим отдельно для каждой. Теперь нам необходимо научится решать задачу о принадлежности точки отрезку. Для того, чтобы точка принадлежала отрезку АВ необходимо, чтобы она принадлежала и лучу АВ и лучу ВА. Как проверить принадлежит ли точка M лучу, заданному вектором PQ, нужно чтобы вектора PQ и PM были сонаправленными, т.е. чтобы угол между ними был равен 0. Чтобы проверить, что угол между векторами равен 0, нужно воспользоваться псевдовекторным произведением (оно будет равно 0, так sin(0) = 0), но поскольку sin(180) = 0 тоже, то необходимо проверить, что скалярное произведение > 0, т.к. cos(0) > 0 (1), а cos(180) < 0 (-1).
Вместо псевдовекторного произведения можно банально посчитать полярный угол точки относительно обеих точек отрезка. Если точка лежит между ними на отрезке, углы будут иметь вид fi, fi-PI. Тогда и скалярное после этого не потребуется. Я могу и ошибаться, но в целом такое решение кажется более простым и выгодным (если оно, конечно, по каким-то причинам не является неправильным).
UPD: Не работает =(. Кто-нибудь может привести контр-пример? Оо
UPD 2: Всё работает, это глупый я забыл обработать случай, когда точка совпадает с крайней точкой отрезка.
Считать полярный угол точки — overkill + double арифметика + тригонометрические функции выполняются дольше умножений и сложений.
У вас обоих оверкилл. С belongs to AB, if d(A,B) == d(A,C) + d(C,B).
А у тебя неправильное решение — ты не сможешь сделать проверку точно.
В каком смысле? В практическом смысле, кажется, добрый дядя не всегда дает целые координаты. А если нельзя сравнивать два числа, то как-то все плохо. Если ты про контестики, то, честное слово, ни разу не падало такое.
UPD
Боря, вот четкое решение для тебя: смотрим чтобы координаы векторов от концов отрезка к заданной точке были пропорциональны, но при этом имели разные знаки. Кажется, все четко, если еще проверить равенство одному из концов.
Для == в double'ах нужен епсилон, а всегда лучше без него, чем с ним, нет?
Ну это само собой разумеется.
Тебе ни разу не попадались хорошие тесты? :)
Ну а честное простое решение проверки точки на принадлежность отрезку: псевдоскалярное произведение равно нулю и точка находится внутри bounding box'a отрезка.
Сразу видно что у тебя еще не было Ковалева)
Хорошо, согласен, приношу свои извинения.
Наводящий вопрос: а ты умеешь определять, принадлежит ли точка отрезку?
Например, по ссылке есть решение более общей задачи — нахождение положения точки относительно многоугольника. Если метод testPoint() возвращает "BOUNDARY", то точка лежит на стороне.
а еще можно проверить расстояние от точки до отрезка. пусть точка имеет координаты A = (x, y), а два конца отрезка B = (x1, y1), C = (x2, y2). тогда посчитаем два скалярных произведения BC * BA и CB * CA. если оба произведения больше либо равны нуля(это первый случай), то расстояние от точки до отрезка равно расстоянию от этой точки до прямой, проходящей через концы отрезка(сторона многоугольника), иначе расстояние равно минимуму из расстояний между точками A, B и точками A, C(это второй случай). так вот если расстояние равно нулю(а это может быть только в первом случае), то точка принадлежит отрезку(т.е. стороне), иначе нет.