Об одном подходе к другим подходам Альтернативная реальность, данная в ощущениях

Просмотры

Рубрики

Последние комментарии

Рейтинг блогов

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

    В процессе разработки одного проекта на Java понадобилось мне посчитать площадь произвольного многоугольника (полигона) с криволинейными границами. Как оказалось, несмотря на наличие довольно мощной библиотеки java.awt.geom для работы с фигурами и областями (Shape и Area), стандартных средств для вычисления площади фигуры или области в JDK в наличии нет.

    Поиски готовых решений ни к чему не привели, кроме нескольких реализаций простых алгоритмов вычисления площади кусочно-линейных полигонов, а хочется максимально точного решения. Что нам стоит дом построить? Да ничего, собственно.

    Итак, что мы знаем о фигурах в Java? Это специальные классы, реализующие интерфейс Shape. Помимо всего прочего, любая фигура, в том числе область (Area) реализует функцию построения итератора пути (PathIterator). По сути, это простое перечисление последовательности ребер по координатам, чего нам вполне достаточно для решения задачи. В итераторе существует три типа ребер - линейные (отрезок), квадратичные (кривая Безье второго порядка) и кубические (кривая Безье третьего порядка). Подробнее принципы и методе работы с фигурами и кривыми описаны в документации.

    Поскольку ограничивающая кривая замкнута, площадь можно найти интегрированием по контуру по формуле Грина:

    Общая площадь равна сумме интегралов А(k) , которые вычисляются в зависимости от типа кривой на данном участке:

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

    Исходник программы на Java, вычисляющий площадь произвольного многоугольника, созданного в виде области Area.

    (Arbitrary polygonal area calculation in Java using Area class)

    AreaCalc.java

    Запись создана: Вторник, 16 сентября 2008 в 2:59 и находится в рубриках Полезные вещи.

3 комментария на “Площадь многоугольника””

  1. Хорошая заметка :-)
    Единственный момент - не стоит грешить на разработчиков JDK, пытаясь найти в java.awt.geom.* алгоритмы вычисления площади, поскольку AWT явно заявлена как display-oriented. Хотя могли бы, да.
    Кстати, ради интереса решил поgoogлить и одна из первых ссылок привела на оригинальное (индусское) решение (речь идет о полигоне, но всё-таки):
    “You could probably call getBounds() on the Polygon, then iterate through all the pixels in that bounding Rectangle… calling Polygon.contains() for each pixel.
    Counting the pixels that are inside the polygon.
    That would be the simplest approach, taking a lot of the work from you.”

    Эх, люблю индусов, чёрт побери :-)

  2. Аватарки шикарные, я - кружок с косичками, ии-хаа :-)
    Вообще, конечно, графика уже давно не мой конек. А жаль.

  3. Ну оно, конечно, простое решение, тыкать точками :) Кстати, тоже натыкался на него.

    Помнится, где-то я читал, кажется Ньютон доказывал такой способ вычисления площади абсолютно произвольной фигуры - начертить контур на бумаге, вырезать и взвесить, а потом, зная плотность бумаги и толщину, вычислить площадь =)))

    Аватарки да, генерятся сами :)

Оставить комментарий