Ответ 1

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

Я считаю девять разных случаев (на рисунке ниже показано число вершин треугольника внутри круга и количество ребер треугольника, которые пересекаются или содержатся в круге):

(Тем не менее, этот вид перечисления геометрических случаев хорошо известен как сложный, и это меня не удивило бы, если бы я пропустил один или два!)

Итак, подход таков:

• Определите для каждой вершины треугольника, если она находится внутри круга. Я собираюсь предположить, что вы знаете, как это сделать.

• Определите для каждого края треугольника, если он пересекает круг. (Я написал один метод здесь или посмотрю любую книгу вычислительной геометрии.) Вам нужно будет вычислить точку или точки пересечения (если есть ) для использования на шаге 4.

• Определите, какой из девяти случаев у вас есть.

• Вычислить площадь пересечения. Случаи 1, 2 и 9 легки. В оставшихся шести случаях я нарисовал пунктирные линии, чтобы показать, как разделить область пересечения на треугольники и круговые сегменты на основе исходных вершин треугольник и точки пересечения, которые вы вычислили на шаге 2.

Этот алгоритм будет довольно деликатным и подвержен ошибкам, которые затрагивают только один из случаев, поэтому убедитесь, что у вас есть тестовые примеры, которые охватывают все девять случаев (и я предлагаю также переставлять вершины тестовых треугольников). Обратите особое внимание на случаи, когда одна из вершин треугольника находится на краю круга.

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

Ответ 2

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

Как найти область многоугольника

Посмотрим на случай треугольника, потому что там появляется вся необходимая логика. Предположим, что мы имеем треугольник с вершинами (x1, y1), (x2, y2) и (x3, y3) при движении вокруг треугольника против часовой стрелки, как показано на следующем рисунке:

Затем вы можете вычислить область по формуле

A = (x1 y2 + x2 y3 + x3 y1 - x2y1-x3 y2 - x1y3)/2.

Чтобы понять, почему эта формула работает, пусть ее переупорядочить так, чтобы она находилась в форме

A = (x1 y2 - x2 y1)/2 + (x2 y3 - x3 y2)/2 + (x3 y1 - x1y3)/2.

Теперь первый член - это следующая область, которая в нашем случае положительна:

Если не ясно, что область зеленой области действительно (x1 y2 - x2 y1)/2, тогда прочитайте this.

Второй член - это область, которая снова положительна:

И третья область показана на следующем рисунке. На этот раз область отрицательная

Добавив эти три, мы получим следующее изображение

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

То, что я сказал выше, было интуитивным объяснением того, почему формула области была правильной. Более строгим объяснением было бы заметить, что при вычислении площади от края площадь, которую мы получаем, является той же областью, которую мы получили бы от интегрирования r ^ 2dθ/2, поэтому мы эффективно интегрируем r ^ 2dθ/2 вокруг границы многоугольника и теоремой Стокса, это дает тот же результат, что и интегрирование rdrdθ над областью, ограниченной полигоном. Поскольку интегрирование rdrdθ над областью, ограниченной полигоном, дает площадь, мы заключаем, что наша процедура должна правильно дать область.

Площадь пересечения круга с многоугольником

Теперь обсудим, как найти область пересечения круга радиуса R с полигоном, как показано на следующем рисунке:

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

Наша первая область будет выглядеть так:

Вторая область будет выглядеть так:

И третья область будет

Опять же, первые две области положительны в нашем случае, а третья - отрицательная. Надеемся, что аннулирование будет работать так, что площадь сети действительно интересует нас. Давайте посмотрим.

Действительно, сумма площадей будет областью, в которой нас интересует.

Опять же, мы можем дать более точное объяснение, почему это работает. Пусть я - область, определяемая пересечением, и пусть P - многоугольник. Тогда из предыдущего обсуждения мы знаем, что мы хотим вычислить интеграл от r ^ 2dθ/2 вокруг границы I. Однако это трудно сделать, потому что для этого требуется найти пересечение.

Вместо этого мы сделали интеграл по многоугольнику. Мы интегрировали max (r, R) ^ 2 dθ/2 по границе многоугольника. Чтобы понять, почему это дает правильный ответ, определим функцию π, которая принимает точку в полярных координатах (r, θ) до точки (max (r, R), θ). Не следует путать со ссылкой на координатные функции π (r) = max (r, R) и π (θ) = θ. Тогда мы сделали интеграцию π (r) ^ 2 dθ/2 по границе многоугольника.

