Главная страница
Top.Mail.Ru    Яндекс.Метрика
Текущий архив: 2002.04.01;
Скачать: CL | DM;

Вниз

Площадь многоугольника   Найти похожие ветки 

 
Виктор Щербаков ©   (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]


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


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


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


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



Страницы: 1 вся ветка

Текущий архив: 2002.04.01;
Скачать: CL | DM;

Наверх




Память: 0.49 MB
Время: 0.012 c
14-315
ao1973
2002-02-20 15:37
2002.04.01
WIndows Ce


1-144
dolphin
2002-03-22 02:25
2002.04.01
Как определить есть ли файл на сервере.


1-223
MaXie
2002-03-20 12:50
2002.04.01
Массив объектов.


14-309
McSimm
2002-02-18 15:47
2002.04.01
Клиент для форумов. Dolphin 1.2. Новая версия.


14-311
Kozhanov
2002-02-19 13:54
2002.04.01
---|Ветка была без названия|---