Та же история. Мы не можем ничего намотать вокруг точки по этому алгоритму. Но, действительно, должны выделить случаи, когда вокруг точки намотано изначально (как в звезде с точкой по центру), и сделать вывод о принадлежности точки многоугольнику при принадлежности её всем оставшимся треугольникам.
В общем, пока никто не показал, как конкретно алгоритм может не сработать. Хотя, большие сомнения остаются, поскольку нетщательный гуглёж не находит ничего похожего.
Насчёт O(N) надо смотреть. Вроде бы не должно быть сильно больше — нам же достаточно каждый треугольник просчитать только один раз, а пустые треугольники тут же удаляются.
Вижу, что вы не поняли алгоритм. Перечитайте внимательнее. Я же про это как раз и написал. Аж два раза. Если точка лежит в треугольнике — мы этот треугольник не трогаем вообще, поскольку не знаем, принадлежит ли он (вместе с точкой) многоугольнику или нет. Но если точки там нет, то нам без разницы, уменьшаем мы площадь многоугольника или увеличиваем, удалив этот треугольник, — точка от этого не перескачет границу многоугольника и не перестанет принадлежать или не принадлежать ему.
Определять не надо. Не могу придумать варианта, где это было бы важно. Важно, чтобы проверяемая точка в любом случае не находилась на этой площади или на стороне треугольника. Иначе, пропускаем этот треугольник и переходим к следующему. Может оказаться, в конце останется четырёхугольник с точкой ровно на пересечении диагоналей - надо отследить, чтобы не зациклиться.
Я бы последовательно отсекал от многоугольника треугольники, которым точно не принадлежит проверяемая точка, сведя задачу к определению принадлежности точки последнему оставшемуся треугольнику.
Может быть. Но суть в том, что ходить туда вообще не было смысла. Разве что, для того, чтобы потом оставить комментарий, как тебя в очередной раз обманули.
Этот голос как раз не в никуда, а победителю процент добавил, даже при честном подсчёте. А я вот сознательно действительно отправил бюллетени в никуда, испортив их — так эти жулики и недействительные бюллетени украли — не было, оказывается, на моём УИК недействительных бюллетеней.
Если бы задача так просто решалась, понимаете, то армянское радио этим бы не занималось.
Мне напомнило афоризм:
Как жаль, что способность делиться осталась только у простейших.
А у меня другое предложение...
„Да мы с вами ещё так будем жить, что наши дети и внуки нам завидовать будут.“
— Виктор Степанович Черномырдин
В измерительных радиоприборах такие раньше стояли на тыльной стороне
https://www.google.ru/search?q=ртутный+счетчик+времени+наработки
А опилки спрессуем в ДСП и будем делать из неё мебель.
Та же история. Мы не можем ничего намотать вокруг точки по этому алгоритму. Но, действительно, должны выделить случаи, когда вокруг точки намотано изначально (как в звезде с точкой по центру), и сделать вывод о принадлежности точки многоугольнику при принадлежности её всем оставшимся треугольникам.
В общем, пока никто не показал, как конкретно алгоритм может не сработать. Хотя, большие сомнения остаются, поскольку нетщательный гуглёж не находит ничего похожего.
Насчёт O(N) надо смотреть. Вроде бы не должно быть сильно больше — нам же достаточно каждый треугольник просчитать только один раз, а пустые треугольники тут же удаляются.
Вижу, что вы не поняли алгоритм. Перечитайте внимательнее. Я же про это как раз и написал. Аж два раза. Если точка лежит в треугольнике — мы этот треугольник не трогаем вообще, поскольку не знаем, принадлежит ли он (вместе с точкой) многоугольнику или нет. Но если точки там нет, то нам без разницы, уменьшаем мы площадь многоугольника или увеличиваем, удалив этот треугольник, — точка от этого не перескачет границу многоугольника и не перестанет принадлежать или не принадлежать ему.
Определять не надо. Не могу придумать варианта, где это было бы важно. Важно, чтобы проверяемая точка в любом случае не находилась на этой площади или на стороне треугольника. Иначе, пропускаем этот треугольник и переходим к следующему. Может оказаться, в конце останется четырёхугольник с точкой ровно на пересечении диагоналей - надо отследить, чтобы не зациклиться.
Искать не надо. Треугольник - это любые три последовательные точки в массиве.
Я бы последовательно отсекал от многоугольника треугольники, которым точно не принадлежит проверяемая точка, сведя задачу к определению принадлежности точки последнему оставшемуся треугольнику.
Может быть. Но суть в том, что ходить туда вообще не было смысла. Разве что, для того, чтобы потом оставить комментарий, как тебя в очередной раз обманули.
Этот голос как раз не в никуда, а победителю процент добавил, даже при честном подсчёте. А я вот сознательно действительно отправил бюллетени в никуда, испортив их — так эти жулики и недействительные бюллетени украли — не было, оказывается, на моём УИК недействительных бюллетеней.
А почему нет? В списке смешных законов смотрится вполне себе.
...
64. Во Франции запрещено называть свинью Наполеоном.
65. В Великобритании размещение марки с монархом вверх тормашками приравнивается к предательству.
66. В Колорадо запрещено собирать дождевую воду всем кроме фермеров.
67. В России Гуглу и Яндексу запрещено использовать обозначение «Умное голосование» в поисковой выдаче в качестве одного из ключевых слов поиска.
Эффект кобры
«Они удавятся за 50 копеек»