С другой стороны, поскольку π (θ) = θ, это то же самое, что интегрирование π (r) ^ 2 dπ (θ)/2 по границе многоугольника.

Теперь, изменив переменную, получим тот же ответ, если бы мы интегрировали r ^ 2 dθ/2 по границе π (P), где π (P) - образ P под π.

Снова воспользовавшись теоремой Стокса, мы знаем, что интегрирование r ^ 2 dθ/2 по границе π (P) дает площадь π (P). Другими словами, он дает тот же ответ, что и интегрирование dxdy по π (P).

Снова заменив переменную, мы знаем, что интегрирование dxdy над π (P) совпадает с интегрированием Jdxdy над P, где J - якобиан π.

Теперь мы можем разбить интеграл от Jdxdy на две области: часть в круге и часть вне круга. Теперь π оставляет точки в окружности, так что J = 1, поэтому вклад этой части P является площадью части P, лежащей в круге, т.е. площади пересечения. Вторая область - это область вне круга. Там J = 0, так как π сворачивает эту часть вниз до границы круга.

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

Теперь, когда мы относительно уверены, что знаем концептуально, как найти область, поговорим более конкретно о том, как вычислить вклад из одного сегмента. Давайте начнем с рассмотрения сегмента в так называемой "стандартной геометрии". Это показано ниже.

В стандартной геометрии край идет горизонтально слева направо. Он описывается тремя числами: xi, x-координатой, где начинается край, xf, координатой x, где заканчивается ребро, и y, y-координатой ребра.

Теперь мы видим, что если | y | < R, как и на рисунке, то край будет пересекать круг в точках (-xint, y) и (xint, y), где xint = (R ^ 2-y ^ 2) ^ (1/2). Затем площадь, которую нам нужно вычислить, разбивается на три части, обозначенные на рисунке. Чтобы получить области областей 1 и 3, мы можем использовать arctan для получения углов различных точек, а затем приравнять область к R ^ 2 Δθ/2. Так, например, мы бы установили θi = atan2 (y, xi) и θl = atan2 (y, -xint). Тогда площадь области одна равна R ^ 2 (θl-θi)/2. Мы можем также получить область области 3.

Площадь области 2 - это только площадь треугольника. Однако мы должны быть осторожны в отношении знака. Мы хотим, чтобы показанная область была положительной, поэтому мы скажем, что область - (xint - (-xint)) y/2.

Еще одна вещь, которую следует иметь в виду, состоит в том, что в общем случае xi не должен быть меньше, чем -xint, а xf не должен быть больше xint.

Другим рассмотренным случаем является | y | > R. Этот случай проще, потому что есть только одна часть, которая похожа на область 1 на рисунке.

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

Но это просто простая смена координат. Для некоторых с начальной вершиной vi и конечной вершиной vf новый x единичный вектор будет единичным вектором, указывающим от vi до vf. Тогда xi - это просто смещение vi из центра круга, пунктированного в x, а xf - просто xi плюс расстояние между vi и vf. Между тем y задается клиновым произведением x со смещением vi из центра круга.

Код

Это завершает описание алгоритма, теперь настало время написать некоторый код. Я буду использовать java.

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

public class Circle {

    final Point2D center;
    final double radius;

    public Circle(double x, double y, double radius) {
        center = new Point2D.Double(x, y);
        this.radius = radius;
    }

    public Circle(Point2D.Double center, double radius) {
        this(center.getX(), center.getY(), radius);
    }

    public Point2D getCenter() {
        return new Point2D.Double(getCenterX(), getCenterY());
    }

    public double getCenterX() {
        return center.getX();
    }

    public double getCenterY() {
        return center.getY();
    }

    public double getRadius() {
        return radius;
    }

}

Для полигонов я буду использовать класс java Shape. Shape имеют PathIterator, который я могу использовать для итерации по краям многоугольника.

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

Итак, у меня есть общий класс, который вычисляет некоторое свойство класса T о нашем пересечении круга многоугольника.

public abstract class CircleShapeIntersectionFinder<T> {

Он имеет три статических метода, которые просто помогают вычислять геометрию:

private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
    return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
}

private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
    return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
}

static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
    return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
}

Есть два поля экземпляра, a Circle, который просто хранит копию круга, и currentSquareRadius, который хранит копию квадратного радиуса. Это может показаться странным, но класс, который я использую, действительно оборудован, чтобы найти области целого набора пересечений круг-полигон. Вот почему я имею в виду один из кругов как "текущий".

