Как найти точку в треугольнике питон - Сайт, где вы сможете решить свои вопросы

Переписал формулу из этого ответа (спасибо nörbörnën).

В примере ниже, позиция курсора мышки сравнивается с положением треугольника и выводится надпись Collision! если курсор мышки находится в треугольнике.

Пример:

from dataclasses import dataclass
import sys

import pygame


BLACK = (  0,   0,   0)
WHITE = (255, 255, 255)


@dataclass
class Point:
    x: float
    y: float


def get_triangle_area(a: Point, b: Point, c: Point) -> float:
    return abs((a.x - c.x) * (b.y - c.y) + (b.x - c.x) * (c.y - a.y))


def is_point_in_triangle(a: Point, b: Point, c: Point, p: Point) -> bool:
    tr_area = get_triangle_area(a, b, c)  # Площадь основного треугольника

    tr_area2 = get_triangle_area(a, b, p)  # Площади треугольника, образованного из 2 точек основного
    tr_area3 = get_triangle_area(a, p, c)  # и точки, которая проверяется на принадлежность
    tr_area4 = get_triangle_area(b, p, c)  # к треугольнику

    # Если площади образованных треугольников равны, то точка в треугольнике
    return tr_area == tr_area2 + tr_area3 + tr_area4


pygame.init()

color = BLACK
screen = pygame.display.set_mode((600, 600))
clock = pygame.time.Clock()
mouse_pos = Point(0, 0)

# Triangle
a, b, c = Point(100, 100), Point(100, 400), Point(500, 500)

fnt = pygame.font.Font(None, 40)


while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            sys.exit()

        elif event.type == pygame.MOUSEMOTION:
            mouse_pos.x, mouse_pos.y = event.pos
            break

    screen.fill(WHITE)

    # This draws a triangle using the polygon command
    pygame.draw.polygon(screen, BLACK, [[a.x, a.y], [b.x, b.y], [c.x, c.y]], 5)

    if is_point_in_triangle(a, b, c, mouse_pos):
        color = BLACK
    else:
        color = WHITE

    text = fnt.render("Collision!", True, color)
    screen.blit(text, (260, 20))

    pygame.display.update()
    clock.tick(60)

Источник

Improve Article

Save Article

Like Article

Read

Discuss(40+)

Improve Article

Save Article

Like Article

Given three corner points of a triangle, and one more point P. Write a function to check whether P lies within the triangle or not.

Example:

Input: A = (0, 0), B = (10, 30), C = (20, 0), P(10, 15)
Output: Inside
Explanation:
              B(10,30)
                / 
               /   
              /     
             /   P         P'
            /         
     A(0,0) ----------- C(20,0) 

Input: A = (0, 0), B = (10, 30), C = (20, 0), P(30, 15)
Output: Outside
Explanation:
              B(10,30)
                / 
               /   
              /     
             /             P
            /         
     A(0,0) ----------- C(20,0)

Solution:
Let the coordinates of the three corners be (x1, y1), (x2, y2), and (x3, y3). And coordinates of the given point P be (x, y)

Calculate the area of the given triangle, i.e., the area of the triangle ABC in the above diagram.
Area A = [ x1(y2 – y3) + x2(y3 – y1) + x3(y1-y2)]/2
Calculate the area of the triangle PAB. We can use the same formula for this. Let this area be A1.
Calculate the area of the triangle PBC. Let this area be A2.
Calculate the area of the triangle PAC. Let this area be A3.
If P lies inside the triangle, then A1 + A2 + A3 must be equal to A.

C++

#include <bits/stdc++.h>

using namespace std;

float area(int x1, int y1, int x2, int y2, int x3, int y3)

{

return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);

}

bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)

{

float A = area (x1, y1, x2, y2, x3, y3);

float A1 = area (x, y, x2, y2, x3, y3);

float A2 = area (x1, y1, x, y, x3, y3);

float A3 = area (x1, y1, x2, y2, x, y);

return (A == A1 + A2 + A3);

}

int main()

{

if (isInside(0, 0, 20, 0, 10, 30, 10, 15))

cout <<"Inside";

else

cout <<"Not Inside";

return 0;

}

C

#include <stdio.h>

#include <math.h>

#include <stdbool.h>

#include <stdlib.h>

float area(int x1, int y1, int x2, int y2, int x3, int y3)

{

return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);

}

bool isInside(int x1, int y1, int x2, int y2, int x3, int y3, int x, int y)

