Дана точка А(х, у). Определить, принадлежит ли она треугольнику

@pro100saniok · Регистрация: 11.04.2010

Author24 — интернет-сервис помощи студентам

Дана точка А(х, у). Определить, принадлежит ли она треугольнику с вершинами в точках (х1, у1), (х2, у2), (x3, y3).

@kambain · 11.04.2010, 17:17

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

@erlik · 11.04.2010, 18:58

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

В общем вот тебе пример - это переделанный под C# код на lua который я в одной игре использовал - там он отлично работал вычисляя находится ли персонаж в нужной зоне или нет
В шарпе я сам новичок - поэтому если кто то увидит недочеты - поправьте.

C#

    
class Tri
    {
        public int[] xp;
        public int[] yp;
        public int x;
        public int y;
        public int npol;
 
 
        public int Triangle(int npol, int[] xp, int[] yp, int x,int y)
        {
            int c = 0;
            for (int i = 0, j = npol - 1; i < npol; j = i++)
            {
                if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) &&
                  (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
                    c = 1 - c;
            }
            return c;
        }
 
        public bool Res()
       { 
       Tri  t = new Tri();
 
       xp = new int[] {0,2,4}; // массив х вершин треугольника
       yp = new int [] {0, 2, 2 }; // массив  у вершин треугольника
       x = 2;  // координата x точки 
       y = 1; // координата y точки 
       npol = xp.Length;
       int res = t.Triangle(npol, xp, yp, x, y);
 
            if (res==1) // точка внутри
            {
            return true;
            }
            return false; // иначе - снаружи
          }
    } 
 
 
    static void Main()
    {
       
        Tri t = new Tri();
        bool text = t.Res();
        Console.WriteLine(text==true ? "Точка принадлежит треугольнику!" : "Точка снаружи");
        Console.ReadKey();
      
        }

Добавлено через 19 минут
да чуть не забыл - координаты (если я не ошибаюсь) нужно вписывать в порядке обхода вершин по часовой стрелке.

@pro100saniok · 12.04.2010, 00:04 **[ТС]**

[QUOTE=erlik;654513]pro100saniok,

C#

    static void Main()
    {
       
        Tri t = new Tri();
        bool text = t.Res();
        Console.WriteLine(text==true ? "Точка принадлежит треугольнику!" : "Точка снаружи");
        Console.ReadKey();
      
        }

[/CSHARP]

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

@NightmareCode · 12.04.2010, 00:24

Как-то так:

C#

public static double AreaOfTriangle(Point a, Point b, Point c)
{
   return ((((b.x-a.x)*(c.y-a.y))-((c.x-a.x)*(b.y-a.y)))/2.0d);
}

@erlik · 12.04.2010, 01:13

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

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

@Mikant · 12.04.2010, 03:23

Не по теме:

Сообщение от erlik

В шарпе я сам новичок - поэтому если кто то увидит недочеты - поправьте

1) нет разметки кода (ну эт не шарп, конечно, но убить можно)
2) нарушение инкапсуляции - все поля класса должны быть приватны (а доступ уж через аксессоры (свойства))
3) очень плохое именование переменных/параметров. в C# - паскаль (верблюжья) нотация действует: вместо Tri - Triangle, вместо Res - Result, поля начинаются с "_" : _pointA;
4) нарушение логики: в свободный метод передаются параметры этой самой точки - бред
5) глупый тернарный оператор : text==true ? ... не проще ли text ? ... ну и разумеется имя переменной text не отражает ничего, кроме собственной несостоятельности
6) не зависящие от контекста методы не статичны
7) пространства имён НЕТ
8) нарушение логики: обязательный вызов метода из внутреннего кода
в итоге - суперНЕувиресальное решение: а в шарпе все наоборот. надо максимально дифференцировать логику с минимизацией стороннего функционала и выдержкой обобщенности

Добавлено через 7 минут

Не по теме:

и еще очень много чего. в т.ч. критичного

Добавлено через 13 минут

Не по теме:

на здоровье. посмотри на обрамления всех элементов

C#

using System;
 