private Circle currentCircle;
private double currentSquareRadius;

Далее идет метод вычисления того, что мы хотим вычислить:

public final T computeValue(Circle circle, Shape shape) {
    initialize();
    processCircleShape(circle, shape);
    return getValue();
}

initialize() и getValue() являются абстрактными. initialize() установит переменную, которая будет поддерживать общую площадь до нуля, а getValue() просто вернет область. Определение processCircleShape имеет вид

private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
    initializeForNewCirclePrivate(circle);
    if (cellBoundaryPolygon == null) {
        return;
    }
    PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
    double[] firstVertex = new double[2];
    double[] oldVertex = new double[2];
    double[] newVertex = new double[2];
    int segmentType = boundaryPathIterator.currentSegment(firstVertex);
    if (segmentType != PathIterator.SEG_MOVETO) {
        throw new AssertionError();
    }
    System.arraycopy(firstVertex, 0, newVertex, 0, 2);
    boundaryPathIterator.next();
    System.arraycopy(newVertex, 0, oldVertex, 0, 2);
    segmentType = boundaryPathIterator.currentSegment(newVertex);
    while (segmentType != PathIterator.SEG_CLOSE) {
        processSegment(oldVertex, newVertex);
        boundaryPathIterator.next();
        System.arraycopy(newVertex, 0, oldVertex, 0, 2);
        segmentType = boundaryPathIterator.currentSegment(newVertex);
    }
    processSegment(newVertex, firstVertex);
}

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

private void initializeForNewCirclePrivate(Circle circle) {
    currentCircle = circle;
    currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
    initializeForNewCircle(circle);
}

initializeForNewCircle является абстрактным, и одна реализация будет заключаться в том, чтобы он сохранял радиус кругов, чтобы избежать необходимости делать квадратные корни. В любом случае вернитесь к processCircleShape. После вызова initializeForNewCirclePrivate мы проверяем, является ли многоугольник null (который я интерпретирую как пустой многоугольник), и мы возвращаемся, если это null. В этом случае наша вычисленная область будет равна нулю. Если многоугольник не null, то мы получаем PathIterator многоугольника. Аргумент метода getPathIterator, который я называю, является аффинным преобразованием, которое может быть применено к пути. Я не хочу применять его, поэтому я просто передаю null.

Далее я объявляю double[], который будет отслеживать вершины. Я должен помнить первую вершину, потому что PathIterator дает мне только каждую вершину один раз, поэтому мне нужно вернуться после того, как она дала мне последнюю вершину и сформировать ребро с этой последней вершиной и первой вершиной.

Метод currentSegment на следующей строке помещает следующую вершину в свой аргумент. Он возвращает код, который сообщает вам, когда он находится вне вершин. Вот почему контрольное выражение для моего цикла while - это то, что оно есть.

Большая часть остальной части кода этого метода является неинтересной логикой, связанной с итерацией по вершинам. Важно то, что один раз за итерацию цикла while я вызываю processSegment, а затем снова вызываю processSegment в конце метода для обработки ребра, соединяющего последнюю вершину с первой вершиной.

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

private void processSegment(double[] initialVertex, double[] finalVertex) {
    double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
    if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
        return;
    }
    double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
    double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
    final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
    final double rightX = leftX + segmentLength;
    final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
    processSegmentStandardGeometry(leftX, rightX, y);
}

В этом методе я реализую шаги для преобразования ребра в стандартную геометрию, как описано выше. Сначала я вычисляю segmentDisplacement, смещение от начальной вершины до конечной вершины. Это определяет ось x стандартной геометрии. Я делаю раннее возвращение, если это смещение равно нулю.

Затем я вычисляю длину перемещения, потому что это необходимо для получения x-единичного вектора. Как только у меня есть эта информация, я вычисляю смещение от центра круга к начальной вершине. Точечный продукт этого с segmentDisplacement дает мне leftX, который я называл xi. Тогда rightX, который я называл xf, просто leftX + segmentLength. Наконец, я делаю клин-продукт, чтобы получить y, как описано выше.

Теперь, когда я превратил проблему в стандартную геометрию, с ней будет легко справиться. Это делает метод processSegmentStandardGeometry. Посмотрите на код

