03-10-2003 20:13 Ланиста » Помогите решить задачу разными способами : )
Задача следующая.
Нужно проверить, находится ли точка внутри данного тругольника.
Рассматривается двумерное пространство, т. е. и треугольник, и точка лежат в одной плоскости. Вершины A, B, C треугольника и точка M заданы координатами. Требуется решить задачу максимальным количеством способов.
При этом сложность алгоритма решения не имеет значения.
Я уже знаю несколько решений : ) Например:
1) Очень просто определить пренадлежность точки единичному треугольнику с вершинами (0,0), (0,1) и (1,0). Поэтому мы можем найти такое преобразование (матрицу), которая переводит наш треугольник в единичный. А дальше элементарно.
2) Соединить точку со всеми вершинами и подсчитать сумму верхних углов получившихся треугольников. Если 360 - то внутри, если меньше - снаружи.
Если вы знаете другие методы решения, поделитесь ими со мной.
Заранее спасибо : )
Нужно проверить, находится ли точка внутри данного тругольника.
Рассматривается двумерное пространство, т. е. и треугольник, и точка лежат в одной плоскости. Вершины A, B, C треугольника и точка M заданы координатами. Требуется решить задачу максимальным количеством способов.
При этом сложность алгоритма решения не имеет значения.
Я уже знаю несколько решений : ) Например:
1) Очень просто определить пренадлежность точки единичному треугольнику с вершинами (0,0), (0,1) и (1,0). Поэтому мы можем найти такое преобразование (матрицу), которая переводит наш треугольник в единичный. А дальше элементарно.
2) Соединить точку со всеми вершинами и подсчитать сумму верхних углов получившихся треугольников. Если 360 - то внутри, если меньше - снаружи.
Если вы знаете другие методы решения, поделитесь ими со мной.
Заранее спасибо : )
Комментарии:
Камрад
Манни (мне кажется, он ) спрашивал (давно) что-то очень похожее, он писал программу, которая определяла, находится ли точка внутри плоского многоугольника. Спроси у него, на каком методе он остановился.
Хорошо, спрошу. Только сдается мне, с программой все проще. Закрасить весь треугольник в красный цвет, а потом проверить, какого цвета искомая точка. Если красная - внутри, другого- снаружи.
Спасибо за совет : )
Спасибо за совет : )
Камрад
Можно через уравнения прямых - сторон треугольника.
Камрад
Можно считать расстояния до вершин.
Если лирику будет позволено вставить свое неавторитетное мнение в диалог физиков, то можно нарисовать этот треугольник на координатной плоскости, поставить точку и визуально определить... 
Камрад
Ланиста
Тебе ж понятно, как через уравнения сторон, например?
Подставить точку, посмотреть знаки. Если неохота думать, что там со знаками должно получиться, взять точку, которая заведомо внутри, например, точку пересечения медиан, и проверить знаки для нее. Если у твоей совпадает - внутри, если нет - снаружи.
Тебе ж понятно, как через уравнения сторон, например?
Подставить точку, посмотреть знаки. Если неохота думать, что там со знаками должно получиться, взять точку, которая заведомо внутри, например, точку пересечения медиан, и проверить знаки для нее. Если у твоей совпадает - внутри, если нет - снаружи.
Джей
Можно считать расстояния до вершин.
подсчитаю, а дальше?
Magic Master
Этот метод мне очень нравится, но его нельзя реализовать в виде алгоритма на машине. Даже если комп нарисует картинку, он не поймет ее. Нужен обязательно человек... или отдельная программа распознавания : )
Джей
что-то смутно : ) Ты предлагаешь проверять лежит ли точка выше/ниже прямой каждой стороны? Можешь объяснить подробнее? : )
Можно считать расстояния до вершин.
подсчитаю, а дальше?
Magic Master
Этот метод мне очень нравится, но его нельзя реализовать в виде алгоритма на машине. Даже если комп нарисует картинку, он не поймет ее. Нужен обязательно человек... или отдельная программа распознавания : )
Джей
что-то смутно : ) Ты предлагаешь проверять лежит ли точка выше/ниже прямой каждой стороны? Можешь объяснить подробнее? : )
Камрад
Ланиста Ты предлагаешь проверять лежит ли точка выше/ниже прямой каждой стороны? Ну да. Каждая прямая делит плоскость на полуплоскости. Можно записать условие того, что точка внутри, в двоичном коде, если сопоставить 0 и 1 разным полуплоскостям.
Камрад
Я уже тут...
Да, я делал именно так, как сказала Джей.
Уточняю специально для Ланисты: :)
1) прямая делит плоскость на две полуплоскости. Это ты должен знать.
2) если в выражение, равное нулю согласно уравнению прямой :)
подставлять координаты точек плоскости, то точки, лежащие на прямой, будут давать ноль (это ты тоже знаешь), точки из одной полуплоскости будут давать положительный результат, из другой -- отрицательный.
3) "точка лежит внутри треугольника" равносильно тому, что она лежит в той же полуплоскости относительно прямой, проходящей через каждые две вершины, что и соответствующая третья вершина (т.е. относительно прямой АВ там же, где и С, отн. ВС там же, где и А, отн. СА там же, где и В).
4) а знаешь ли ты, как написать уравнение прямой, проходящей через две точки?
Да, я делал именно так, как сказала Джей.
Уточняю специально для Ланисты: :)
1) прямая делит плоскость на две полуплоскости. Это ты должен знать.
2) если в выражение, равное нулю согласно уравнению прямой :)
подставлять координаты точек плоскости, то точки, лежащие на прямой, будут давать ноль (это ты тоже знаешь), точки из одной полуплоскости будут давать положительный результат, из другой -- отрицательный.
3) "точка лежит внутри треугольника" равносильно тому, что она лежит в той же полуплоскости относительно прямой, проходящей через каждые две вершины, что и соответствующая третья вершина (т.е. относительно прямой АВ там же, где и С, отн. ВС там же, где и А, отн. СА там же, где и В).
4) а знаешь ли ты, как написать уравнение прямой, проходящей через две точки?
Камрад
Вот ещё правильный способ, он годится для произвольного многоугольника (и для приличной замкнутой кривой).
Провести из интересующей нас точки луч в любую сторону.
Посчитать количество точек пересечения этого луча с кривой (границей области).
Если оно нечётное, то точка лежит внутри, если чётное -- снаружи.
Провести из интересующей нас точки луч в любую сторону.
Посчитать количество точек пересечения этого луча с кривой (границей области).
Если оно нечётное, то точка лежит внутри, если чётное -- снаружи.
Манни
1) да
1) да
1) да
1) догадываюсь : )
Вот ещё правильный способ
Вот на него-то я и наткнулся, когда стал искать в инете. Только он все больше в матпакетах используется. Фактически нужно подсчитать количество пересечений прямой со сторонами, а потом исключить те пересечения, которые дает второй луч на прямой.
Спасибо большое! : )
Кстати, Джей упомянула о методе подсчета расстояний до вершин. Это что такое?
1) да
1) да
1) да
1) догадываюсь : )
Вот ещё правильный способ
Вот на него-то я и наткнулся, когда стал искать в инете. Только он все больше в матпакетах используется. Фактически нужно подсчитать количество пересечений прямой со сторонами, а потом исключить те пересечения, которые дает второй луч на прямой.
Спасибо большое! : )
Кстати, Джей упомянула о методе подсчета расстояний до вершин. Это что такое?
Камрад
Ланиста
Насчёт пересечений: имей в виду, что касание (или прохождение через вершину) луча считается за два.
Да не за что... всегда приятно выставить себя умным :)
По сумме расстояний до вершин, мне кажется, не получится. Может, сумма расстояний до сторон?
Насчёт пересечений: имей в виду, что касание (или прохождение через вершину) луча считается за два.
Да не за что... всегда приятно выставить себя умным :)
По сумме расстояний до вершин, мне кажется, не получится. Может, сумма расстояний до сторон?
Камрад
Ланиста
Кстати, Джей упомянула о методе подсчета расстояний до вершин. Это что такое?
Да ни то, ни другое, ни третье - не какие-то методы, а просто прикидываешь, как можно определить, внутри точка или вне.
Ищешь инвариант, то есть свойство, которым точки внутри обладают, а точки вне - нет.
Можно найти инварианты и с расстояниями. А можно записать уравнение прямой через эту точку и одну вершину, найти пересечение этой прямой с противоположной стороной треугольника, и проверить, лежит ли точка пересечения между вершинами.
Если тебя не интересует простота алгоритма, то этот тоже годится, хоть он и несколько неуклюжий.
Кстати, Джей упомянула о методе подсчета расстояний до вершин. Это что такое?
Да ни то, ни другое, ни третье - не какие-то методы, а просто прикидываешь, как можно определить, внутри точка или вне.
Ищешь инвариант, то есть свойство, которым точки внутри обладают, а точки вне - нет.
Можно найти инварианты и с расстояниями. А можно записать уравнение прямой через эту точку и одну вершину, найти пересечение этой прямой с противоположной стороной треугольника, и проверить, лежит ли точка пересечения между вершинами.
Если тебя не интересует простота алгоритма, то этот тоже годится, хоть он и несколько неуклюжий.
Камрад
В общем, чем в инете искать, ты сам посоображай, у тебя ж хорошо получается, я помню, ты решал и посложнее задачки. :)
Джей
Да ни то, ни другое, ни третье - не какие-то методы, а просто прикидываешь, как можно определить, внутри точка или вне.
Да я так и делаю, есть даже результаты : ) Но две головы всегда лучше : )
В общем, чем в инете искать, ты сам посоображай, у тебя ж хорошо получается, я помню, ты решал и посложнее задачки. :)
хех, может, напомнишь? Что-то я забывчивый стал : )
Да ни то, ни другое, ни третье - не какие-то методы, а просто прикидываешь, как можно определить, внутри точка или вне.
Да я так и делаю, есть даже результаты : ) Но две головы всегда лучше : )
В общем, чем в инете искать, ты сам посоображай, у тебя ж хорошо получается, я помню, ты решал и посложнее задачки. :)
хех, может, напомнишь? Что-то я забывчивый стал : )
Всем большое спасибо!
Написал огромный труд с выкладками и доказательствами на 9 методов.
Одним зачетом стало меньше : )
Написал огромный труд с выкладками и доказательствами на 9 методов.
Одним зачетом стало меньше : )
Отчисление
[Print] 1 2
Джей