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

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

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

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

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

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

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

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

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

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

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