private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
    if (y * y > getCurrentSquareRadius()) {
        processNonIntersectingRegion(leftX, rightX, y);
    } else {
        final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
        if (leftX < -intersectionX) {
            final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
            processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
        }
        if (intersectionX < rightX) {
            final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
            processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
        }
        final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
        final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
        final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
        processIntersectingRegion(middleRegionLength, y);
    }
}

Первый if выделяет случаи, когда y достаточно мало, чтобы край мог пересекать круг. Если y велико, и нет возможности пересечения, я вызываю метод для обработки этого случая. В противном случае я обрабатываю случай, когда пересечение возможно.

Если пересечение возможно, я вычисляю координату x пересечения, intersectionX, и я разделяю край на три части, которые соответствуют областям 1, 2 и 3 стандартного геометрического рисунка выше. Сначала я обрабатываю область 1.

Чтобы обрабатывать область 1, я проверяю, действительно ли leftX меньше -intersectionX, иначе бы не было области 1. Если есть область 1, тогда мне нужно знать, когда она закончится. Он заканчивается как минимум rightX и -intersectionX. После того, как я нашел эти координаты x, я занимаюсь этой областью непересечения.

Я делаю аналогичную вещь для обработки области 3.

Для области 2, я должен сделать некоторую логику, чтобы проверить, что leftX и rightX действительно скобят некоторую область между -intersectionX и intersectionX. После нахождения области мне нужна длина области и y, поэтому я передаю эти два числа абстрактному методу, который обрабатывает область 2.

Теперь посмотрим на код для processNonIntersectingRegion

private void processNonIntersectingRegion(double leftX, double rightX, double y) {
    final double initialTheta = Math.atan2(y, leftX);
    final double finalTheta = Math.atan2(y, rightX);
    double deltaTheta = finalTheta - initialTheta;
    if (deltaTheta < -Math.PI) {
        deltaTheta += 2 * Math.PI;
    } else if (deltaTheta > Math.PI) {
        deltaTheta -= 2 * Math.PI;
    }
    processNonIntersectingRegion(deltaTheta);
}

Я просто использую atan2 для вычисления разности углов между leftX и rightX. Затем я добавляю код, чтобы справиться с разрывом в atan2, но это, вероятно, не нужно, потому что разрыв происходит либо на 180 градусов, либо на 0 градусов. Затем я передаю разницу в углу на абстрактный метод. Наконец, у нас есть только абстрактные методы и геттеры:

    protected abstract void initialize();

    protected abstract void initializeForNewCircle(Circle circle);

    protected abstract void processNonIntersectingRegion(double deltaTheta);

    protected abstract void processIntersectingRegion(double length, double y);

    protected abstract T getValue();

    protected final Circle getCurrentCircle() {
        return currentCircle;
    }

    protected final double getCurrentSquareRadius() {
        return currentSquareRadius;
    }

}

Теперь посмотрим на расширяющийся класс, CircleAreaFinder

public class CircleAreaFinder extends CircleShapeIntersectionFinder<Double> {

public static double findAreaOfCircle(Circle circle, Shape shape) {
    CircleAreaFinder circleAreaFinder = new CircleAreaFinder();
    return circleAreaFinder.computeValue(circle, shape);
}

double area;

@Override
protected void initialize() {
    area = 0;
}

@Override
protected void processNonIntersectingRegion(double deltaTheta) {
    area += getCurrentSquareRadius() * deltaTheta / 2;
}

@Override
protected void processIntersectingRegion(double length, double y) {
    area -= length * y / 2;
}

@Override
protected Double getValue() {
    return area;
}

@Override
protected void initializeForNewCircle(Circle circle) {

}

}

У него есть поле area для отслеживания области. initialize устанавливает область в ноль, как и ожидалось. Когда мы обрабатываем непересекающееся ребро, мы увеличиваем площадь на R ^ 2 Δθ/2, как мы заключили, мы должны выше. Для пересекающегося края мы уменьшаем площадь на y*length/2. Это было так, что отрицательные значения для y соответствуют положительным областям, поскольку мы решили, что они должны.

Теперь аккуратная вещь, если мы хотим отслеживать периметр, нам не нужно делать гораздо больше работы. Я определил класс AreaPerimeter:

public class AreaPerimeter {

    final double area;
    final double perimeter;

    public AreaPerimeter(double area, double perimeter) {
        this.area = area;
        this.perimeter = perimeter;
    }

    public double getArea() {
        return area;
    }

    public double getPerimeter() {
        return perimeter;
    }

}

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

