Повышение точности метода

[XairOn]

Здравствуйте господа! Я пишу программу по нахождению площади заданного пользователем многоугольника. Есть 2 способа (вернее рассматриваются 2 способа, на самом деле их наверное больше). Так вот первый способ: расчет по формуле ½*(∑(Xi+Xi+1)*(Yi-Yi+1)) i принимает значения от 1 до N-1 (N - количесво вершин многоугольника) Xn = X0 вобщем не в этом суть, метод довольно хороший и точный, но есть у него один существенный недостаток: порядок обхода должен строго соблюдаться, если пользователь задал многоугольник, а потом между какими-нибудь вершинами решил добавить ещё парочку, данный метод отлетает сразу... о точном значении можно сразу забыть . Есть второй способ: отрисованный многоугольник проверяется 2-мя циклами (строки-столбцы) и если встречает не белый пиксель увеличивает счетчик на еденицу:

Код: Выделить всё

...
If GetPixel(hdc, X, Y)<>White Then s=s+1
...


Этот способ лишен недостатков первого, но имеет свои Точность в этом методе страдает. Пока рисуются прямые линии (имеется ввиду НЕ наклонные) всё хорошо, но каждая наклонная линия дает погрешность, при чем когда фигура большая и довольно сложная (много линий) погрешность получается нехилая. А вот и вопрос: как можно повысить точность данного метода

P.S. А может быть у кого-нибудь есть соображения о том, как ещё можно расчитать площадь многоугольника?

[tyomitch]

Ещё раз, какие исходные данные? Только координаты вершин? Тогда они не задают фигуру однозначно.
Значит, задано что-то ещё?

[XairOn]

Ещё раз, какие исходные данные? Только координаты вершин?

Да, только координаты вершин, НО в определённом порядке. Вобщем-то порядок вершин которые задают фигуру является ключевым для первого метода. Но он меня не очень-то интересует. Главный вопрос — это второй метод!

[tyomitch]

Ещё раз. Если у тебя есть только координаты вершин, то ты не знаешь, что за фигура имелась в виду.
Никакой метод тебе в этом случае не поможет. Особенно такой, хмм... самобытный, как твой второй.

[BV]

Никакой метод тебе в этом случае не поможет.

Это одна из задач нейронных сетей.

[XairOn]

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

Да, но если есть порядок в котором они заданы, можно однозначно определить фигуру. А что ещё нужно по-твоему? Вобщем-то проблема не в том, что бы определить фигуру, грубо говоря, пользователь сам её рисует и по MouseUp/MouseDown задает вершины. Нужно найти её площадь, и как можно точнее.

[alibek]

А почему бы не разбить фигуру на треугольники и не посчитать площади этих треугольников? Единственный момент, на который надо будет обрадить внимание -- если многоугольник не выпуклый, то надо будет вычитать "внутренние" треугольники.

[tyomitch]

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

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

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

[tyomitch]

А почему бы не разбить фигуру на треугольники и не посчитать площади этих треугольников? Единственный момент, на который надо будет обрадить внимание -- если многоугольник не выпуклый, то надо будет вычитать "внутренние" треугольники.

Зачем на треугольники, когда можно на трапеции? Тогда невыпуклые многоугольники не потребуют особой обработки.
Первый метод XairOn-а именно в этом и состоит.

[XairOn]

Насчет треугольников: метод неплохой и имеет место быть... НО опять, но... если фигура сложная (много вершин) не будет ли каждый треугольник (трапеция) добавлять погрешность?

[tyomitch]

Будет. Но точнее ты на компьютере вычислить всё равно не сможешь.
И точность всё равно будет на много порядков выше, чем при пересчёте пикселов.

[XairOn]

Да пересчет пикселей - это бред, на точность можно не расчитывать. Вот идея с треугольниками у меня давно в голове крутилась, только я вот не могу сообразить по каким критерям определять из какой вершины в какую, строить эти треугольники. Сдаётся мне: этот процесс сопровождается особо крупными дозами геммороя

[alibek]

