Рубрики

Подсчитать интегральные точки внутри треугольника

Для трех неколлинеарных интегральных точек на плоскости XY найдите количество интегральных точек внутри треугольника, образованного тремя точками. (Точка в плоскости XY называется интегральной / решеточной точкой, если обе ее координаты являются интегральными).

Пример:

Input: p = (0, 0), q = (0, 5) and r = (5,0) 

Output: 6

Explanation: The points (1,1) (1,2) (1,3) (2,1)
             (2,2) and (3,1) are the integral
             points inside the triangle.


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


Pick's Theeorem:
 A = I + (B/2) -1

A ==> Area of Polygon
B ==> Number of integral points on edges of polygon
I ==> Number of integral points inside the polygon

Using the above formula, we can deduce,
I = (2A - B + 2) / 2 

Мы можем найти A (площадь треугольника), используя приведенную ниже формулу Шнеласа .

A =  1/2 * abs(x1(y2 - y3) + x2(y3 - y1) + x3(y1 - y2)) 

Как найти B (количество целых точек на ребрах треугольника)?
Мы можем найти число целых точек между любыми двумя вершинами (V1, V2) треугольника, используя следующий алгоритм.

1. If the edge formed by joining V1 and V2 is parallel 
   to the X-axis, then the number of integral points 
   between the vertices is : 
        abs(V1.y - V2.y)-1

2. Similarly, if edge is parallel to the Y-axis, then 
   the number of integral points in between is :
    abs(V1.x - V2.y)-1

3. Else, we can find the integral points between the
   vertices using below formula:
     GCD(abs(V1.x-V2.x), abs(V1.y-V2.y)) - 1
   The above formula is a well known fact and can be 
   verified using simple geometry. (Hint: Shift the 
   edge such that one of the vertex lies at the Origin.) 

Please refer below link for detailed explanation.
https://www.geeksforgeeks.org/number-integral-points-two-points/amp/

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для поиска интегральных точек внутри треугольника
#include<bits/stdc++.h>

using namespace std;

  
// Класс для представления интегральной точки на плоскости XY.

class Point

{

public:

    int x, y;

    Point(int a=0, int b=0):x(a),y(b) {}

};

  
// функция полезности для поиска GCD из двух чисел
// GCD a и b

int gcd(int a, int b)

{

    if (b == 0)

       return a;

    return gcd(b, a%b);

}

  
// Находит номер Интегральных точек между
// две заданные точки.

int getBoundaryCount(Point p,Point q)

{

    // Проверяем, параллельна ли линия осям

    if (p.x==q.x)

        return abs(p.y - q.y) - 1;

    if (p.y == q.y)

        return abs(p.x-q.x) - 1;

  

    return gcd(abs(p.x-q.x),abs(p.y-q.y))-1;

}

  
// Возвращает количество точек внутри треугольника

int getInternalCount(Point p, Point q, Point r)

{

    // 3 дополнительные целочисленные точки для вершин

    int BoundaryPoints = getBoundaryCount(p, q) +

                         getBoundaryCount(p, r) +

                         getBoundaryCount(q, r) + 3;

  

    // Рассчитать 2 * A для треугольника

    int doubleArea = abs(p.x*(q.y - r.y) + q.x*(r.y - p.y)  +

                         r.x*(p.y - q.y));

  

    // Используем теорему Пика для вычисления нет. внутренних точек

    return (doubleArea - BoundaryPoints + 2)/2;

}

  
// функция драйвера для проверки программы.

int main()

{

    Point p(0, 0);

    Point q(5, 0);

    Point r(0, 5);

    cout << "Number of integral points inside given triangle is "

         << getInternalCount(p, q, r);

    return 0;

}

Джава

// Java-программа для поиска интегральных точек внутри треугольника
// Класс для представления интегральной точки на плоскости XY.

class Point

{

    int x, y;

  

    public Point(int a, int b) 

