[геометрия] площадь произвольной фигуры...
 

кто силен в математике/геометрии, подскажите. как посчитать площадь произвольной фигуры, стороны которой - отрезки прямых?
для выпуклой фигуры задача крайне простая, но нужно именно для произвольной.

задача абсолютно нерешабельная, ежели известны ток длины отрезков -- строй как хош.

ежели есть углы, то можно на треугольники порезать и их считать =))

фигура задана координатами вершин. сама себя не пересекает.
вопрос в том, по какому принципу делить на треугольники, если фигура невыпуклая?

ну вот вариант навскидку.

1. фигура, конечно, не должна себя пересекать.
2. фигура д. лежать в одном квадранте, если не так - передвинь параллельным переносом.
3. площадь фигур есть сумма площадей трапеций, составленных одной гранью фигуры, перпендикулярами на ось х и проекцией грани. надеюсь, прощадь трапеции мы считаем без проблем. :) на иллюстрации будет
S = S(abb1a1)+s(bcc1b1)-s(dcc1d1)-s(add1a1).
решение о + или - принимаем след. образом. в каждую из точек верхней грани трапеции может приходить не более двух отрезков (фигура не пересекается, в т.ч. вершинами). один из этих отрезков есть верхняя грань трапеции, другой - иная грань фигуры. определяем, попадает эта "иная" грань внутрь трапеции или нет (разностью углов, определяем углы арктангенсом, например), если попадает, значит +, если не попадает, то -.

алгоритм на практике не проверен, возможны косяки, но вроде похоже.

читаем учебник по геометрии за 9-10 класс

Ну-ка, блесни! ;)

Придумал нечто )
Варварское.
Создаем мув. Строим фигуру, заливаем ее. Берем 4 крайних координаты. И начинаем пикс за пиксом заполнять и проверять hitTest() ;
:)
Как говорится метод "в лоб".

идея смольного про трапеции меня подкупила. буду думать. придумаю - покажу.
но если у кого есть готовый алгоритм - велкам! =)

Видимо, мне сегодня везет... %)
http://www.2devochki.ru/67/15467/1.html

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

http://algolist.manual.ru/maths/geom/polygon/area.php
гы гы гы

и работает же, скатина =)

А мне больше метод с hitTest() нравица, тогда уж точно любую площадь подсчитать мона будет

а вот тут ты не прав. это ж по сути метод монте-карло, только точки накидываются упорядоченно.
минусы:
- высокие затраты ресуросов
- о-о-о-очень маленькая точность

Да нефига! Ставь 120fps и сможешь за короткий срок высчитать площадь АБСОЛЮТНО ЛЮБОЙ фигуры, в т.ч. неправильной формы и с дырками внутри

Kapaysya na www.ultrashock.com tam ya tochno vidil chtoto podobnoe

2smamyan
Говорю же, решил уже. См. линк выше

2Ion
Постой-постой, а
1) при чем тут 120fps?
2) можт накидаешь алгоритм - сделаем мини-бенчмарк? ;)

120 fps? Чтобы быстро можно было пробежать всю фигуру, можно конечно чёрёз setInterval, но эт геморно, да и 120 фпс никогда не помешают, алгоритм примерно следующий: берем клип из 1-о пикселя, определяем габариты фигуры, начинаем двигать клип слева направо, сверху вниз, по 1-й точке, каждый раз проверяя, перекрывает ли он фигуру, если да - инкрементируем счетчик площади фигуры.

1) Чем больше fps, тем меньше времени на кадр.
2) 120 фпс никогда не помешают - глупость. Если нужен быстрый отклик - есть updateAfterEvent()
3) каждый раз проверяя, перекрывает ли он фигуру - во флеш нет функции проверки перекрытия двух фигур
4) Точность подсчета - 1 кв. пиксель. А если у меня фигура 2х2 пикселя? Погрешность порядка 50-200%.
5) Если фигура 5000х5000. Скока будет считать?

Метод hitTest'ом очевидно крайне неточен. К примеру площадь, соответствующая сектору с R=10cм и углом 180 можно hitTestom и пощитать как 0... (помните как в школе учитель доказывал, мол длина полуокружности равна диаметру - из той же серии). Но если мы работаем с заведомо большими простыми фигурами... то почему бы и нет? Хотя очевидно, что пора флэш научить пользоваться интегралами )

updateAfterEvent - эт если ты делаешь setInterval, 120фпс никогда не помешают. Просто делай больше интервал между ключевыми кадрами. Функция проверки перекрытия - hitTest. Абсолютная погрешность всегда будет небольшой, достаточно малой, чтобы её невозможно было заметить. 5000х5000 - бред, покажи мне хоть одну флешку с такими размерами! А если всё же найдешь, то там этот способ использовать не нужно - у всего есть свои недостатки

Ion а толку извращаться с дикими fps и хитестами когда есть отлично работающая формула?