public class CircleAreaPerimeterFinder extends CircleShapeIntersectionFinder<AreaPerimeter> {

    public static AreaPerimeter findAreaPerimeterOfCircle(Circle circle, Shape shape) {
        CircleAreaPerimeterFinder circleAreaPerimeterFinder = new CircleAreaPerimeterFinder();
        return circleAreaPerimeterFinder.computeValue(circle, shape);
    }

    double perimeter;
    double radius;
    CircleAreaFinder circleAreaFinder;

    @Override
    protected void initialize() {
        perimeter = 0;
        circleAreaFinder = new CircleAreaFinder();
    }

    @Override
    protected void initializeForNewCircle(Circle circle) {
        radius = Math.sqrt(getCurrentSquareRadius());
    }

    @Override
    protected void processNonIntersectingRegion(double deltaTheta) {
        perimeter += deltaTheta * radius;
        circleAreaFinder.processNonIntersectingRegion(deltaTheta);
    }

    @Override
    protected void processIntersectingRegion(double length, double y) {
        perimeter += Math.abs(length);
        circleAreaFinder.processIntersectingRegion(length, y);
    }

    @Override
    protected AreaPerimeter getValue() {
        return new AreaPerimeter(circleAreaFinder.getValue(), perimeter);
    }

}

У нас есть переменная perimeter для отслеживания периметра, мы помним значение radius, чтобы избежать многократного вызова Math.sqrt, и мы делегируем вычисление области нашему CircleAreaFinder, Мы можем видеть, что формулы для периметра легки.

Для справки здесь приведен полный код CircleShapeIntersectionFinder

private static double[] displacment2D(final double[] initialPoint, final double[] finalPoint) {
        return new double[]{finalPoint[0] - initialPoint[0], finalPoint[1] - initialPoint[1]};
    }

    private static double wedgeProduct2D(final double[] firstFactor, final double[] secondFactor) {
        return firstFactor[0] * secondFactor[1] - firstFactor[1] * secondFactor[0];
    }

    static private double dotProduct2D(final double[] firstFactor, final double[] secondFactor) {
        return firstFactor[0] * secondFactor[0] + firstFactor[1] * secondFactor[1];
    }

    private Circle currentCircle;
    private double currentSquareRadius;

    public final T computeValue(Circle circle, Shape shape) {
        initialize();
        processCircleShape(circle, shape);
        return getValue();
    }

    private void processCircleShape(Circle circle, final Shape cellBoundaryPolygon) {
        initializeForNewCirclePrivate(circle);
        if (cellBoundaryPolygon == null) {
            return;
        }
        PathIterator boundaryPathIterator = cellBoundaryPolygon.getPathIterator(null);
        double[] firstVertex = new double[2];
        double[] oldVertex = new double[2];
        double[] newVertex = new double[2];
        int segmentType = boundaryPathIterator.currentSegment(firstVertex);
        if (segmentType != PathIterator.SEG_MOVETO) {
            throw new AssertionError();
        }
        System.arraycopy(firstVertex, 0, newVertex, 0, 2);
        boundaryPathIterator.next();
        System.arraycopy(newVertex, 0, oldVertex, 0, 2);
        segmentType = boundaryPathIterator.currentSegment(newVertex);
        while (segmentType != PathIterator.SEG_CLOSE) {
            processSegment(oldVertex, newVertex);
            boundaryPathIterator.next();
            System.arraycopy(newVertex, 0, oldVertex, 0, 2);
            segmentType = boundaryPathIterator.currentSegment(newVertex);
        }
        processSegment(newVertex, firstVertex);
    }

    private void initializeForNewCirclePrivate(Circle circle) {
        currentCircle = circle;
        currentSquareRadius = currentCircle.getRadius() * currentCircle.getRadius();
        initializeForNewCircle(circle);
    }

    private void processSegment(double[] initialVertex, double[] finalVertex) {
        double[] segmentDisplacement = displacment2D(initialVertex, finalVertex);
        if (segmentDisplacement[0] == 0 && segmentDisplacement[1] == 0) {
            return;
        }
        double segmentLength = Math.sqrt(dotProduct2D(segmentDisplacement, segmentDisplacement));
        double[] centerToInitialDisplacement = new double[]{initialVertex[0] - getCurrentCircle().getCenterX(), initialVertex[1] - getCurrentCircle().getCenterY()};
        final double leftX = dotProduct2D(centerToInitialDisplacement, segmentDisplacement) / segmentLength;
        final double rightX = leftX + segmentLength;
        final double y = wedgeProduct2D(segmentDisplacement, centerToInitialDisplacement) / segmentLength;
        processSegmentStandardGeometry(leftX, rightX, y);
    }

    private void processSegmentStandardGeometry(double leftX, double rightX, double y) {
        if (y * y > getCurrentSquareRadius()) {
            processNonIntersectingRegion(leftX, rightX, y);
        } else {
            final double intersectionX = Math.sqrt(getCurrentSquareRadius() - y * y);
            if (leftX < -intersectionX) {
                final double leftRegionRightEndpoint = Math.min(-intersectionX, rightX);
                processNonIntersectingRegion(leftX, leftRegionRightEndpoint, y);
            }
            if (intersectionX < rightX) {
                final double rightRegionLeftEndpoint = Math.max(intersectionX, leftX);
                processNonIntersectingRegion(rightRegionLeftEndpoint, rightX, y);
            }
            final double middleRegionLeftEndpoint = Math.max(-intersectionX, leftX);
            final double middleRegionRightEndpoint = Math.min(intersectionX, rightX);
            final double middleRegionLength = Math.max(middleRegionRightEndpoint - middleRegionLeftEndpoint, 0);
            processIntersectingRegion(middleRegionLength, y);
        }
    }

    private void processNonIntersectingRegion(double leftX, double rightX, double y) {
        final double initialTheta = Math.atan2(y, leftX);
        final double finalTheta = Math.atan2(y, rightX);
        double deltaTheta = finalTheta - initialTheta;
        if (deltaTheta < -Math.PI) {
            deltaTheta += 2 * Math.PI;
        } else if (deltaTheta > Math.PI) {
            deltaTheta -= 2 * Math.PI;
        }
        processNonIntersectingRegion(deltaTheta);
    }

    protected abstract void initialize();

    protected abstract void initializeForNewCircle(Circle circle);

    protected abstract void processNonIntersectingRegion(double deltaTheta);

    protected abstract void processIntersectingRegion(double length, double y);

    protected abstract T getValue();

    protected final Circle getCurrentCircle() {
        return currentCircle;
    }

    protected final double getCurrentSquareRadius() {
        return currentSquareRadius;
    }