    {

        x = a;

        y = b;

    }

}

  

class GFG 

{

    // функция полезности для поиска GCD из двух чисел

    // GCD a и b

    static int gcd(int a, int b) 

    {

        if (b == 0)

            return a;

        return gcd(b, a % b);

    }

  

    // Находит номер Интегральных точек между

    // две заданные точки.

    static int getBoundaryCount(Point p, Point q)

    {

        // Проверяем, параллельна ли линия осям

        if (p.x == q.x)

            return Math.abs(p.y - q.y) - 1;

  

        if (p.y == q.y)

            return Math.abs(p.x - q.x) - 1;

  

        return gcd(Math.abs(p.x - q.x), 

                   Math.abs(p.y - q.y)) - 1;

    }

  

    // Возвращает количество точек внутри треугольника

    static int getInternalCount(Point p, Point q, Point r)

    {

  

        // 3 дополнительные целочисленные точки для вершин

        int BoundaryPoints = getBoundaryCount(p, q) + 

                             getBoundaryCount(p, r) + 

                             getBoundaryCount(q, r) + 3;

  

        // Рассчитать 2 * A для треугольника

        int doubleArea = Math.abs(p.x * (q.y - r.y) + 

                                  q.x * (r.y - p.y) + 

                                  r.x * (p.y - q.y));

  

        // Используем теорему Пика для расчета

        // нет. внутренних точек

        return (doubleArea - BoundaryPoints + 2) / 2;

    }

  

    // Код драйвера

    public static void main(String[] args) 

    {

        Point p = new Point(0, 0);

        Point q = new Point(5, 0);

        Point r = new Point(0, 5);

        System.out.println("Number of integral points" +

                           " inside given triangle is "

                              getInternalCount(p, q, r));

    }

}

  
// Этот код предоставлен Вивеком Кумаром Сингхом

C #

// C # программа для поиска интегральных точек
// внутри треугольника

using System;

  
// Класс для представления интегральной точки
// в плоскости XY.

public class Point

{

    public int x, y;

  

    public Point(int a, int b) 

    {

        x = a;

        y = b;

    }

}

  

class GFG 

{

    // функция полезности для поиска GCD из

    // два числа а и б

    static int gcd(int a, int b) 

    {

        if (b == 0)

            return a;

        return gcd(b, a % b);

    }

  

    // Находит номер Интегральных точек между

    // две заданные точки.

    static int getBoundaryCount(Point p, Point q)

    {

        // Проверяем, параллельна ли линия осям

        if (p.x == q.x)

            return Math.Abs(p.y - q.y) - 1;

  

        if (p.y == q.y)

            return Math.Abs(p.x - q.x) - 1;

  

        return gcd(Math.Abs(p.x - q.x), 

                Math.Abs(p.y - q.y)) - 1;

    }

  

    // Возвращает количество точек внутри треугольника

    static int getInternalCount(Point p, Point q, Point r)

    {

  

        // 3 дополнительные целочисленные точки для вершин

        int BoundaryPoints = getBoundaryCount(p, q) + 

                             getBoundaryCount(p, r) + 

                              getBoundaryCount(q, r) + 3;

  

        // Рассчитать 2 * A для треугольника

        int doubleArea = Math.Abs(p.x * (q.y - r.y) + 

                                  q.x * (r.y - p.y) + 

                                  r.x * (p.y - q.y));

  

        // Используем теорему Пика для расчета

        // нет. внутренних точек

        return (doubleArea - BoundaryPoints + 2) / 2;

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

        Point p = new Point(0, 0);

        Point q = new Point(5, 0);

        Point r = new Point(0, 5);

        Console.WriteLine("Number of integral points" +

                         " inside given triangle is "

                            getInternalCount(p, q, r));

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

Number of integral points inside given triangle is 6

Эта статья предоставлена Ашутошем Кумаром . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Подсчитать интегральные точки внутри треугольника

0.00 (0%) 0 votes