{

float A = area (x1, y1, x2, y2, x3, y3);

float A1 = area (x, y, x2, y2, x3, y3);

float A2 = area (x1, y1, x, y, x3, y3);

float A3 = area (x1, y1, x2, y2, x, y);

return (A == A1 + A2 + A3);

}

int main()

{

if (isInside(0, 0, 20, 0, 10, 30, 10, 15))

printf ("Inside");

else

printf ("Not Inside");

return 0;

}

Java

import java.util.*;

class GFG {

static double area(int x1, int y1, int x2, int y2,

int x3, int y3)

{

return Math.abs((x1*(y2-y3) + x2*(y3-y1)+

x3*(y1-y2))/2.0);

}

static boolean isInside(int x1, int y1, int x2,

int y2, int x3, int y3, int x, int y)

{

double A = area (x1, y1, x2, y2, x3, y3);

double A1 = area (x, y, x2, y2, x3, y3);

double A2 = area (x1, y1, x, y, x3, y3);

double A3 = area (x1, y1, x2, y2, x, y);

return (A == A1 + A2 + A3);

}

public static void main(String[] args)

{

if (isInside(0, 0, 20, 0, 10, 30, 10, 15))

System.out.println("Inside");

else

System.out.println("Not Inside");

}

Python

def area(x1, y1, x2, y2, x3, y3):

return abs((x1 * (y2 - y3) + x2 * (y3 - y1)

+ x3 * (y1 - y2)) / 2.0)

def isInside(x1, y1, x2, y2, x3, y3, x, y):

A = area (x1, y1, x2, y2, x3, y3)

A1 = area (x, y, x2, y2, x3, y3)

A2 = area (x1, y1, x, y, x3, y3)

A3 = area (x1, y1, x2, y2, x, y)

if(A == A1 + A2 + A3):

return True

else:

return False

if (isInside(0, 0, 20, 0, 10, 30, 10, 15)):

print('Inside')

else:

print('Not Inside')

C#

using System;

class GFG {

static double area(int x1, int y1, int x2,

int y2, int x3, int y3)

{

return Math.Abs((x1 * (y2 - y3) +

x2 * (y3 - y1) +

x3 * (y1 - y2)) / 2.0);

}

static bool isInside(int x1, int y1, int x2,

int y2, int x3, int y3,

int x, int y)

{

double A = area(x1, y1, x2, y2, x3, y3);

double A1 = area(x, y, x2, y2, x3, y3);

double A2 = area(x1, y1, x, y, x3, y3);

double A3 = area(x1, y1, x2, y2, x, y);

return (A == A1 + A2 + A3);

}

public static void Main()

{

if (isInside(0, 0, 20, 0, 10, 30, 10, 15))

Console.WriteLine("Inside");

else

Console.WriteLine("Not Inside");

}

PHP

<?php

function area($x1, $y1, $x2,

$y2, $x3, $y3)

{

return abs(($x1 * ($y2 - $y3) +

$x2 * ($y3 - $y1) +

$x3 * ($y1 - $y2)) / 2.0);

}

function isInside($x1, $y1, $x2, $y2,

$x3, $y3, $x, $y)

{

$A = area ($x1, $y1, $x2, $y2, $x3, $y3);

$A1 = area ($x, $y, $x2, $y2, $x3, $y3);

$A2 = area ($x1, $y1, $x, $y, $x3, $y3);

$A3 = area ($x1, $y1, $x2, $y2, $x, $y);

return ($A == $A1 + $A2 + $A3);

}

if (isInside(0, 0, 20, 0, 10, 30, 10, 15))

echo "Inside";

else

echo "Not Inside";

?>

Javascript

<script>

function area(x1, y1, x2, y2, x3, y3)

{

return Math.abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0);

}

function isInside(x1, y1, x2, y2, x3, y3, x, y)

{

let A = area (x1, y1, x2, y2, x3, y3);

let A1 = area (x, y, x2, y2, x3, y3);

let A2 = area (x1, y1, x, y, x3, y3);

let A3 = area (x1, y1, x2, y2, x, y);

return (A == A1 + A2 + A3);

}

if (isInside(0, 0, 20, 0, 10, 30, 10, 15))

document.write("Inside");

else

document.write("Not Inside");

</script>

Time Complexity: O(1)
Auxiliary Space: O(1)

Exercise: Given coordinates of four corners of a rectangle, and a point P. Write a function to check whether P lies inside the given rectangle or not.

Another Approach – Using Barycentric Coordinate Method: Below is the algorithm to check if a point P lies inside a triangle ABC using the Barycentric Coordinate Method:

Define a function “isInsideTriangle” that takes four input parameters: A, B, C, and P.
Calculate the barycentric coordinates of point P with respect to the triangle ABC. To do this, we first need to calculate the area of the triangle ABC. We can use the cross product to find the area of the triangle ABC as:

Area(ABC) = 0.5 * ||AB x AC||, where ||AB x AC|| is the magnitude of the cross product of vectors AB and AC.

Then, we can calculate the barycentric coordinates of point P as:
1. a = 0.5 * ||PB x PC|| / Area(ABC)
2. b = 0.5 * ||PC x PA|| / Area(ABC)
3. c = 0.5 * ||PA x PB|| / Area(ABC), where PB, PC, and PA are vectors from point P to vertices B, C, and A, respectively.
If all three barycentric coordinates are non-negative, then the point P lies inside the triangle ABC. Return “Inside”. Otherwise, point P lies outside the triangle ABC. Return “Outside”.

Below is the implementation of the above approach:

C++

#include<iostream>

#include<vector>

using namespace std;

string isInsideTriangle(vector<int> A, vector<int> B, vector<int> C, vector<int> P) {

double denominator = ((B[1] - C[1]) * (A[0] - C[0]) + (C[0] - B[0]) * (A[1] - C[1]));

double a = ((B[1] - C[1]) * (P[0] - C[0]) + (C[0] - B[0]) * (P[1] - C[1])) / denominator;

double b = ((C[1] - A[1]) * (P[0] - C[0]) + (A[0] - C[0]) * (P[1] - C[1])) / denominator;

double c = 1 - a - b;

if (a >= 0 && b >= 0 && c >= 0) {

return "Inside";

} else {

return "Outside";

}

int main() {

vector<int> A = {0, 0};

vector<int> B = {10, 30};

vector<int> C = {20, 0};

vector<int> P = {10, 15};

string result = isInsideTriangle(A, B, C, P);

cout << result << endl;

return 0;

}

Java

import java.awt.Point;

class Main

{

public static String isInsideTriangle(Point A, Point B, Point C, Point P)

{

double denominator = ((B.y - C.y) * (A.x - C.x) +

(C.x - B.x) * (A.y - C.y));

double a = ((B.y - C.y) * (P.x - C.x) +

(C.x - B.x) * (P.y - C.y)) / denominator;

double b = ((C.y - A.y) * (P.x - C.x) +

(A.x - C.x) * (P.y - C.y)) / denominator;

double c = 1 - a - b;

if (a >= 0 && b >= 0 && c >= 0) {

return "Inside";

} else {

return "Outside";

}

public static void main(String[] args) {

Point A = new Point(0, 0);

Point B = new Point(10, 30);

Point C = new Point(20, 0);

Point P = new Point(10, 15);

String result = isInsideTriangle(A, B, C, P);

System.out.println(result);

}

Python3

def isInsideTriangle(A, B, C, P):

denominator = ((B[1] - C[1]) * (A[0] - C[0]) +

(C[0] - B[0]) * (A[1] - C[1]))

a = ((B[1] - C[1]) * (P[0] - C[0]) +

(C[0] - B[0]) * (P[1] - C[1])) / denominator

b = ((C[1] - A[1]) * (P[0] - C[0]) +

(A[0] - C[0]) * (P[1] - C[1])) / denominator

c = 1 - a - b

if a >= 0 and b >= 0 and c >= 0:

return "Inside"

else:

return "Outside"

A = (0, 0)

B = (10, 30)

C = (20, 0)

P = (10, 15)

result = isInsideTriangle(A, B, C, P)

print(result)

Javascript

function isInsideTriangle(A, B, C, P) {

let denominator = ((B[1] - C[1]) * (A[0] - C[0]) +

(C[0] - B[0]) * (A[1] - C[1]));

let a = ((B[1] - C[1]) * (P[0] - C[0]) +

(C[0] - B[0]) * (P[1] - C[1])) / denominator;

let b = ((C[1] - A[1]) * (P[0] - C[0]) +

(A[0] - C[0]) * (P[1] - C[1])) / denominator;

let c = 1 - a - b;

if (a >= 0 && b >= 0 && c >= 0) {

return "Inside";

} else {

return "Outside";

}

let A = [0, 0];

let B = [10, 30];

let C = [20, 0];

let P = [10, 15];

let result = isInsideTriangle(A, B, C, P);

console.log(result);

Time Complexity: O(1)
Auxiliary Space: O(1)

Last Updated :
27 Apr, 2023

Like Article

Save Article

Источник

Последнее обновление 25 июля 2019 05:38:05 (UTC / GMT +8 часов)

script1adsense2code

script1adsense3code

Python Basic – 1: Упражнение 40 с решением

Напишите программу на Python, чтобы проверить, находится ли точка (x, y) в треугольнике или нет. Существует треугольник, образованный тремя точками.

Входные данные :
x1, y1, x2, y2, x3, y3, xp, yp, разделенные одним пробелом.

Пример решения :

Код Python:

print("Input x1,y1,x2,y2,x3,y3,xp,yp:")
x1,y1,x2,y2,x3,y3,xp,yp = map(float, input().split())
c1 = (x2-x1)*(yp-y1)-(y2-y1)*(xp-x1)
c2 = (x3-x2)*(yp-y2)-(y3-y2)*(xp-x2)
c3 = (x1-x3)*(yp-y3)-(y1-y3)*(xp-x3)
if (c1<0 and c2<0 and c3<0) or (c1>0 and c2>0 and c3>0):
    print("The point is in the triangle.")
else:
    print("The point is outside the triangle.")

Пример вывода:

 Введите x1, y1, x2, y2, x3, y3, xp, yp:
 2 3 4 5 6 8 7 1
Точка находится за пределами треугольника.

Блок – схема:

Редактор кода Python:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Предыдущий: Напишите программу на Python для вывода числа простых чисел, которые меньше или равны данному целому числу.
Далее: Написать программу на Python для вычисления и вывода суммы двух заданных целых чисел (больше или равно нулю). Если заданные целые числа или сумма имеют более 80 цифр, выведите «overflow».

Источник

Python: проверьте, находится ли точка (x, y) в треугольнике или нет

Python Basic – 1: Упражнение 40 с решением

Входные данные :
x1, y1, x2, y2, x3, y3, xp, yp, разделенные одним пробелом.

Пример решения :

Код Python:

Блок – схема:

Редактор кода Python:

Есть другой способ решить это решение? Внесите свой код (и комментарии) через Disqus.

Каков уровень сложности этого упражнения?

Определение принадлежности точки треугольнику

Дано: у нас есть треугольник, нам известны только координаты его вершин. У нас есть точка, нам известны её координаты.

Что нужно узнать: нужно установить принадлежность точки треугольнику.

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

Метод сравнения площадей

В данном методе сначала находятся площади 3-х треугольников, которые образует данная точка с каждой стороной треугольника. В нашем случае(рис. 1) это треугольники ABP, BCP, CAP и их площади s1, s2, s3 соответственно.

Затем находится площадь самого треугольника ABC.

Найденный площади сравниваются — если сумма 3-х площадей равна площади всего треугольника, то значит точка принадлежит треугольнику. При сравнении, как правило, задаётся погрешность.

Так как у нас известны только координаты точек, то все площади, находятся по формуле Герона, от обильности операций которой становится ясно, почему этот метод очень трудоёмкий.

Простейшая реализация алгоритма:

Атрибуты функции: aAx, aAy, aBx, aBy, aCx, aCy — координаты точек A, B, C треугольника; aPx, aPy — координаты точки, принадлежность которой надо определить.

Метод относительности

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

На рисунке 2 продемонстрирована ситуация, когда точка только для одной прямой AB лежит по левую сторону, а значит не принадлежит треугольнику.

Всё относительно!

Тут надо кое что пояснить, весьма не маловажное, что может сыграть роль в оптимизации и выборе алгоритма. Обратите внимание, что в приведённом коде есть закомментированные блоки кода с комментариями «для строгой ориентации», в то время как рабочий код универсален — он предназначен для любой ориентации. Т.е. представленный код определит принадлежность точки для любого заданного треугольника. В моей тестирующей программе треугольники как раз таки строятся по random()-у координат вершин, а ориентация идёт по вершинам(A>B>C>A). Для рисунка 2 — это по часовой стрелки, но для рисунка 3 — это против часовой.

Так вот, в случае рисунка 3 точка должна лежать по левую сторону векторов, чтобы принадлежать треугольнику.

Вот тут и получается важный момент! Если вы уверены, что в вашем проекте все треугольники будут ориентированы по часовой стрелке(а т.е. вершина C будет всегда правее вектора AB), то вам можно закомментировать блок универсального решения и раскомментировать блок «для строгой ориентации по часовой» и данный алгоритм упрощается аж на 3 логических операции!

Векторный метод

Третий метод который я освещаю для меня самый интересный.

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

Данный метод я сначала проверил на бумаге. После всех оптимизаций формул, как всё сошлось, я реализовал его в коде, где он показал себя вполне успешным и результативным. Аж эффективнее 2-х предыдущих методов :]

1) одну вершину треугольника помещаем в координаты (0;0);

2) две стороны, выходящие из этой вершины, представляем как вектора.

Таким образом из всего этого появляется система простых условий нахождения точки P между векторами b и c.(рис. 4)

Рис. 4.

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

Принадлежность произвольной точки полигону

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

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

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

Метод сравнения площадей

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

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

Затем находится площадь самого полигона. Найденные площади сравниваются — если сумма трёх площадей равна площади всего полигона, то значит точка принадлежит полигону.

ввод координат точки в виде кортежей вида (x, y);
определить принадлежности точки полигону;

Входные данные	Выходные данные
True
True
False
True
True
True
True
False
False
False
True
True

Полученный мною опыт

Опыт работы с языком Python 3;
Обработка исключений при неправильном вводе входных параметров;
Вспомнил школьный курс геометрии.

About

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

[spoiler title=”источники:”]

Определение принадлежности точки треугольнику

http://github.com/b0006/Point-in-polygon

[/spoiler]

Источник

Это геометрическая задача. Я геометрию уже смутно помню. Но придумал алгоритм и по нему написал сценарий:

Python

# для любой точки внутри треугольника ABC тангенс угла между 
# отрезком MB и осью X будет меньше b/a (если точка не лежит на 
# границе треугольника или за пределами треугольника.
# отсюда исходные требования:
# a > 0
# b > 0
# y/(a-x) < b/a
a = float(input('введите положительное число для "a": '))
b = float(input('введите положительное число для "b": '))
M = input('введите для точки "M" координаты X,Y: ').split(',')
X = float(M[0])
Y = float(M[1])
tan = b/a
if a>0 and b>0 and (Y/X < b/a):
    print('True')
else:
    print('False')

пример 1:
введите положительное число для “a”: 9.3
введите положительное число для “b”: 4.231
введите для точки “M” координаты X,Y: 3.54,1.42
True

пример2:
введите положительное число для “a”: 9.3
введите положительное число для “b”: 4.231
введите для точки “M” координаты X,Y: 6.33,3.134
False

Добавлено через 14 минут
Сорри, случайно дал первый вариант, который с ошибкой. Вот верный:

Python

# для любой точки внутри треугольника ABC тангенс угла между 
# отрезком MB и осью X будет меньше b/a (если точка не лежит на 
# границе треугольника или за пределами треугольника.
# отсюда исходные требования:
# a > 0
# b > 0
# y/(a-x) < b/a
a = float(input('введите положительное число для "a": '))
b = float(input('введите положительное число для "b": '))
M = input('введите для точки "M" координаты X,Y: ').split(',')
X = float(M[0])
Y = float(M[1])
tan = b/a
if a>0 and b>0 and (Y/(a-X) < b/a):
    print('True')
else:
    print('False')

Добавлено через 18 минут
Сорри, и второй вариант не правильный, я в нем забыл исключить отрицательные координаты у точки M. Даю еще один вариант, надеюсь он последний:

Python

# для любой точки внутри треугольника ABC тангенс угла между 
# отрезком MB и осью X будет меньше b/a (если точка не лежит на 
# границе треугольника или за пределами треугольника.
# отсюда исходные требования:
# a > 0
# b > 0
# X > 0
# Y > 0
# y/(a-X) < b/a
a = float(input('введите положительное число для "a": '))
b = float(input('введите положительное число для "b": '))
M = input('введите для точки "M" положительные координаты X,Y: ').split(',')
X = float(M[0])
Y = float(M[1])
tan = b/a
if a>0 and b>0 and X>0 and Y>0 and (Y/(a-X) < b/a):
    print('True')
else:
    print('False')

Надеюсь, что этот вариант уже все предусматривает.

Добавлено через 4 минуты
пример3:
введите положительное число для “a”: 9.3
введите положительное число для “b”: 4.231
введите для точки “M” положительные координаты X,Y: -6.33,-3.134
False

Источник

C++

C

Java

Python

C#

PHP

Javascript

C++

Java

Python3

Javascript

Python Basic – 1: Упражнение 40 с решением

Python: проверьте, находится ли точка (x, y) в треугольнике или нет

Python Basic – 1: Упражнение 40 с решением

Определение принадлежности точки треугольнику

Метод сравнения площадей

Метод относительности

Всё относительно!

Векторный метод

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

About

Вам также может понравиться

Как составьте уравнение прямой

Память не может быть виден windows 7 как исправить

Как найти симку ростелеком

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