namespace CyberForum {
    public struct Point {
        private float _x;
        private float _y;
 
        public Point(float x, float y) {
            _x = x;
            _y = y;
        }
 
        public float X {
            get { return _x; }
            set { _x = value; }
        }
 
        public float Y {
            get { return _y; }
            set { _y = value; }
        }
    }
 
    public class Triangle {
        private Point _a;
        private Point _b;
        private Point _c;
 
        public Triangle(Point a, Point b, Point c) {
            _a = a;
            _b = b;
            _c = c;
        }
 
        public bool IsInside(Point p) {
            // тут твой код. без глобальных переменных: всё на стеке
            return true;
        }
 
        //// можно и это использовать из IsInside, никто не против
        //private bool CrossCountIsOdd(Point p) {
        //    // вычисление кол-ва этих твоих пересечений
        //    return true;
        //}
 
        public Point A {
            get { return _a; }
        }
 
        public Point B {
            get { return _b; }
        }
 
        public Point C {
            get { return _c; }
        }
 
    }
 
    public static class Program {
 
        private static void Main() {
            Point p1 = new Point(0, 0);
            Point p2 = new Point(0, 10);
            Point p3 = new Point(10, 0);
            Point p4 = new Point(1, 1);
 
            Triangle t = new Triangle(p1, p2, p3);
 
            Console.WriteLine(t.IsInside(p4) ? "Внутри" : "Снаружи");
            Console.ReadKey();
        }
 
    }
}

@pro100saniok · 12.04.2010, 09:15 **[ТС]**

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace  cyberforum
{
    class Program
    {
        static void Main(string[] args)

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

C#

1
2
3

 public static class Program {
 
        private static void Main() { }

етот код находится в конце ??

C#

1 2	'Program': member names cannot be the same as their enclosing type

у меня появляется такая ошыбка ))

@outoftime · 12.04.2010, 09:33

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

@erlik · 12.04.2010, 12:20

Mikant,
Спасибо за пояснение- только не мог бы ты указывать на ошибки более корректным тоном.
Я понимаю -после года изучения языка чувствуешь себя наверно МегаГУРУ, однако я его изучаю всего два месяца - и мои ошибки это обычные ошибки любого новичка.
С ООП я пока толком не работал поэтому создавать универсальные модели не умею.
Кстати в lua этот код вообще занимает 14 строчек, а не сотню как выходит с твоей разметкой. Я же хотел как покороче - ну в общем как привык работая с lua. Если не считать того что это вспомогательный сценарный язык - то гибче и компактнее его трудно найти.

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

у меня никакой ошибки от вставки кода Mikant'а, не появляется.

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

C#

namespace CyberForum
{
 
    public class Triangle
    {
 
        public bool IsInside(int npol, float[] xp, float[] yp, float x, float y)
        {
 
            int c = 0;
            for (int i = 0, j = npol - 1; i < npol; j = i++)
            {
                if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) &&
                  (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
                    c = 1 - c;
            }
 
 
            if (c == 1) // точка внутри
            {
                return true;
            }
            return false; // иначе - снаружи
 
        }
 
        //public static class Program  а зачем это ???
        //{
 
            private static void Main()
            {
 
 
                float[] xp = { 0, 2, 4 }; // масив  х вершин
                float[] yp = { 0, 2, 2 }; // массив  у вершин
                float x = 2;
                float y = 1;
                int npol = xp.Length;
 
                Triangle t = new Triangle();
                bool result = t.IsInside(npol, xp, yp, x, y);
 
                Console.WriteLine(result ? "Внутри" : "Снаружи");
                Console.ReadKey();
            }
 
        }
    }

@Frozzeg · 12.04.2010, 16:56

C#

if (c == 1) // точка внутри
            {
                return true;
            }
            return false; // иначе - снаружи

==

C#

1	return c == 1;

@pro100saniok · 31.05.2010, 04:09 **[ТС]**

кто то может по этой теме сделать итоги,и написать полностью код програми на С# ?

@pro100saniok · 14.06.2010, 23:32 **[ТС]**

я попробовал сам подбить итоги по этому заданию, кто может исправить если что не так ))