Нет. Триангуляция давно решена и активно используется 3D-шниками. Поищи в разделе "VB и 3D" алгоритмы, там были.

[tyomitch]

Да пересчет пикселей - это бред, на точность можно не расчитывать. Вот идея с треугольниками у меня давно в голове крутилась, только я вот не могу сообразить по каким критерям определять из какой вершины в какую, строить эти треугольники. Сдаётся мне: этот процесс сопровождается особо крупными дозами геммороя

Ещё раз: твой первый метод -- это готовое, формализованное, проверенно работоспособное разбиение фигуры на трапеции.
Хочешь геморроя с треугольниками -- выбор твой.

[XairOn]

Хочешь геморроя с треугольниками -- выбор твой.

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

[tyomitch]

Хорошо. Тогда предельно конкретный вопрос:
если у тебя уже есть список вершин в порядке обхода, то что тебе мешает просто воспользоваться теми формулами?


Обоснование этого метода, если тебе интересно, есть на http://algolist.manual.ru/maths/geom/polygon/area.php

[XairOn]

2 tyomitch, мешает мне вот что: метод имеет свои недостатки, например вычисляется площадь замкнутой ломаной без самопересечений, а если вдруг самопересечения будут, что тогда делать? Кстати тут резонный вопрос, а триангуляция возможна для замкнутой ломанной с самопересечениями???

Хорошо. Тогда предельно конкретный вопрос:
если у тебя уже есть список вершин в порядке обхода, то что тебе мешает просто воспользоваться теми формулами?

Если пользователь добавил вершины и нарушил порядок обхода, метод отлетает.

[GAGArin]

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

[tyomitch]

2 tyomitch, мешает мне вот что: метод имеет свои недостатки, например вычисляется площадь замкнутой ломаной без самопересечений, а если вдруг самопересечения будут, что тогда делать? Кстати тут резонный вопрос, а триангуляция возможна для замкнутой ломанной с самопересечениями???

Вряд ли. Многоугольник, по определению, -- это замкнутая ломаная без самопересечений; значит, все алгоритмы на многоугольниках тебе не подойдут.

Например, нетривиальный вопрос -- что для такой самопересекающейся кривой будет "внутрь", и что "наружа". Что именно ты собрался триангулировать?

Хорошо. Тогда предельно конкретный вопрос:
если у тебя уже есть список вершин в порядке обхода, то что тебе мешает просто воспользоваться теми формулами?

Если пользователь добавил вершины и нарушил порядок обхода, метод отлетает.

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

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

[XairOn]

Например, нетривиальный вопрос -- что для такой самопересекающейся кривой будет "внутрь", и что "наружа". Что именно ты собрался триангулировать?

Мне вот тоже ОЧЕНЬ интересно было бы это узнать, вот например как работает FillRgn работает... порой так интересно работает... в жизни б не подумал, что так бывает )

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

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

[tyomitch]

Ты в этом почему так уверен? Ты это твёрдо знаешь и при желании сможешь доказать или это тебе так кажется просто?

Ох уж эти сказочки, ох уж эти сказочники
http://users.isnet.ru/tyomitch/Sample01.png
Отмечены вершины многоугольника. Найди его площадь.
Потом посмотри на Sample02.png и Sample03.png

[d3drm]

Ты в этом почему так уверен? Ты это твёрдо знаешь и при желании сможешь доказать или это тебе так кажется просто?

Ох уж эти сказочки, ох уж эти сказочники
http://users.isnet.ru/tyomitch/Sample01.png
Отмечены вершины многоугольника. Найди его площадь.
Потом посмотри на Sample02.png и Sample03.png

Тём, ты как бы неправ. XairOn как бы говорил и не раз, что порядок точек указан. А раз так, то как бы можно спокойно построить фигуру, причем как бы однозначно и как как бы только одну.

Если я как бы не прав, поправьте меня...

[tyomitch]

Да что ли мы на разных языках говорим?
Если порядок есть, первый метод применим без ограничений.
Если порядка нет, неприменим никакой метод.
Зачем пересчёт пикселов? зачем триангуляция? зачем столько геморроя в пустячной задаче?