2Fl00r
какими интегралами? дал же 100%-но рабочую формулу без загонов, быструю и т.д.
http://algolist.manual.ru/maths/geom/polygon/area.php
Кто найдет ситуевину, когда она не работает?

2Ion
1) 120fps - повторяться не буду.
2) hitTest - читай хелп ВНИМАТЕЛЬНО! hitTest считает перекрытие точки с фигурой или ограничивающих прямоугольников
3) Я ж привел пример - погрешность зависит от выбранных масштабов, что очень не есть гут.
4) 5000х5000 - номальный размер мувика. Делаю CAD-систему.
5) Нужно - не нужно. Была речь об универсальном методе. Но ВСЕ РАВНО предложенный в ссылке метод сделает твой хитТестный в 100% случаев по точности/времени. Ибо он аналитический.

Почти как в песне из "Врунгеля":
Танкисто, наступанто, агрессивно... =)))

Повторяю для кандидатов наук: если те над определить площадь надписи, написанной рукописным шрифтом, как ты туда свою формулу впихнешь?! А hitTest проглотит

Для любителей "хитТста": если координаты вершин не целые ( напр 20.24 ) то твой метод полный бред выдаст.

Почитай первый пост, профессор

Ты сам то понял что сказал? Каким образом длина полуокружности может быть равна длине диаметра? Диаметр - есть хорда, а хорда всегда короче дуги (не обязательно окружности), которую он отсекает.

А вообще вы зря на хит тест гоните. Главное придумать как его отмасштабировать. То есть если 2*2 пикселя, то ерунда конечно, но если хотя бы 100*100 и больше, то вполне прокатит. Только опять таки же масштабировать. Чтобы не кидать 25000000 точек в фигуру 5000*5000.

А вообще тут хорошо катит пример с вычислением числа ПИ до 16 знаков: Брали двумерны (х,у) генератор случайных чисел (от 0 до 1). Кидали им точки. то есть все точки попадают в квадрат размера 1*1. В квадрат вписана окружность. Так вот отношение всех точек, к точкам попавщим в окружность есть отношение площадей квадрата к площади окружности. Если память не изменяет, нужное отношение было достигнуто при 100000 бросаний!

Так вот взять нашу фигуру, описать её прямоугольником и кидать точки только в него генератором случ чиселотношение площади прямоугольника к площади площади фигуры есть отношение всех точек, к точкам с хиттест равным true!

ну давай, умник, устроим мини-бенчмарк, я уже предлагал.
как раз будем пи считать и посмотрим у кого точность\время выше.

попробуй обойтись без формулы пифагора... с^2=a^2+b^2 которой пользуются 5-ти класники... :) это я не со зла... просто хочу сказать что формула та лучше, где вычисления простейшие и их мало...

4eLLlblpckuu_KoT,
))... Если тебе этого не доказывали - значит это тебя этому не учили. И приводить здесь докозательства я не собираюсь. Это знаешь, как апории Зенона - вроде очевидный обман, но ведь обратного то не докажешь! Так и доказывается, что длина полуокружности равна диаметру, при чемдостаточно математически )).
Метод хитТеста нельзя не брать во внимания, но надо отдавать себе отчет, что это тоже, что считать длину окружности веревочкой. Помню интегралы считали по клеточкам - вот это и есть хитТест. Очень просто, приминим ко многим простым случаям, но при этом от сложности фигуры растет погрешность.

а бенчмарк это что? пари?

типа гонки, на скорость=)

вот как раз погрешность хиттеста с увеличением размера фигуры уменьшается, т.к. погрешность возможна только на краях, а с увеличением площади фигуры, относительная площадь краев уменьшается!

да, все верно. но мы же хотим найти универсальное решение. не только для больших и малых )).

Ion твой вариант работает при совпадений нескольких если.
а вообще зачастую может потреботваться использовать этот алгоритм в мувике где есть простая анимация, и ты советуешь вместо 10 кадров анимации делать 120? и тд.

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

и что же эт за несколько "если"?

А вот я докажу, причём тоже достаточно математически:
Если речь идёт об окружности, которая опирается на данный диаметр, то:
1) дина окружности: 2Пr, длина полуокружности Пr!!!
2) Длина диаметра 2r.
3) П=3.1416>2 => Пr>2r. Ч.Т.Д.

Значит либо речь идёт об окружности не опирающейся на данный диаметр, либо это новый вид геометрии типа Евклидовых пространств... Называется "Геометрия FLOOr'a"! :D

вот жеж сырбор подняли.
всё мега понятно.
в случае D-manа он нашёл своё решение. оно в разы лучше хиттеста.
и спорить не о чём.

другое дело, что еслибы дакабы задача стояла просчитать площать мегаофигительной фигуры типа текста, тогда да. тогда без хиттеста не обойтись, ток господа академики, на коё х*р нужна площадь текста?
есть реальные примеры?

необязательно же делать что - то с целью конкретного применения