C#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace ConsoleApplication4
{
 
    public class Triangle
    {
 
        public bool IsInside(int npol, float[] xp, float[] yp, float x, float y)
        {
 
            int c = 0;
            for (int i = 0, j = xp.Length - 1; i < xp.Length; j = i++)
            {
                if ((((yp[i] <= y) && (y < yp[j])) || ((yp[j] <= y) && (y < yp[i]))) &&
                  (x > (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
                    c = 1 - c;
            }
 
 
            if (c == 1) // точка внутри
            {
                return true;
            }
            return false; // иначе - снаружи
 
        }
        static int[] enter_point()
        {
            string s = Console.ReadLine();
            string[] data = s.Split(' ', ',');
            int[] mas = new int[data.Length];
            for (int i = 0; i < data.Length; i++)
                mas[i] = int.Parse(data[i]);
            return mas;
        }
 
       
        private static void Main()
        {
 
 
            Console.WriteLine("Введите координаты точки А");
            int[] A = new int[2];
            float[] xp = new float[3]; // масив  х вершин
            float[] yp = new float[3]; // массив  у вершин
            A = enter_point();
            int[] temp = new int[2];
            Console.WriteLine("Введите координаты вершин треугольника");
            int i = 0;
            while (i < 3)
            {
 
                Console.WriteLine("Вершина №{0}:", i + 1);
                temp = enter_point();
                xp[i] = temp[0];
                yp[i] = temp[1];
                i++;
            }
            float x = A[0];
            float y = A[1];
            int npol = xp.Length;
 
            Triangle t = new Triangle();
            bool result = t.IsInside(npol, xp, yp, x, y);
 
            Console.WriteLine();
            Console.WriteLine(result ? "Внутри" : "Снаружи");
            Console.ReadKey();
        }
 
    }
}

помогите написать алгоритм решения к етой задачи !

@kuroiryuu · 15.06.2010, 13:28

странный этот метод:

C#

bool IsInside(Point[] p, int x, int y)
{
    int c = 0;
    for (int i = 0, j = p.Length - 1; i < p.Length; j = i++)
        if ((((p[i].Y <= y) && (y < p[j].Y)) || ((p[j].Y <= y) && (y < p[i].Y))) &&
          (x > (p[j].X - p[i].X) * (y - p[i].Y) / (p[j].Y - p[i].Y) + p[i].X))
            c = 1 - c;
 
    if (c == 1) // точка внутри
        return true;
 
    return false; // иначе - снаружи
}

проверял на треугольнике Point[] p = new Point[] { new Point(0, 40), new Point(30, 0), new Point(0, 0) };
и для проверки ввёл точку (0, 20) и получил false

нашел у себя еще одну функцию для нахождения принадлежности точки фигуре (но она громозкая):

C#

bool IsPointInsidePolygon(Point[] p, int x, int y)
{
    int i1, i2, N, S, S1, S2, S3;
    bool flag = false;
    N = p.Length;
    for (int n = 0; n < N; n++)
    {
        flag = false;
        i1 = n < N - 1 ? n + 1 : 0;
        while (!flag)
        {
            i2 = i1 + 1;
            if (i2 >= N)
                i2 = 0;
            if (i2 == (n < N - 1 ? n + 1 : 0))
                break;
            S = Math.Abs(p[i1].X * (p[i2].Y - p[n].Y) +
                     p[i2].X * (p[n].Y - p[i1].Y) +
                     p[n].X * (p[i1].Y - p[i2].Y));
            S1 = Math.Abs(p[i1].X * (p[i2].Y - y) +
                      p[i2].X * (y - p[i1].Y) +
                      x * (p[i1].Y - p[i2].Y));
            S2 = Math.Abs(p[n].X * (p[i2].Y - y) +
                      p[i2].X * (y - p[n].Y) +
                      x * (p[n].Y - p[i2].Y));
            S3 = Math.Abs(p[i1].X * (p[n].Y - y) +
                      p[n].X * (y - p[i1].Y) +
                      x * (p[i1].Y - p[n].Y));
            if (S == S1 + S2 + S3)
            {
                flag = true;
                break;
            }
            i1 = i1 + 1;
            if (i1 >= N)
                i1 = 0;
        }
        if (!flag)
            break;
    }
    return flag;
}

эта вернула true

@erlik · 16.06.2010, 20:17

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

@kuroiryuu · 17.06.2010, 11:43

Не по теме:

erlik, я описал, то что обнаружил при тестировании кода и не более.
будет это полезно кому-нибудь - хорошо, не будет - ещё лучше.

@pro100saniok · 20.06.2010, 18:33 **[ТС]**

Сообщение от erlik

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

мне надо узнать принадлежит ли двумерная точка треугольнику с двумерными координатами?

вот ссылка Алгоритм по данной теме
Как проверить принадлежит ли точка треугольнику?

@pro100saniok · 23.06.2010, 00:41 **[ТС]**

Сообщение от Somebody

Уже было - https://www.cyberforum.ru/showthread.php?t=8234.
Математическая часть - векторное и псевдоскалярное произведения.
Реализация - считаются произведения (1, 2, 3 - вершины треугольника, 0 - точка):
(x1 - x0) * (y2 - y1) - (x2 - x1) * (y1 - y0)
(x2 - x0) * (y3 - y2) - (x3 - x2) * (y2 - y0)
(x3 - x0) * (y1 - y3) - (x1 - x3) * (y3 - y0)
Если они одинакового знака, то точка внутри треугольника, если что-то из этого - ноль, то точка лежит на стороне, иначе точка вне треугольника.

вот решения по данной формуле выше, решил не я
namespace zadacha_2

C#

    class Program
    {
        static void Main(string[] args)
        {
 
            int[] x = new int[4];
            int[] y = new int[4];
            for (int i = 0; i < 4; ++i)
            {
               Console.Write("Введите (x" + i.ToString() + ",y" + i.ToString() + "): ");
                x[i] = Console.Read();
                y[i] = Console.Read();
                Console.ReadLine();
            }
            int a = (x[1] - x[0]) * (y[2] - y[1]) - (x[2] - x[1]) * (y[1] - y[0]);
            int b = (x[2] - x[0]) * (y[3] - y[2]) - (x[3] - x[2]) * (y[2] - y[0]);
            int c = (x[3] - x[0]) * (y[1] - y[3]) - (x[1] - x[3]) * (y[3] - y[0]);
 
            if ((a >= 0 && b >= 0 && c >= 0) || (a <= 0 && b <= 0 && c <= 0))
            {
                Console.WriteLine("Принадлежит треугольнику");
            }
            else
            {
                Console.WriteLine("Не принадлежит треугольнике");
            }
            Console.ReadKey();
        }

Добавлено через 2 часа 31 минуту
вот эту я сам писал,но только ошибку вибивает

Operator '==' cannot be applied to operands of type 'bool' and 'int'

C#

 class Program
    {
        static void Main(string[] args)
        {
            int x, y, x1, y1, x2, y2, x3, y3;
            int s, s1, s2, s3;
            Console.WriteLine("\nVvedite koordinaty treugolnika:");
            Console.WriteLine("x1=");
            x1 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("y1="); 
            y1 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("x2=");
            x2 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("y2="); 
            y2 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("x3=");
            x3 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("y3");
            y3 = Int32.Parse(Console.ReadLine());
            Console.WriteLine("\nVVedite koordinaty tochki: ");
            Console.WriteLine("y=");
            x = Int32.Parse(Console.ReadLine());
            Console.WriteLine("x=");
            y = Int32.Parse(Console.ReadLine());
 
            if ((x1==x2==x3) || (y1==y2==y3))
            {
                Console.WriteLine("\nNevernye koordinaty treugolnika!");
            }
            {
                s = 1 / 2 *Math.Abs((x2 - x1) * (y3 - y1) - (x3 - x1) * (y2 - y1));
                s1 = 1 / 2 *Math.Abs((x2 - x1) * (y - y1) - (x - x1) * (y2 - y1));
                s2 = 1 / 2 *Math.Abs((x - x1) * (y3 - y1) - (x3 - x1) * (y - y1));
                s3 = 1 / 2 *Math.Abs((x2 - x) * (y3 - y) - (x3 - x) * (y2 - y));
 
                if (s == s1 + s2 + s3)
                
                    Console.WriteLine("\n Tochka v treugolnike! ");
                else 
                    Console.WriteLine("\n Vne treugolnika!");
                
                }
            Console.ReadKey();
 
 
            }

@pro100saniok 42 / 42 / 3 Регистрация: 11.04.2010 Сообщений: 177
		1
	Дана точка А(х, у). Определить, принадлежит ли она треугольнику 11.04.2010, 15:19. Показов 15013. Ответов 17 Метки нет (Все метки) Дана точка А(х, у). Определить, принадлежит ли она треугольнику с вершинами в точках (х1, у1), (х2, у2), (x3, y3). 0

@kambain 0 / 0 / 0 Регистрация: 04.11.2009 Сообщений: 23
	11.04.2010, 17:17	2
	Точка принадлежит многоугольнику, если она пересекает его стороны нечетное число раз. Если к примеру треугольник нарисован на битмапе и ты заведомо знаешь цвет фона, цвет границ треугольника, то достаточно попиксельно пройти от точки А до границы битмапа слева направо, сравнивая цвет. Это будет легко, если нарисован только треугольник. Если привязки к графике нет никакой, просто есть координаты - то задача сводится к сравниванию координат, исходя из этого же правила 0

@erlik 146 / 118 / 8 Регистрация: 09.03.2010 Сообщений: 150
	12.04.2010, 01:13	6
	pro100saniok, у меня там скобка закрывающая (перед методом Main) не в том месте стоит - нужно включить метод Main в границы класса - то есть переставить ее в конец. просто у меня в файле куча функций и классов (вложенных друг в друга)- поэтому не уследил за этой мелочью. Добавлено через 14 минут NightmareCode, а к чему приведена функция вычисления площади треугольника вместо заданной задачи? если уж вычислять по площади (долго и нудно) то выкладывай продолжение - а это только начало пути. 1

@outoftime ║XLR8║ 1212 / 909 / 270 Регистрация: 25.07.2009 Сообщений: 4,361 Записей в блоге: 5
	12.04.2010, 09:33	9
	pro100saniok, а я бы сделал многоугольник с тремя вершинамы и проверил принадлежит ли точка ему с помощью уже имеющихся класов 0

@pro100saniok 42 / 42 / 3 Регистрация: 11.04.2010 Сообщений: 177
	31.05.2010, 04:09 [ТС]	12
	кто то может по этой теме сделать итоги,и написать полностью код програми на С# ? 0

@erlik 146 / 118 / 8 Регистрация: 09.03.2010 Сообщений: 150
	16.06.2010, 20:17	15
	kuroiryuu, у меня нормально работала (я это дело в игре применял - для отслеживания попадания NPC в определенную зону - на выпуклых полигонах она работает как надо, - на прочих - точно не помню) - это же трассировка лучей - самый компактный и (наверно)быстрый способ - почитай о нем как-нить на досуге. 0

@kuroiryuu
	17.06.2010, 11:43 #16
	Не по теме: erlik, я описал, то что обнаружил при тестировании кода и не более. будет это полезно кому-нибудь - хорошо, не будет - ещё лучше. 0

@pro100saniok 42 / 42 / 3 Регистрация: 11.04.2010 Сообщений: 177
	20.06.2010, 18:33 [ТС]	17
	Сообщение от erlik kuroiryuu, у меня нормально работала (я это дело в игре применял - для отслеживания попадания NPC в определенную зону - на выпуклых полигонах она работает как надо, - на прочих - точно не помню) - это же трассировка лучей - самый компактный и (наверно)быстрый способ - почитай о нем как-нить на досуге. мне надо узнать принадлежит ли двумерная точка треугольнику с двумерными координатами? вот ссылка Алгоритм по данной теме Как проверить принадлежит ли точка треугольнику? 0