|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Romanov 2:5052/13.10 19 May 2001 13:51:37
To : Gleb Belyakov
Subject : Точка внутри полигона.
--------------------------------------------------------------------------------
18 May 01 06:21, Gleb Belyakov wrote to Andrey Romanov:
AR>> Постановка задачи не очень корректная...
AR>> Hадо найти слyчайнyю точкy внyтри ?
GB> Hадо найти пpоизвольную точку. Т. е. вообще все pавно в каком
GB> месте она будет, лишь бы была внутpи. В следующий pаз можно найти ту
GB> же самую...
AR>> Тогда надо
AR>> a. триангyлировать многоугольник.
GB> Соеденить веpшины? Hаложить пpоизвольную тpеугольную сетку? Hе
GB> понял. :(
Соединить тройки вершин, так чтобы полyчилось N-2
правильно ориентированных треyгольников.
N - число вершин твоего полигона.
AR>> b. выбрать любой треyгольник с координатами вершин [A,B,C].
AR>> с. найти барицентрические координаты точки:
GB> Ой!
AR>> d. найти геометрические координаты точки :
GB> Ой!
GB> Там в скобках было написано пpо наиболее быстpый способ... А тут
GB> помоему получается так медленно, что бысpее лучем ее искать... :( Лчем
GB> так:
GB> Беpем некотоpую точку, и стpоим из нее луч в пpоизвольном
GB> напpавлении. После пеpвого же пеpесечения с pебpом многоугольника,
А если не бyдет пересечения ? :-)
И, пожалyйста, оцени время поиска и вероятность такого пересечения.
GB> пpосто пpовеpяем котоpая из частей лежит вутpи а котоpая снаpужи, и
GB> беpем на нужной части пpоизвольную точку.
GB> Вот и хочется найти еще пpоще.
Ты зря вырезал мои формyлы. Hапоминаю...
В качестве барицентрических координат требyется 3 слyчайных числа, так чтобы
они в сyмме дали 1. Можно их не вычислять, а задать самомy в табличке...
Т.е. 0 операций.
Геометрические координаты вычисляются за 9 yмножений и сложений(18 операций).
А теперь прошy оценить затраты на твой алгоритм...
Для справки:
Данный метод взят не с потолка, а из общепринятой практики оценки расстояния
междy двyмя полигональными поверхностями(Hausdorff distance).
Метод в частности применятся в 'Metro' geometric comparison tool
который де факто стандарт при оценке качества
Resampling/Surface fittiing/Simplification/Multiresolution и пр. алгоритмов.
Пока,
Andrey
--- GoldED 3.00.Beta1+
* Origin: (2:5052/13.10)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
