Естественные науки
Мне даны координаты n точек на плоскости. Как узнать, являются ли они вершинами n-угольника?
Спасибо.
Талап Дуйсибек
345
Это зависит от того, имеешь ли ты в виду правильный многоугольник, любой многоугольник или любой не самопересекающийся многоугольник. Если ты имеешь в виду любой многоугольник, то ты всегда можешь создать не самопересекающийся многоугольник из заданного набора точек. Найти минимальную - это пример задачи коммивояжера.
Если же ты имеешь в виду правильный многоугольник, возьми любые три точки и найди круг, проходящий через них. Если какая-либо из оставшихся точек не находится на окружности, то они не являются вершинами правильного многоугольника. В противном случае отсортируй точки по углу, который они образуют с центром круга, перебери точки в отсортированном порядке и убедись, что расстояние между каждой парой соседних точек постоянно.
Если же ты имеешь в виду правильный многоугольник, возьми любые три точки и найди круг, проходящий через них. Если какая-либо из оставшихся точек не находится на окружности, то они не являются вершинами правильного многоугольника. В противном случае отсортируй точки по углу, который они образуют с центром круга, перебери точки в отсортированном порядке и убедись, что расстояние между каждой парой соседних точек постоянно.
Наталья Кудрявская
* Коллинеарные точки не являются вершинами n -угольника... На всякий случай.
Необходимым и достаточным условием того, что р точек, заданных на плоскости, были вершинами р-угольника, может являться условие НЕ НАХОЖДЕНИЯ ЛЮБОЙ ТРОЙКИ ЭТИХ ТОЧЕК НА ОДНОЙ ПРЯМОЙ (назовём это условием "У") в случаях:
а) Если заданные точки могут образовать выпуклый р-угольник;
б) Если р= 4.
Если р больше 4 и условие "а" не соблюдается, то условие "У" будет достаточным, но не необходимым.
Например, пусть заданы 5 точек А (0;1), В (2;1), С (3;2), Е (4;1), Н (1;0). Здесь "тройки" А- В-Е и Н-В-С лежат на одной прямой, тем не менее имеем пятиугольник (не выпуклый) АВСЕН. То есть необязательно, чтобы соблюдалось условие "У".
а) Если заданные точки могут образовать выпуклый р-угольник;
б) Если р= 4.
Если р больше 4 и условие "а" не соблюдается, то условие "У" будет достаточным, но не необходимым.
Например, пусть заданы 5 точек А (0;1), В (2;1), С (3;2), Е (4;1), Н (1;0). Здесь "тройки" А- В-Е и Н-В-С лежат на одной прямой, тем не менее имеем пятиугольник (не выпуклый) АВСЕН. То есть необязательно, чтобы соблюдалось условие "У".
Asemgul Askhat
69 696
Проверить каждую тройку точек на предмет лежат ли они на одной прямой. Если ответ отрицательный, все n точек являются вершинами n-угольника.
Или вас интересует конкретно выпуклый многоугольник?
Или вас интересует конкретно выпуклый многоугольник?
Деня Соколов
89 018
Asemgul Askhat
Ваша проверка как раз для выпуклого многоугольника.
А (0;1), В (2;1), С (3;2), Е (4;1), Н (1;0). здесь А- В-Е и Н-В-С лежат на одной прямой, тем не менее имеем пятиугольник (не выпуклый) АВСЕН.
А (0;1), В (2;1), С (3;2), Е (4;1), Н (1;0). здесь А- В-Е и Н-В-С лежат на одной прямой, тем не менее имеем пятиугольник (не выпуклый) АВСЕН.
проверить, нет ли равных у.
Umm Аиша ......
56 296
вопрос невнятен
какого многоугольника?
правильного, выпуклого, звездчатого, с самопересечением?
какого многоугольника?
правильного, выпуклого, звездчатого, с самопересечением?
Ксения Тарасюк
36 668
Деня Соколов
Сомопересечения можно не опасаться. Мы же сами строим многоугольник. Вот по поводу выпуклости - да, требуется уточнение.
Я так понимаю, набор точек у тебя упорядочернный, тебя интересует проверка на самопересечения сторон?
Кажись, это стандартная задачка по вычислительной геометрии/компьютерной графике. Только я стандартный алгоритм забыл - все там пары сторон пррверяются (пары без общей вершины), или еще как...
ЗЫ. Вот такую штуку глянь
ru.wikipedia.org/wiki/Алгоритм_Бентли_—_Оттманна
Кажись, это стандартная задачка по вычислительной геометрии/компьютерной графике. Только я стандартный алгоритм забыл - все там пары сторон пррверяются (пары без общей вершины), или еще как...
ЗЫ. Вот такую штуку глянь
ru.wikipedia.org/wiki/Алгоритм_Бентли_—_Оттманна
Евгений Магарилл
34 449
Asemgul Askhat
А я так понимаю, что автора интересует то, что написано именно в вопросе. А многоугольник, по определению, может быть и выпуклым, и невыпуклым, и самопересекающимся.
Asemgul Askhat
По-моему, гораздо интереснее (и сложнее) такая постановка вопроса: "В каких случаях заданные р точек НЕ МОГУТ БЫТЬ вершинами р-угольника?"
Похожие вопросы
- Как найти угол в окружности? ? Зная координаты двух точек.
- Известны длины сторон n-угольника (n > 3). Как найти максимальную площадь?
- Из двух правильных n- угольников один вписан в другой. При каких значениях отношения длин их сторон это возможно?
- Две точки определяют прямую, три точки определяют плоскость. Почему четыре точки не определяют трехмерное пространство?
- Расстояние между двумя n-мерными объектами является m-мерным. m = n+1 - правильная ли подстановка?
- Докажите, что 9^(n+1) + 8n + 7 делится на 16 при всех натуральных n
- Как построить оси координат в n-мерном пространстве?
- Если даны три точки в координатах обычных как узнать само просто лежат ли она на одной прямой?
- Подскажите, с математической точки зрения на ПЛОСКОСТИ столько же точек сколько на ПРЯМОЙ?
- Как составить уравнение плоскости, если мы знаем 3 точки(с 3-мя координатами)?