Во всяком случае, это мое описание алгоритма. Я думаю, что это хорошо, потому что это точно, и на самом деле не так много случаев, чтобы проверить.

Ответ 3

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

Ответ 4

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

Это не симпатичная формула или особенно быстро, но она выполняет свою работу.

Ответ 5

попробуйте вычислительная геометрия

Примечание: это не тривиальная проблема, я надеюсь, что это не домашняя работа; -)

Ответ 6

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

Ответ 7

Я думаю, вы не должны аппроксимировать круг как некоторый набор треугольников, вместо этого вы можете аппроксимировать его форму полигоном. Наивный алгоритм может выглядеть так:

• Преобразуйте круг в многоугольник с некоторым количеством вершин.
• Вычислите пересечение двух полигонов (преобразованный круг и треугольник).
• Вычислить квадрат этого пересечения.

Вы можете оптимизировать этот алгоритм, объединив шаги 2 и 3 в единую функцию.

Прочитать ссылки:
Площадь выпуклого многоугольника
Пересечение выпуклых многоугольников

Ответ 8

Поскольку ваши формы выпуклые, вы можете использовать оценку площади Монте-Карло.

Нарисуйте прямоугольник вокруг круга и треугольника.

Выберите случайные точки в поле и подсчитайте количество падений в круге и сколько падайте в круг и треугольник.

Площадь пересечения ≅ Площадь круга * # точек в круге и треугольника /# точек в круге

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

Примечание: здесь, как вы определяете, находится ли точка в треугольнике: Барицентрические координаты

Ответ 9

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

Ответ 10

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

В соответствии с эти уравнения:

ϑ = 2 sin⁻¹(0.5 c / r)
A = 0.5 r² (ϑ - sin(ϑ))

где c - длина хорды, r - радиус, θ - угол по центру, а A - площадь. Обратите внимание, что это решение ломается, если отключено более половины круга.

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

Ответ 11

Моим первым инстинктом было бы преобразовать все, чтобы окружность была сосредоточена по происхождению, перевела треугольник в полярные координаты и решила для пересечения (или охвата) треугольника с кругом. Я на самом деле не работал на бумаге, хотя так, что только догадка.