主页
Top.Mail.Ru Yandeks.Metrika
论坛:“抢”;
当前存档: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]

如果有帮助,那么我会在最近出版的一本关于算法的书中看到该算法(是如此丰富,在R. Rivest的作者中,我已经不记得了)。 有一种算法可以找到相交的线段。 它当然适用于此(附加条件)。 IPA怎么不知道。 我在职业GIS中遇到了这个问题。 而且对我来说更容易,相应的机制已内置在GIS软件包中:)



Виктор Щербаков   (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;
下载:[xml.tar.bz2];

楼上









内存:0.59 MB
时间:0.114 c
4-353
Rumrunner
2002-01-27 04:45
2002.04.01
您好!


1-234
库尔特
2002-03-20 19:00
2002.04.01
人们帮助PLIZ! 如何让BorderStyle窗口有一个bsDialog,但是他有机会破坏???


14-304
Viktor55
2002-02-17 22:20
2002.04.01
正常使用下的电脑性能


14-286
AriokH
2002-02-17 22:00
2002.04.01
只是一个问题


6-255
瓦尔德马
2002-01-17 14:37
2002.04.01
使用套接字





南非荷兰语 阿尔巴尼亚人 阿拉伯语 亚美尼亚 阿塞拜疆 巴斯克 白俄罗斯 保加利亚语 加泰罗尼亚 简体中文 中国(繁体) 克罗地亚 捷克 丹麦语 荷兰人 英语 爱沙尼亚语 菲律宾人 芬兰 法文
加利亚西语 格鲁吉亚语 德语 希腊语 海地克里奥尔语 希伯来语 印地语 匈牙利 北日耳曼语 印度尼西亚人 爱尔兰语 意大利语 日本性玩偶 韩语 拉脱维亚 立陶宛 马其顿 马来语 马耳他语 挪威语
波斯语 波兰语 葡萄牙语 罗马尼亚 俄语 塞尔维亚 斯洛伐克 斯洛文尼亚 西班牙语 斯瓦希里 瑞典语 泰国人 土耳其 乌克兰 乌尔都语 越南人 威尔士语 意第绪语 孟加拉 波斯尼亚
宿务 世界语 古吉拉特语 豪萨语 苗族 伊博 爪哇 卡纳达语 高棉 老挝 拉丁语 毛利 马拉 蒙古人 尼泊尔 旁遮普 索马里 泰米尔人 泰卢固语 约鲁巴语
祖鲁
英文 Французский Немецкий Итальянский Португальский 俄文 Испанский