Форум: "Потрепаться";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.04.01;
Скачать: [xml.tar.bz2];




Вниз

Площадь многоугольника 


Виктор Щербаков   (2002-02-19 09:40) [0]

Нужен алгоритм вычисления площади самопересекающегося многоугольника. В инете пока ничего путного не нашел (может искал плохо :)

На самом деле алгоритм-то я придумал, но ведь эта задача уже давно решена и решение оптимизировано. Потому и спрашиваю.



MrBeer   (2002-02-19 09:57) [1]

tolko predlozhenie - sdelatj meshing i potom u otdelnih treugolnikov vichisljatj.



Виктор Щербаков   (2002-02-19 10:09) [2]

Это понятно:
либо на треугольники, либо на несамопересекающиеся многоугольники. А потом складывать площади.

Тогда может кто подскажет алгоритм триангуляции для самопересекающихся многоугольников?



Вячеслав   (2002-02-19 10:43) [3]

Я, не могу утверждать на 100%, но самопересекающиеся многоугольники , с прикладной точки зрения некорректны. Существует огромное количество программ, которые устраняют, или находят места самопересечения. А для нахождения площади многоугольника без самопересечений, не обязательно выполнять триангуляцию, для этого есть геодезические формулы. Я собственно предлагаю разбивать на несамопересекающиеся, а затем рассчитывать площади.
PS Я думаю, что твой поиск закончился неудачей именно из-за того, что самоперересекающиеся многоугольники считают некорректными.



Виктор Щербаков   (2002-02-19 10:56) [4]


> А для нахождения площади многоугольника без самопересечений,
> не обязательно выполнять триангуляцию, для этого есть геодезические
> формулы.


Площадь несамопересекающегося многоугольника найти действительно просто. Любой поисковик вываливает с десяток ссылок на то, как это делается.


> Я собственно предлагаю разбивать на несамопересекающиеся.


Вот мне и нужен алгоритм разбивания.


> Я думаю, что твой поиск закончился неудачей именно из-за того, > что самоперересекающиеся многоугольники считают некорректными.


Функция API Polygon - может рисовать самопересекающиеся многоугольники. Причем с 2-мя разными режимами заполнения внутренних областей. Значит может и разбивать их на несамопересекающиеся. Вопрос в том, как она это делает?



Вячеслав   (2002-02-19 12:43) [5]

Если это поможет, то алгоритм я видел в недавно изданной книге по алгоритмаи(такая толстая и среди авторов Р.Ривест, болше не помню). Там есть алгоритм поиска пересекающихся отрезков. Он наверняка применим и здесь(с дополнительными условиями). Как это делает АПИ-не знаю. Я с этой проблемой сталкивюсь по роду занятий-ГИС. И мне легче, в пакетах ГИС встроены соответствующие механизмы :)



Виктор Щербаков   (2002-02-19 13:48) [6]

Основная проблема не в поиске пересекающихся отрезков, а в нумерации точек получившихся многоугольников.
Т.е. как из множества точек вершин исходного многоугольника и точек пересечения получить последовательности точек несамопересекающихся многоугольников.



Вячеслав   (2002-02-19 14:24) [7]

Да, но для этого надо найти точки пересечения?



Виктор Щербаков   (2002-02-19 14:37) [8]

Надо.
Для каждой пары отрезков решается задача о пересечении 2-х прямых. Если точка пересечения есть, то определяется, принадлежит ли она прямоугольникам, стороны которых параллельны осям координат, а диагоналями являются рассматриваемые отрезки.
Смежные стороны многоугольника на пересечения не проверяются.

Так что здесь всё достаточно просто.



handra   (2002-02-20 10:58) [9]

Один из способов - метод Монте-Карло, а принадлежность точки многоугольнику (в т.ч. и самопересекающемуся) уже здесь обсуждалась.



Виктор Щербаков   (2002-02-20 11:19) [10]


> Один из способов - метод Монте-Карло


Согласен, но он приближенный, а хотелось бы точно. Приберегу его на крайний случай, если по другому не получится.


> а принадлежность точки многоугольнику (в т.ч. и самопересекающемуся)
> уже здесь обсуждалась.


Чего же тут обсуждать то :) Вот, например, в мат. энциклопедии написано: сроим из интересуемой точки произвольный луч и считаем кол-во пересечений со сторонами многоугольника. Если оно четное, то точка внутри, нечетное - снаружи.




Форум: "Потрепаться";
Поиск по всему сайту: delphimaster.net;
Текущий архив: 2002.04.01;
Скачать: [xml.tar.bz2];




Наверх





Память: 0.74 MB
Время: 0.017 c
1-185             JibSkeart             2002-03-17 16:28  2002.04.01  
Как Узнать программно и можноли что у Файла досовская (Рус) кодировка ??


1-233             Ольга                 2002-03-18 16:24  2002.04.01  
Outlook


1-201             tovSuhov              2002-03-20 10:25  2002.04.01  
Вот еще такой вопрос...


1-91              Yu                    2002-03-21 12:06  2002.04.01  
Что за ошибка?


1-247             AlexanderS            2002-03-20 23:31  2002.04.01  
Как получить значение переменной окружения TEMP?