Jak ustalić, czy punkt znajduje się w trójkącie 2D? [Zamknięte]


258

Czy istnieje prosty sposób ustalenia, czy punkt znajduje się w trójkącie? Jest 2D, a nie 3D.


15
Napisałem pełny artykuł o punkcie w teście trójkąta. Pokazuje metody barycentryczne, parametryczne i oparte na iloczynie punktowym. Następnie zajmuje się problemem dokładności występującym, gdy punkt leży dokładnie na jednej krawędzi (z przykładami). Wreszcie ujawnia całkowicie nową metodę opartą na odległości od krawędzi do krawędzi. totologic.blogspot.fr/2014/01/... Ciesz się!
Logika


1
Warto zauważyć, że wszelkie omawiane tutaj metody są również ważne w przestrzeni 3D. Trzeba je tylko poprzedzić transformacją współrzędnych (i odpowiednim rzutem punktu na płaszczyznę trójkąta). Trójkąt to obiekt dwuwymiarowy.
andreasdr

Dla rozwiązania niezależnego od kolejności nawijania. Oto działające skrzypce: jsfiddle.net/ibowankenobi/oex3pzq2
ibrahim tanyalcin

2
Głosuję za zamknięciem tego pytania, ponieważ dotyczy matematyki, a nie programowania, i opiera się na opiniach (co jest dla ciebie „łatwe”?).
TylerH

Odpowiedzi:


264

Zasadniczo najprostszym (i dość optymalnym) algorytmem jest sprawdzenie, po której stronie półpłaszczyzny utworzonej przez krawędzie znajduje się punkt.

Oto informacje o wysokiej jakości w tym temacie na GameDev , w tym problemy z wydajnością.

Oto kod na początek:

float sign (fPoint p1, fPoint p2, fPoint p3)
{
    return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}

bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
    float d1, d2, d3;
    bool has_neg, has_pos;

    d1 = sign(pt, v1, v2);
    d2 = sign(pt, v2, v3);
    d3 = sign(pt, v3, v1);

    has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
    has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);

    return !(has_neg && has_pos);
}

12
Jest powszechnie stosowany w 2D. Współrzędne barycentryczne mylą ludzi. Biorąc również pod uwagę współrzędne trójkąta i punkt cordinate, nie jestem pewien skuteczności stosowania barycentrycznych.
Kornel Kisielewicz

7
@Kornel Wersja barycentryczna jest również bardziej wydajna w 2D. Twoje rozwiązanie ma również problem polegający na tym, że zgłosi inny wynik dla punktów dokładnie na krawędziach trójkąta, w zależności od tego, czy trójkąt jest określony w kolejności zgodnej z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara.
Andreas Brinck

9
Na moje potrzeby (powód, dla którego znalazłem tę stronę) oryginalna odpowiedź zaproponowana przez Kornela Kisielewicza jest znacznie wydajniejsza. Pracuję z wyświetlaczem LCD o współrzędnych wielkości BYTE i bardzo typowym mikroprocesorem, w którym mnożenie liczb całkowitych jest bardzo szybką instrukcją, a dzielenie jest znacznie, dużo, wolniejsze. Kwestie numeryczne są również znacznie mniejsze, ze względu na brak podziału! wszystkie obliczenia są dokładne. Dzięki, Rick

4
Więc funkcja sign () mówi ci, która strona półpłaszczyzny (utworzona przez linię między p2 i p3) p1 jest?
David Doria,

1
Zauważ, że jeśli przyjmujesz pewną kolejność wierzchołków (powiedz przeciwnie do ruchu wskazówek zegara), nie musisz cały czas obliczać wszystkich tych wyznaczników. W najlepszym wypadku wystarczy 1 wyznacznik, aby stwierdzić, że punkt nie znajduje się w trójkącie.
Thash

176

Rozwiąż następujący układ równań:

p = p0 + (p1 - p0) * s + (p2 - p0) * t

Punkt pznajduje się wewnątrz trójkąta jeśli 0 <= s <= 1i 0 <= t <= 1i s + t <= 1.

s, tI 1 - s - tnazywane są barycentryczne współrzędne tego punktu p.


1
Jest to szybsze niż sprawdzanie na półpłaszczyźnie, ale być może nieco trudniejsze do uchwycenia, jeśli nie znasz współrzędnych barycentrycznych.
Daniel Rikowski,

8
Dzięki trywialnym wyjściom (nie zaimplementowanym) w metodzie Kornela, jego może być znacznie wydajniejszy niż twój. Jeśli faktycznie spróbujesz obliczyć s i t, będziesz wiedział, co mam na myśli.

85
Chciałem to przetestować, więc zrobiłem jsfiddle, opierając się na rozwiązaniu @andreasdr i komentarzu coproc
urraka

5
Optymalizacja: s + t <= 1implikuje s <= 1i t <= 1czy s >= 0i t >= 0.
Thomas Eding

7
Artykuł totologic.blogspot.fr/2014/01/... zaproponowany przez post @Logic pomógł mi lepiej zrozumieć to rozwiązanie
Flayn

112

Zgadzam się z Andreasem Brinckiem , współrzędne barycentryczne są bardzo wygodne do tego zadania. Zauważ, że nie ma potrzeby rozwiązywania układu równań za każdym razem: wystarczy ocenić rozwiązanie analityczne. Korzystając z notacji Andreasa , rozwiązaniem jest:

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

gdzie Areajest (podpisany) obszar trójkąta:

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

Wystarczy ocenić s, ta 1-s-t. Punkt pznajduje się w trójkącie tylko wtedy, gdy wszystkie są dodatnie.

EDYCJA: Zauważ, że powyższe wyrażenie dla obszaru zakłada, że ​​numeracja węzłów trójkąta jest przeciwna do ruchu wskazówek zegara. Jeśli numeracja jest zgodna z ruchem wskazówek zegara, to wyrażenie zwróci obszar ujemny (ale z poprawną wielkością). Sam test ( s>0 && t>0 && 1-s-t>0) nie zależy jednak od kierunku numeracji, ponieważ powyższe wyrażenia są mnożone przez 1/(2*Area)znak zmiany również w przypadku zmiany orientacji węzła trójkąta.

EDYCJA 2: Aby uzyskać jeszcze lepszą wydajność obliczeniową, zobacz komentarz Coproc poniżej (który wskazuje, że jeśli orientacja węzłów trójkąta (zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara) jest wcześniej znana, podział według 2*Areawyrażeń dla si tmoże być unikane). Zobacz także kod jsfiddle Perro Azula w komentarzach pod odpowiedzią Andreasa Brincka .


6
Że jest rozwiązywanie układu równań :)
Andreas Brinck

1
Tak, mam na myśli to, że każda krytyka twojej metody oparta na kosztach obliczeniowych rozwiązania układu równań jest bezzasadna, ponieważ nie musi to być robione jako część algorytmu.
andreasdr,

13
Wydajność można poprawić, nie dzieląc 2*Area, tj. Obliczając s´=2*|Area|*si t´=2*|Area|*t(jeśli orientacja punktów - zgodnie z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara - nie jest znana, znak znaku Areanależy oczywiście sprawdzić, ale w przeciwnym razie może nawet nie trzeba obliczyć), ponieważ do sprawdzenia s>0wystarczy sprawdzić s´>0. I zamiast sprawdzania 1-s-t>0wystarczy sprawdzić s´+t´<2*|Area|.
coproc

1
Mogę dodać, że jeśli w kartezjańskimp0->p1->p2 jest przeciwny do ruchu wskazówek zegara (który zwykle ma współrzędne ekranu zgodnie z ruchem wskazówek zegara ), obliczona tą metodą będzie dodatnia. Area
rhgb

1
@ user2600366 Podczas podróży wzdłuż granicy trójkąta w kierunku p0 -> p1 -> p2 -> p0 itd. wnętrze trójkąta będzie zawsze po prawej lub zawsze po lewej stronie. W pierwszym przypadku numeracja jest zgodna z ruchem wskazówek zegara, w drugim przypadku jest przeciwna do ruchu wskazówek zegara.
andreasdr

47

Napisałem ten kod przed ostatnią próbą znalezienia tej strony w Google, więc pomyślałem, że go podzielę. Jest to w zasadzie zoptymalizowana wersja odpowiedzi Kisielewicza. Przyjrzałem się również metodzie barycentrycznej, ale sądząc z artykułu z Wikipedii, trudno mi się przekonać, w jaki sposób jest bardziej wydajna (domyślam się, że istnieje głębsza równoważność). W każdym razie ten algorytm ma tę zaletę, że nie używa dzielenia; potencjalnym problemem jest zachowanie detekcji krawędzi w zależności od orientacji.

bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
    int as_x = s.x-a.x;
    int as_y = s.y-a.y;

    bool s_ab = (b.x-a.x)*as_y-(b.y-a.y)*as_x > 0;

    if((c.x-a.x)*as_y-(c.y-a.y)*as_x > 0 == s_ab) return false;

    if((c.x-b.x)*(s.y-b.y)-(c.y-b.y)*(s.x-b.x) > 0 != s_ab) return false;

    return true;
}

Innymi słowy, idea jest następująca: czy punkt jest na lewo, czy na prawo od linii AB i AC? Jeśli to prawda, nie może być w środku. Jeśli false, to przynajmniej w „stożkach”, które spełniają ten warunek. Ponieważ wiemy, że punkt w trygonie (trójkącie) musi znajdować się po tej samej stronie AB co BC (a także CA), sprawdzamy, czy się różnią. Jeśli tak, to nie może być w środku, w przeciwnym razie musi być w środku.

Niektóre słowa kluczowe w obliczeniach to półpłaszczyzny linii i wyznacznik (iloczyn krzyżowy 2x2). Być może bardziej pedagogicznym sposobem jest prawdopodobnie myślenie o tym jako o punkcie znajdującym się wewnątrz, jeśli jest po tej samej stronie (lewej lub prawej) każdej linii AB, BC i CA. Powyższy sposób wydawał się jednak bardziej odpowiedni do optymalizacji.


2
Ten test jest około 140-180% szybszy niż pierwszy podany (dzięki wam oboje btw :). Uruchomiłem kod tutaj: paste.ubuntu.com/p/k5w7ywH4p8 przy użyciu silnika nodejs v8 z wyłączonymi optymalizacjami i uzyskałem następujące wyniki:: w! Node -p - minimalny test1: 114,852ms test2: 64.330ms test1: 115.650ms test2: 63.491ms test1: 117.671ms test2: 65.353ms test1: 119.146ms test2: 63.871ms test1: 118.271ms test1: 118.670ms test2: 63.352ms
chirurgemcgee

@surgemcgee dlaczego miałbyś go uruchomić bez optymalizacji? Czy to nie jest bardziej usuwane z rzeczywistości?
xuiqzy

@xuiqzy Cóż, mój program zawiera dwa różne rozwiązania. Muszę jeszcze podać najszybszą metodę tego. Być może ten komentarz powinien zostać usunięty i zastąpiony moimi ukończonymi pracami na ten temat ...
operacja chirurgiczna

33

Wersja C # metody barycentrycznej opublikowana przez andreasdr i Perro Azul. Należy pamiętać, że kalkulacja obszar można uniknąć, jeśli si tmają przeciwne znaki. Sprawdziłem prawidłowe zachowanie za pomocą dość dokładnego testu jednostkowego.

public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
    var s = p0.Y * p2.X - p0.X * p2.Y + (p2.Y - p0.Y) * p.X + (p0.X - p2.X) * p.Y;
    var t = p0.X * p1.Y - p0.Y * p1.X + (p0.Y - p1.Y) * p.X + (p1.X - p0.X) * p.Y;

    if ((s < 0) != (t < 0))
        return false;

    var A = -p1.Y * p2.X + p0.Y * (p2.X - p1.X) + p0.X * (p1.Y - p2.Y) + p1.X * p2.Y;

    return A < 0 ?
            (s <= 0 && s + t >= A) :
            (s >= 0 && s + t <= A);
}

[ edytuj ]
zaakceptował sugerowaną modyfikację @Pierre; Zobacz komentarze


Rozwiązanie z zakończeniem if działa dla punktów trójkąta zgodnych z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara.
Luke Dupin,

@LukeDupin Nie jestem pewien, czy rozumiem twój komentarz. Ta odpowiedź działa jak w przypadku każdego dostarczonego zamówienia 3 punktów.
Glenn Slayden,

12

Wersja barycentryczna metody Java:

class Triangle {
    Triangle(double x1, double y1, double x2, double y2, double x3,
            double y3) {
        this.x3 = x3;
        this.y3 = y3;
        y23 = y2 - y3;
        x32 = x3 - x2;
        y31 = y3 - y1;
        x13 = x1 - x3;
        det = y23 * x13 - x32 * y31;
        minD = Math.min(det, 0);
        maxD = Math.max(det, 0);
    }

    boolean contains(double x, double y) {
        double dx = x - x3;
        double dy = y - y3;
        double a = y23 * dx + x32 * dy;
        if (a < minD || a > maxD)
            return false;
        double b = y31 * dx + x13 * dy;
        if (b < minD || b > maxD)
            return false;
        double c = det - a - b;
        if (c < minD || c > maxD)
            return false;
        return true;
    }

    private final double x3, y3;
    private final double y23, x32, y31, x13;
    private final double det, minD, maxD;
}

Powyższy kod będzie działał dokładnie z liczbami całkowitymi, przy założeniu braku przepełnienia. Działa również z trójkątami zgodnymi z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara. Nie będzie działać z trójkątami współliniowymi (ale możesz to sprawdzić, testując det == 0).

Wersja barycentryczna jest najszybsza, jeśli zamierzasz przetestować różne punkty za pomocą tego samego trójkąta.

Wersja barycentryczna nie jest symetryczna w 3 punktach trójkąta, więc prawdopodobnie będzie mniej spójna niż wersja półpłaszczyznowa Kornela Kisielewicza z powodu błędów zaokrąglania zmiennoprzecinkowego.

Credit: Powyższy kod zrobiłem z artykułu Wikipedii na temat współrzędnych barycentrycznych.


Miły ! Można nawet ulepszyć użycie krotek Point3f / Point2f javax.vecmath, aby lepiej obsługiwać wprowadzanie danych.
Alex Byrth

10

Prostym sposobem jest:

znajdź wektory łączące punkt z każdym z trzech wierzchołków trójkąta i zsumuj kąty między tymi wektorami. Jeśli suma kątów wynosi 2 * pi, to punkt znajduje się w trójkącie.

Dwie dobre strony wyjaśniające alternatywy to:

blackpawn i wolfram


3
Ta metoda nie jest dokładnie wydajna i jest bardzo podatna na błędy numeryczne ...
Kornel Kisielewicz

Wręcz przeciwnie, jest bardzo nieefektywny :-) To tylko jeden prosty sposób, łatwy do wdrożenia. Czy możesz podać przykład błędu numerycznego, który może to spowodować?
Simon P Stevens,

Chociaż wydaje mi się, że jest to po prostu najlepsza ze wszystkich odpowiedzi w tym temacie, wydaje mi się, że punkty na krawędziach trójkąta są uwzględnione w trójkącie i nie masz na to solidnej kontroli.
Redu,

sprawdzanie, czy to dokładnie 2pi, jest liczbowo niemożliwe, biorąc pod uwagę irracjonalność pi. Wystarczy jednak sprawdzić, czy kąty sumują się do czegoś większego niż pi.
lonewarrior556

10

Stosując rozwiązanie analityczne do współrzędnych barycentrycznych (wskazane przez Andreasa Brincka ) i:

  • nie dystrybuuje mnożenia w nawiasach
  • unikając wielokrotnego obliczania tych samych terminów przez ich przechowywanie
  • redukowanie porównań (jak wskazali Coproc i Thomas Eding )

Można zminimalizować liczbę „kosztownych” operacji:

function ptInTriangle(p, p0, p1, p2) {
    var dX = p.x-p2.x;
    var dY = p.y-p2.y;
    var dX21 = p2.x-p1.x;
    var dY12 = p1.y-p2.y;
    var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
    var s = dY12*dX + dX21*dY;
    var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
    if (D<0) return s<=0 && t<=0 && s+t>=D;
    return s>=0 && t>=0 && s+t<=D;
}

Kod można wkleić w jsfiddle Perro Azul lub wypróbować go, klikając „Uruchom fragment kodu” poniżej

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    var sign = A < 0 ? -1 : 1;
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
    
    return s > 0 && t > 0 && (s + t) < 2 * A * sign;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Prowadzący do:

  • zmienna „przypomina”: 30
  • przechowywanie zmiennych: 7
  • dodatki: 4
  • odejmowanie: 8
  • mnożenia: 6
  • podziały: brak
  • porównania: 4

Porównuje się to całkiem dobrze z rozwiązaniem Kornela Kisielewicza (25 odwołań, 1 pamięć, 15 odejmowań, 6 mnożeń, 5 porównań), a może być jeszcze lepsze, jeśli konieczne jest wykrywanie zgodnie z ruchem wskazówek zegara / przeciwnie do ruchu wskazówek zegara (co wymaga 6 odwołań, 1 dodania, 2 odejmowań , 2 multiplikacje i 1 porównanie samo w sobie, przy użyciu analitycznego wyznacznika rozwiązania, jak wskazał rhgb ).


Niezłe rozwiązanie. Wydaje
Jack D'Aurizio

Właśnie przetestowałem kod w obecnej postaci i nie działa on dla mnie (przykład p -4.69317198, -6.99191951 p0 -7.05846786 0,596718192 p1 -6.8703599 -2.36565161 p2 -4.69317198, -6.99191951)
Giovanni Funchal

@ GiovanniFunchal Dziwne, twój przykład działa dla mnie, zarówno w jsfiddle (zastąp początkowe definicje „punkt” i „trójkąt”), jak i mojej lokalnej implementacji Pythona. Problemy z precyzją numeryczną (spróbuj usunąć niektóre miejsca po przecinku)?
Cédric Dufour,

1
Twój wydaje się najszybszy w moim teście: jsfiddle.net/eyal/gxw3632c/27 . Różnica między wszystkimi metodami jest jednak niewielka.
Eyal

Wypróbuj trójkąt (-1, -1), (1, -1), (0,1) i punkt (0, -1). Zwraca false, gdy powinna zwrócić true, ponieważ s (2) + t (2)> d (2). Wydaje się, że coś jest nie tak z matematyką na krawędziach trójkąta, ponieważ punkt p znajduje się na granicy między p0 i p1 i nie jest to prosta kwestia przekształcenia <w <= lub coś w tym rodzaju.
devnullicus

5

To, co robię, polega na wstępnym obliczeniu trzech normalnych twarzy,

  • w 3D przez iloczyn wektorowy wektora bocznego i normalnego wektora twarzy.

  • w 2D po prostu zamieniając komponenty i negując jeden,

wtedy wewnątrz / na zewnątrz dla jednej strony występuje iloczyn punktowy strony normalnej i wierzchołka do wektora punktowego, zmiana znaku. Powtórz dla pozostałych dwóch (lub więcej) stron.

Korzyści:

  • wiele jest wstępnie obliczonych, więc świetnie nadaje się do testowania wielu punktów na tym samym trójkącie.

  • wczesne odrzucenie częstego przypadku większej liczby punktów zewnętrznych niż wewnętrznych. (również jeśli rozkład punktów jest ważony z jednej strony, można najpierw przetestować tę stronę).


5

Oto wydajna implementacja Pythona :

def PointInsideTriangle2(pt,tri):
    '''checks if point pt(2) is inside triangle tri(3x2). @Developer'''
    a = 1/(-tri[1,1]*tri[2,0]+tri[0,1]*(-tri[1,0]+tri[2,0])+ \
        tri[0,0]*(tri[1,1]-tri[2,1])+tri[1,0]*tri[2,1])
    s = a*(tri[2,0]*tri[0,1]-tri[0,0]*tri[2,1]+(tri[2,1]-tri[0,1])*pt[0]+ \
        (tri[0,0]-tri[2,0])*pt[1])
    if s<0: return False
    else: t = a*(tri[0,0]*tri[1,1]-tri[1,0]*tri[0,1]+(tri[0,1]-tri[1,1])*pt[0]+ \
              (tri[1,0]-tri[0,0])*pt[1])
    return ((t>0) and (1-s-t>0))

i przykładowy wynik:

wprowadź opis zdjęcia tutaj


Nie byłem w stanie sprawić, by to zadziałało, na przykład dla punktu w trójkącie [(0,0), (3,0), (3,4)], ani punktów (1,1) ani (0 , 0) pozytywny wynik testu. Próbowałem z trójkątnymi punktami zarówno zgodnie z ruchem wskazówek zegara, jak i przeciwnie do ruchu wskazówek zegara.
ThorSummoner

3

Jeśli szukasz prędkości, oto procedura, która może ci pomóc.

Posortuj wierzchołki trójkąta według ich rzędnych. To zajmuje w najgorszym przypadku trzy porównania. Niech Y0, Y1, Y2 będą trzema posortowanymi wartościami. Rysując przez nie trzy poziomy, dzielisz płaszczyznę na dwie półpłaszczyzny i dwie płyty. Niech Y będzie rzędną punktu zapytania.

if Y < Y1
    if Y <= Y0 -> the point lies in the upper half plane, outside the triangle; you are done
    else Y > Y0 -> the point lies in the upper slab
else
    if Y >= Y2 -> the point lies in the lower half plane, outside the triangle; you are done
    else Y < Y2 -> the point lies in the lower slab

Kosztuje dwa kolejne porównania. Jak widać, szybkie odrzucenie jest osiągane dla punktów poza „płytą ograniczającą”.

Opcjonalnie możesz dostarczyć test na odciętych w celu szybkiego odrzucenia po lewej i po prawej stronie ( X <= X0' or X >= X2'). To wdroży jednocześnie szybki test ramki granicznej, ale musisz też posortować wyniki na odciętych.

W końcu będziesz musiał obliczyć znak danego punktu w odniesieniu do dwóch boków trójkąta, które wyznaczają odpowiednią płytę (górną lub dolną). Test ma postać:

((X - Xi) * (Y - Yj) > (X - Xi) * (Y - Yj)) == ((X - Xi) * (Y - Yk) > (X - Xi) * (Y - Yk))

Pełna dyskusja na temat i, j, kkombinacji (jest ich sześć, w zależności od wyniku tego rodzaju) jest poza zakresem tej odpowiedzi i „pozostawiona czytelnikowi jako ćwiczenie”; dla wydajności powinny być zakodowane na stałe.

Jeśli uważasz, że to rozwiązanie jest złożone, zauważ, że obejmuje ono głównie proste porównania (niektóre z nich można wstępnie obliczyć), a także 6 odejmowań i 4 mnożeń w przypadku niepowodzenia testu ramki granicznej. Ten ostatni koszt jest trudny do pokonania, ponieważ w najgorszym przypadku nie można uniknąć porównania punktu testowego z dwiema stronami (żadna metoda w innych odpowiedziach nie ma niższego kosztu, niektóre pogarszają, na przykład 15 odejmowań i 6 mnożeń, czasem podziałów).

AKTUALIZACJA: Szybsza dzięki transformacji ścinającej

Jak wyjaśniono powyżej, możesz szybko zlokalizować punkt w jednym z czterech poziomych pasm wyznaczonych przez trzy rzędne wierzchołków, używając dwóch porównań.

Opcjonalnie możesz wykonać jeden lub dwa dodatkowe testy X, aby sprawdzić nieświadomość obwiedni (linie przerywane).

Następnie rozważ transformację „ścinania” podaną przez X'= X - m Y, Y' = Y, gdzie mjest nachylenie DX/DYdla najwyższej krawędzi. Ta transformacja sprawi, że ta strona trójkąta będzie pionowa. A ponieważ wiesz, po której stronie środkowego poziomu jesteś, wystarczy przetestować znak w odniesieniu do pojedynczej strony trójkąta.

wprowadź opis zdjęcia tutaj

Zakładając, że wstępnie obliczyłeś nachylenie m, a także X'ścinane wierzchołki trójkąta i współczynniki równań boków, ponieważ X = m Y + pw najgorszym przypadku będziesz potrzebować

  • dwa rzędne porównania do klasyfikacji pionowej;
  • opcjonalnie jedno lub dwa porównania odciętych dla odrzucenia ramki granicznej;
  • obliczanie X' = X - m Y;
  • jedno lub dwa porównania z odciętymi ściętego trójkąta;
  • test jednego znaku X >< m' Y + p'na odpowiedniej stronie ściętego trójkąta.

3

Jeśli znasz współrzędne trzech wierzchołków i współrzędne określonego punktu, możesz uzyskać obszar pełnego trójkąta. Następnie obliczyć powierzchnię trzech segmentów trójkąta (jeden punkt jest podanym punktem, a pozostałe dwa to dowolne dwa wierzchołki trójkąta). W ten sposób otrzymasz obszar trzech segmentów trójkąta. Jeśli suma tych obszarów jest równa całkowitej powierzchni (którą otrzymałeś wcześniej), to punkt powinien znajdować się wewnątrz trójkąta. W przeciwnym razie punkt nie znajduje się w trójkącie. To powinno działać. Jeśli są jakieś problemy, daj mi znać. Dziękuję Ci.


3

Inne funkcje w pythonie , szybsze niż metoda programisty (przynajmniej dla mnie) i zainspirowane rozwiązaniem Cédric Dufour :

def ptInTriang(p_test, p0, p1, p2):       
     dX = p_test[0] - p0[0]
     dY = p_test[1] - p0[1]
     dX20 = p2[0] - p0[0]
     dY20 = p2[1] - p0[1]
     dX10 = p1[0] - p0[0]
     dY10 = p1[1] - p0[1]

     s_p = (dY20*dX) - (dX20*dY)
     t_p = (dX10*dY) - (dY10*dX)
     D = (dX10*dY20) - (dY10*dX20)

     if D > 0:
         return (  (s_p >= 0) and (t_p >= 0) and (s_p + t_p) <= D  )
     else:
         return (  (s_p <= 0) and (t_p <= 0) and (s_p + t_p) >= D  )

Możesz to przetestować za pomocą:

X_size = 64
Y_size = 64
ax_x = np.arange(X_size).astype(np.float32)
ax_y = np.arange(Y_size).astype(np.float32)
coords=np.meshgrid(ax_x,ax_y)
points_unif = (coords[0].reshape(X_size*Y_size,),coords[1].reshape(X_size*Y_size,))
p_test = np.array([0 , 0])
p0 = np.array([22 , 8]) 
p1 = np.array([12 , 55]) 
p2 = np.array([7 , 19]) 
fig = plt.figure(dpi=300)
for i in range(0,X_size*Y_size):
    p_test[0] = points_unif[0][i]
    p_test[1] = points_unif[1][i]
    if ptInTriang(p_test, p0, p1, p2):
        plt.plot(p_test[0], p_test[1], '.g')
    else:
        plt.plot(p_test[0], p_test[1], '.r')

Wydrukowanie zajmuje dużo czasu, ale ta siatka jest testowana w 0,0195319652557 sekundach wobec 0,0844349861145 sekund kodu programisty .

Na koniec komentarz do kodu:

# Using barycentric coordintes, any point inside can be described as:
# X = p0.x * r + p1.x * s + p2.x * t
# Y = p0.y * r + p1.y * s + p2.y * t
# with:
# r + s + t = 1  and 0 < r,s,t < 1
# then: r = 1 - s - t
# and then:
# X = p0.x * (1 - s - t) + p1.x * s + p2.x * t
# Y = p0.y * (1 - s - t) + p1.y * s + p2.y * t
#
# X = p0.x + (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y = p0.y + (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# X - p0.x = (p1.x-p0.x) * s + (p2.x-p0.x) * t
# Y - p0.y = (p1.y-p0.y) * s + (p2.y-p0.y) * t
#
# we have to solve:
#
# [ X - p0.x ] = [(p1.x-p0.x)   (p2.x-p0.x)] * [ s ]
# [ Y - p0.Y ]   [(p1.y-p0.y)   (p2.y-p0.y)]   [ t ]
#
# ---> b = A*x ; ---> x = A^-1 * b
# 
# [ s ] =   A^-1  * [ X - p0.x ]
# [ t ]             [ Y - p0.Y ]
#
# A^-1 = 1/D * adj(A)
#
# The adjugate of A:
#
# adj(A)   =   [(p2.y-p0.y)   -(p2.x-p0.x)]
#              [-(p1.y-p0.y)   (p1.x-p0.x)]
#
# The determinant of A:
#
# D = (p1.x-p0.x)*(p2.y-p0.y) - (p1.y-p0.y)*(p2.x-p0.x)
#
# Then:
#
# s_p = { (p2.y-p0.y)*(X - p0.x) - (p2.x-p0.x)*(Y - p0.Y) }
# t_p = { (p1.x-p0.x)*(Y - p0.Y) - (p1.y-p0.y)*(X - p0.x) }
#
# s = s_p / D
# t = t_p / D
#
# Recovering r:
#
# r = 1 - (s_p + t_p)/D
#
# Since we only want to know if it is insidem not the barycentric coordinate:
#
# 0 < 1 - (s_p + t_p)/D < 1
# 0 < (s_p + t_p)/D < 1
# 0 < (s_p + t_p) < D
#
# The condition is:
# if D > 0:
#     s_p > 0 and t_p > 0 and (s_p + t_p) < D
# else:
#     s_p < 0 and t_p < 0 and (s_p + t_p) > D
#
# s_p = { dY20*dX - dX20*dY }
# t_p = { dX10*dY - dY10*dX }
# D = dX10*dY20 - dY10*dX20

Ta funkcja nie działa. Daj ptInTriang([11,45],[45, 45],[45, 45] ,[44, 45])i wróci, truechoć jest to fałsz
Kodeks Papież

3

Ponieważ nie ma odpowiedzi JS, rozwiązanie
zgodne z ruchem wskazówek zegara i przeciwnie do ruchu wskazówek zegara:

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)

    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}

EDYCJA: literówka do obliczeń det ( cy - ayzamiast cx - ax), to jest naprawione.

https://jsfiddle.net/jniac/rctb3gfL/

function triangleContains(ax, ay, bx, by, cx, cy, x, y) {

    let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
	
    return  det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
            det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
            det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0 

}






let width = 500, height = 500

// clockwise
let triangle1 = {

	A : { x: 10, y: -10 },
	C : { x: 20, y: 100 },
	B : { x: -90, y: 10 },
	
	color: '#f00',

}

// counter clockwise
let triangle2 = {

	A : { x: 20, y: -60 },
	B : { x: 90, y: 20 },
	C : { x: 20, y: 60 },

	color: '#00f',
	
}


let scale = 2
let mouse = { x: 0, y: 0 }






// DRAW >

let wrapper = document.querySelector('div.wrapper')

wrapper.onmousemove = ({ layerX:x, layerY:y }) => {
	
	x -= width / 2
	y -= height / 2
	x /= scale
	y /= scale
	
	mouse.x = x
	mouse.y = y
	
	drawInteractive()

}

function drawArrow(ctx, A, B) {

	let v = normalize(sub(B, A), 3)
	let I = center(A, B)
	
	let p
	
	p = add(I, rotate(v, 90), v)
	ctx.moveTo(p.x, p.y)
	ctx.lineTo(I.x, I .y)
	p = add(I, rotate(v, -90), v)
	ctx.lineTo(p.x, p.y)

}

function drawTriangle(ctx, { A, B, C, color }) {

	ctx.beginPath()
	ctx.moveTo(A.x, A.y)
	ctx.lineTo(B.x, B.y)
	ctx.lineTo(C.x, C.y)
	ctx.closePath()
	
	ctx.fillStyle = color + '6'
	ctx.strokeStyle = color
	ctx.fill()
	
	drawArrow(ctx, A, B)
	drawArrow(ctx, B, C)
	drawArrow(ctx, C, A)
	
	ctx.stroke()

}

function contains({ A, B, C }, P) {

	return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y)

}

function resetCanvas(canvas) {

	canvas.width = width
	canvas.height = height
	
	let ctx = canvas.getContext('2d')

	ctx.resetTransform()
	ctx.clearRect(0, 0, width, height)
	ctx.setTransform(scale, 0, 0, scale, width/2, height/2)
	
}

function drawDots() {

	let canvas = document.querySelector('canvas#dots')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	let count = 1000

	for (let i = 0; i < count; i++) {

		let x = width * (Math.random() - .5)
		let y = width * (Math.random() - .5)
		
		ctx.beginPath()
		ctx.ellipse(x, y, 1, 1, 0, 0, 2 * Math.PI)
		
		if (contains(triangle1, { x, y })) {
		
			ctx.fillStyle = '#f00'
		
		} else if (contains(triangle2, { x, y })) {
		
			ctx.fillStyle = '#00f'
		
		} else {
		
			ctx.fillStyle = '#0003'
		
		}

		
		ctx.fill()
		
	}
	
}

function drawInteractive() {

	let canvas = document.querySelector('canvas#interactive')
	let ctx = canvas.getContext('2d')

	resetCanvas(canvas)
	
	ctx.beginPath()
	ctx.moveTo(0, -height/2)
	ctx.lineTo(0, height/2)
	ctx.moveTo(-width/2, 0)
	ctx.lineTo(width/2, 0)
	ctx.strokeStyle = '#0003'
	ctx.stroke()
	
	drawTriangle(ctx, triangle1)
	drawTriangle(ctx, triangle2)
	
	ctx.beginPath()
	ctx.ellipse(mouse.x, mouse.y, 4, 4, 0, 0, 2 * Math.PI)
	
	if (contains(triangle1, mouse)) {
	
		ctx.fillStyle = triangle1.color + 'a'
		ctx.fill()
		
	} else if (contains(triangle2, mouse)) {
	
		ctx.fillStyle = triangle2.color + 'a'
		ctx.fill()
		
	} else {
	
		ctx.strokeStyle = 'black'
		ctx.stroke()
		
	}
	
}

drawDots()
drawInteractive()










// trigo

function add(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	return { x, y }

}

function center(...points) {
	
	let x = 0, y = 0
	
	for (let point of points) {
	
		x += point.x
		y += point.y
	
	}
	
	x /= points.length
	y /= points.length
	
	return { x, y }

}

function sub(A, B) {

	let x = A.x - B.x
	let y = A.y - B.y
	
	return { x, y }

}

function normalize({ x, y }, length = 10) {

	let r = length / Math.sqrt(x * x + y * y)
	
	x *= r
	y *= r
	
	return { x, y }

}

function rotate({ x, y }, angle = 90) {

	let length = Math.sqrt(x * x + y * y)
	
	angle *= Math.PI / 180
	angle += Math.atan2(y, x)
	
	x = length * Math.cos(angle)
	y = length * Math.sin(angle)
	
	return { x, y }

}
* {
	margin: 0;
}

html {
	font-family: monospace;
}

body {
	padding: 32px;
}

span.red {
	color: #f00;
}

span.blue {
	color: #00f;
}

canvas {
	position: absolute;
	border: solid 1px #ddd;
}
<p><span class="red">red triangle</span> is clockwise</p>
<p><span class="blue">blue triangle</span> is couter clockwise</p>
<br>
<div class="wrapper">
	<canvas id="dots"></canvas>
	<canvas id="interactive"></canvas>
</div>

wprowadź opis zdjęcia tutaj

Używam tutaj tej samej metody, jak opisano powyżej: punkt znajduje się wewnątrz ABC, jeśli jest odpowiednio po „tej samej” stronie każdej linii AB, BC, CA.

przykład włączenia trójkąta


Zmęczyłem ten kod i nie działa. Zawsze zwraca Fałsz.
xApple

hmmm ... prawdopodobnie popełniłeś błąd. Oto skrzypce z działającą funkcją: jsfiddle.net/jniac/rctb3gfL
Joseph Merdrignac

widziałem twoją odpowiedź w Pythonie, używamy tej samej metody, jeśli użyję jeszcze jednej linii ( let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)), służy to określeniu kolejności nawijania trójkątów, więc metoda będzie działać z trójkątami CW i CCW (patrz jsFiddle).
Joseph Merdrignac

1
hm popełniłem błąd, napisałem: let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)zamiast let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)tego jest naprawiony, dzięki za zgłoszenie
Joseph Merdrignac

2

Chcę tylko użyć prostej matematyki wektorowej, aby wyjaśnić rozwiązanie współrzędnych barycentrycznych, które podał Andreas, będzie o wiele łatwiejsze do zrozumienia.

  1. Obszar A jest definiowany jako dowolny wektor podany przez s * v02 + t * v01, z warunkiem s> = 0 it> 0. Jeśli dowolny punkt wewnątrz trójkąta v0, v1, v2, musi znajdować się w obszarze A.

wprowadź opis zdjęcia tutaj

  1. Jeśli dodatkowo ograniczysz s, i t należy do [0, 1]. Otrzymujemy Obszar B, który zawiera wszystkie wektory s * v02 + t * v01, z warunkiem s, t należy do [0, 1]. Warto zauważyć, że dolna część obszaru B to lustro trójkąta v0, v1, v2. Problem pojawia się, jeśli możemy podać pewne warunki s, i t, w celu dalszego wykluczenia niskiej części obszaru B.

wprowadź opis zdjęcia tutaj

  1. Załóżmy, że podajemy wartość s, a t zmienia się w [0, 1]. Na poniższym zdjęciu punkt p znajduje się na krawędzi v1v2. Wszystkie wektory s * v02 + t * v01, które są wzdłuż linii myślnika za pomocą prostej sumy wektorów. W punkcie v1v2 i punkcie przecięcia linii przerywanej p mamy:

(1-s) | v0v2 | / | v0v2 | = tp | v0v1 | / | v0v1 |

otrzymujemy 1 - s = tp, a następnie 1 = s + tp. Jeśli dowolny t> tp, którego 1 <s + t jest na linii podwójnej kreski, wektor znajduje się poza trójkątem, dowolny t <= tp, który 1> = s + t gdzie jest na linii pojedynczej kreski, wektor jest wewnątrz trójkąta.

Zatem jeśli podamy dowolne s w [0, 1], odpowiadające t musi spełniać 1> = s + t, dla wektora wewnątrz trójkąta.

wprowadź opis zdjęcia tutaj

W końcu otrzymujemy v = s * v02 + t * v01, v znajduje się w trójkącie z warunkiem s, t, s + t należy do [0, 1]. Następnie przetłumacz na punkt, mamy

p - p0 = s * (p1 - p0) + t * (p2 - p0), przy s, t, s + t w [0, 1]

który jest taki sam jak rozwiązanie Andreasa do rozwiązania układu równań p = p0 + s * (p1 - p0) + t * (p2 - p0), przy czym s, t, s + t należą do [0, 1].


Możesz po prostu powiedzieć, że używasz lokalnej ramki zdefiniowanej przez trzy wierzchołki, tak że boki stają się s = 0, t = 0 i s + t = 1. Afiniczna transformacja współrzędnych jest dobrze znaną operacją algebry liniowej.
Yves Daoust,

2

Oto rozwiązanie w Pythonie, które jest wydajne, udokumentowane i zawiera trzy unittests. Jest to profesjonalna jakość i jest gotowy do wprowadzenia do projektu w postaci modułu w obecnej postaci.

import unittest

###############################################################################
def point_in_triangle(point, triangle):
    """Returns True if the point is inside the triangle
    and returns False if it falls outside.
    - The argument *point* is a tuple with two elements
    containing the X,Y coordinates respectively.
    - The argument *triangle* is a tuple with three elements each
    element consisting of a tuple of X,Y coordinates.

    It works like this:
    Walk clockwise or counterclockwise around the triangle
    and project the point onto the segment we are crossing
    by using the dot product.
    Finally, check that the vector created is on the same side
    for each of the triangle's segments.
    """
    # Unpack arguments
    x, y = point
    ax, ay = triangle[0]
    bx, by = triangle[1]
    cx, cy = triangle[2]
    # Segment A to B
    side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
    # Segment B to C
    side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
    # Segment C to A
    side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
    # All the signs must be positive or all negative
    return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)

###############################################################################
class TestPointInTriangle(unittest.TestCase):

    triangle = ((22 , 8),
                (12 , 55),
                (7 , 19))

    def test_inside(self):
        point = (15, 20)
        self.assertTrue(point_in_triangle(point, self.triangle))

    def test_outside(self):
        point = (1, 7)
        self.assertFalse(point_in_triangle(point, self.triangle))

    def test_border_case(self):
        """If the point is exactly on one of the triangle's edges,
        we consider it is inside."""
        point = (7, 19)
        self.assertTrue(point_in_triangle(point, self.triangle))

###############################################################################
if __name__ == "__main__":
    suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
    unittest.TextTestRunner().run(suite)

Istnieje dodatkowy opcjonalny test graficzny dla powyższego algorytmu w celu potwierdzenia jego ważności:

import random
from matplotlib import pyplot
from triangle_test import point_in_triangle

###############################################################################
# The area #
size_x = 64
size_y = 64

# The triangle #
triangle = ((22 , 8),
            (12 , 55),
            (7 , 19))

# Number of random points #
count_points = 10000

# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)

# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))

# Plot the points #
for i in range(count_points):
    x = random.uniform(0, size_x)
    y = random.uniform(0, size_y)
    if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
    else:                                  pyplot.plot(x, y, '.b')

# Save it #
figure.savefig("point_in_triangle.pdf")

Produkcja następującej grafiki:

Przetestuj funkcję point_in_triangle


1

Są nieznośne warunki krawędziowe, w których punkt znajduje się dokładnie na wspólnej krawędzi dwóch sąsiadujących trójkątów. Punkt nie może znajdować się w obu, ani w żadnym z trójkątów. Potrzebujesz arbitralnego, ale spójnego sposobu przypisywania punktu. Na przykład narysuj poziomą linię przez punkt. Jeśli linia przecina się z drugą stroną trójkąta po prawej stronie, punkt jest traktowany tak, jakby znajdował się w trójkącie. Jeśli skrzyżowanie znajduje się po lewej stronie, punkt znajduje się na zewnątrz.

Jeśli linia, na której leży punkt, jest pozioma, użyj powyżej / poniżej.

Jeśli punkt znajduje się na wspólnym wierzchołku wielu trójkątów, użyj trójkąta, którego środkiem punkt tworzy najmniejszy kąt.

Więcej zabawy: trzy punkty mogą znajdować się w linii prostej (zero stopni), na przykład (0,0) - (0,10) - (0,5). W algorytmie triangulacyjnym „ucho” (0,10) należy odciąć, przy czym wygenerowany „trójkąt” jest zdegenerowanym przypadkiem linii prostej.


1

Jest to najprostsza koncepcja pozwalająca ustalić, czy punkt znajduje się wewnątrz trójkąta, czy też na ramieniu trójkąta.

Określenie punktu znajduje się wewnątrz trójkąta za pomocą determinantów:

Określenie punktu znajduje się wewnątrz trójkąta za pomocą determinantów

Najprostszy działający kod:

#-*- coding: utf-8 -*-

import numpy as np

tri_points = [(1,1),(2,3),(3,1)]

def pisinTri(point,tri_points):
    Dx , Dy = point

    A,B,C = tri_points
    Ax, Ay = A
    Bx, By = B
    Cx, Cy = C

    M1 = np.array([ [Dx - Bx, Dy - By, 0],
                    [Ax - Bx, Ay - By, 0],
                    [1      , 1      , 1]
                  ])

    M2 = np.array([ [Dx - Ax, Dy - Ay, 0],
                    [Cx - Ax, Cy - Ay, 0],
                    [1      , 1      , 1]
                  ])

    M3 = np.array([ [Dx - Cx, Dy - Cy, 0],
                    [Bx - Cx, By - Cy, 0],
                    [1      , 1      , 1]
                  ])

    M1 = np.linalg.det(M1)
    M2 = np.linalg.det(M2)
    M3 = np.linalg.det(M3)
    print(M1,M2,M3)

    if(M1 == 0 or M2 == 0 or M3 ==0):
            print("Point: ",point," lies on the arms of Triangle")
    elif((M1 > 0 and M2 > 0 and M3 > 0)or(M1 < 0 and M2 < 0 and M3 < 0)):
            #if products is non 0 check if all of their sign is same
            print("Point: ",point," lies inside the Triangle")
    else:
            print("Point: ",point," lies outside the Triangle")

print("Vertices of Triangle: ",tri_points)
points = [(0,0),(1,1),(2,3),(3,1),(2,2),(4,4),(1,0),(0,4)]
for c in points:
    pisinTri(c,tri_points)


0

Szczerze mówiąc, jest to tak proste, jak odpowiedź Simona P. Stevena, jednak przy takim podejściu nie masz pewności, czy chcesz uwzględnić punkty na krawędziach trójkąta, czy nie.

Moje podejście jest trochę inne, ale bardzo podstawowe. Rozważ następujący trójkąt;

wprowadź opis zdjęcia tutaj

Aby mieć punkt w trójkącie, musimy spełnić 3 warunki

  1. Kąt ACE (zielony) powinien być mniejszy niż kąt ACB (czerwony)
  2. Kąt EBC (niebieski) powinien być mniejszy niż kąt ACB (czerwony)
  3. Punkt E i punkt C powinny mieć ten sam znak, gdy ich wartości xiy zostaną zastosowane do równania | AB | linia.

W tej metodzie masz pełną kontrolę, aby osobno uwzględnić lub wykluczyć punkt na krawędziach. Możesz więc sprawdzić, czy punkt znajduje się w trójkącie, w tym tylko | AC | na przykład krawędź.

Tak więc moje rozwiązanie w JavaScript byłoby następujące;

function isInTriangle(t,p){

  function isInBorder(a,b,c,p){
    var m = (a.y - b.y) / (a.x - b.x);                     // calculate the slope
    return Math.sign(p.y - m*p.x + m*a.x - a.y) === Math.sign(c.y - m*c.x + m*a.x - a.y);
  }
  
  function findAngle(a,b,c){                               // calculate the C angle from 3 points.
    var ca = Math.hypot(c.x-a.x, c.y-a.y),                 // ca edge length
        cb = Math.hypot(c.x-b.x, c.y-b.y),                 // cb edge length
        ab = Math.hypot(a.x-b.x, a.y-b.y);                 // ab edge length
    return Math.acos((ca*ca + cb*cb - ab*ab) / (2*ca*cb)); // return the C angle
  }

  var pas = t.slice(1)
             .map(tp => findAngle(p,tp,t[0])),             // find the angle between (p,t[0]) with (t[1],t[0]) & (t[2],t[0])
       ta = findAngle(t[1],t[2],t[0]);
  return pas[0] < ta && pas[1] < ta && isInBorder(t[1],t[2],t[0],p);
}

var triangle = [{x:3, y:4},{x:10, y:8},{x:6, y:10}],
      point1 = {x:3, y:9},
      point2 = {x:7, y:9};

console.log(isInTriangle(triangle,point1));
console.log(isInTriangle(triangle,point2));


0
bool isInside( float x, float y, float x1, float y1, float x2, float y2, float x3, float y3 ) {
  float l1 = (x-x1)*(y3-y1) - (x3-x1)*(y-y1), 
    l2 = (x-x2)*(y1-y2) - (x1-x2)*(y-y2), 
    l3 = (x-x3)*(y2-y3) - (x2-x3)*(y-y3);
  return (l1>0 && l2>0  && l3>0) || (l1<0 && l2<0 && l3<0);
}

To nie może być bardziej wydajne! Każda strona trójkąta może mieć niezależną pozycję i orientację, dlatego na pewno potrzebne są trzy obliczenia: l1, l2 i l3, z których każda wymaga 2 mnożenia. Gdy znane są l1, l2 i l3, wynikiem jest zaledwie kilka podstawowych porównań i operacji boolowskich.


0

Podobno kod o wysokiej wydajności, który dostosowałem w JavaScript (artykuł poniżej):

function pointInTriangle (p, p0, p1, p2) {
  return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}
  • pointInTriangle(p, p0, p1, p2) - dla trójkątów przeciwnych do ruchu wskazówek zegara
  • pointInTriangle(p, p0, p1, p2) - dla trójkątów zgodnych z ruchem wskazówek zegara

Spójrz w jsFiddle (test wydajności w zestawie), jest też sprawdzanie uzwojenia w osobnej funkcji. Lub naciśnij „Uruchom fragment kodu” poniżej

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();

$("canvas").click(function(evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function(evt) {
    triangle = randomTriangle();
    test();
});

document.querySelector('#performance').addEventListener('click', _testPerformance);

test();

function test() {
    var result = checkClockwise(triangle.a, triangle.b, triangle.c) ? pointInTriangle(point, triangle.a, triangle.c, triangle.b) : pointInTriangle(point, triangle.a, triangle.b, triangle.c);
    
    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function _testPerformance () {
	var px = [], py = [], p0x = [], p0y = [], p1x = [], p1y = [], p2x = [], p2y = [], p = [], p0 = [], p1 = [], p2 = [];
    
	for(var i = 0; i < 1000000; i++) {
    p[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p0[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p1[i] = {x: Math.random() * 100, y: Math.random() * 100};
    p2[i] = {x: Math.random() * 100, y: Math.random() * 100};
  }
  console.time('optimal: pointInTriangle');
  for(var i = 0; i < 1000000; i++) {
    pointInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('optimal: pointInTriangle');

  console.time('original: ptInTriangle');
  for(var i = 0; i < 1000000; i++) {
  	ptInTriangle(p[i], p0[i], p1[i], p2[i]);
  }
  console.timeEnd('original: ptInTriangle');
}

function pointInTriangle (p, p0, p1, p2) {
	return (((p1.y - p0.y) * (p.x - p0.x) - (p1.x - p0.x) * (p.y - p0.y)) | ((p2.y - p1.y) * (p.x - p1.x) - (p2.x - p1.x) * (p.y - p1.y)) | ((p0.y - p2.y) * (p.x - p2.x) - (p0.x - p2.x) * (p.y - p2.y))) >= 0;
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return (s + t) < A;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
	return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    return {
        a: { x: rand(0, W), y: rand(0, H) },
        b: { x: rand(0, W), y: rand(0, H) },
        c: { x: rand(0, W), y: rand(0, H) }
    };
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<button id="performance">Run performance test (open console)</button>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>

Inspirowane tym: http://www.phatcode.net/articles.php?id=459


-1
bool point2Dtriangle(double e,double f, double a,double b,double c, double g,double h,double i, double v, double w){
    /* inputs: e=point.x, f=point.y
               a=triangle.Ax, b=triangle.Bx, c=triangle.Cx 
               g=triangle.Ay, h=triangle.By, i=triangle.Cy */
    v = 1 - (f * (b - c) + h * (c - e) + i * (e - b)) / (g * (b - c) + h * (c - a) + i * (a - b));
    w = (f * (a - b) + g * (b - e) + h * (e - a)) / (g * (b - c) + h * (c - a) + i * (a - b));
    if (*v > -0.0 && *v < 1.0000001 && *w > -0.0 && *w < *v) return true;//is inside
    else return false;//is outside
    return 0;
} 

prawie idealne współrzędne kartezjańskie przekształcone z barycentrycznego są eksportowane w podwójnych liczbach * v (x) i * w (y). Oba podwójne eksportu powinny mieć w każdym przypadku znak *, prawdopodobnie: * v i * w Kod może być również użyty dla drugiego trójkąta czworokąta. Niniejszym podpisałem napisałem tylko trójkąt abc z kwadratu abcd zgodnego z ruchem wskazówek zegara.

A---B
|..\\.o|  
|....\\.| 
D---C 

punkt o znajduje się wewnątrz trójkąta ABC do testowania za pomocą drugiego trójkąta wywołaj tę funkcję kierunek CDA, a wyniki powinny być poprawne po *v=1-*v;i *w=1-*w;dla czworokąta


-1

Potrzebowałem punktu w sprawdzaniu trójkąta w „kontrolowanym środowisku”, kiedy masz absolutną pewność, że trójkąty będą zgodne z ruchem wskazówek zegara. Więc wziąłem jsfiddle Perro Azula i zmodyfikowałem go, jak sugeruje coproc dla takich przypadków; usunęliśmy również zbędne mnożenie 0,5 i 2, ponieważ wzajemnie się anulują.

http://jsfiddle.net/dog_funtom/H7D7g/

var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;

var point = {
    x: W / 2,
    y: H / 2
};
var triangle = randomTriangle();

$("canvas").click(function (evt) {
    point.x = evt.pageX - $(this).offset().left;
    point.y = evt.pageY - $(this).offset().top;
    test();
});

$("canvas").dblclick(function (evt) {
    triangle = randomTriangle();
    test();
});

test();

function test() {
    var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);

    var info = "point = (" + point.x + "," + point.y + ")\n";
    info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
    info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
    info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
    info += "result = " + (result ? "true" : "false");

    $("#result").text(info);
    render();
}

function ptInTriangle(p, p0, p1, p2) {
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0) return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

function checkClockwise(p0, p1, p2) {
    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
    return A > 0;
}

function render() {
    ctx.fillStyle = "#CCC";
    ctx.fillRect(0, 0, 500, 500);
    drawTriangle(triangle.a, triangle.b, triangle.c);
    drawPoint(point);
}

function drawTriangle(p0, p1, p2) {
    ctx.fillStyle = "#999";
    ctx.beginPath();
    ctx.moveTo(p0.x, p0.y);
    ctx.lineTo(p1.x, p1.y);
    ctx.lineTo(p2.x, p2.y);
    ctx.closePath();
    ctx.fill();
    ctx.fillStyle = "#000";
    ctx.font = "12px monospace";
    ctx.fillText("1", p0.x, p0.y);
    ctx.fillText("2", p1.x, p1.y);
    ctx.fillText("3", p2.x, p2.y);
}

function drawPoint(p) {
    ctx.fillStyle = "#F00";
    ctx.beginPath();
    ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
    ctx.fill();
}

function rand(min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function randomTriangle() {
    while (true) {
        var result = {
            a: {
                x: rand(0, W),
                y: rand(0, H)
            },
            b: {
                x: rand(0, W),
                y: rand(0, H)
            },
            c: {
                x: rand(0, W),
                y: rand(0, H)
            }
        };
        if (checkClockwise(result.a, result.b, result.c)) return result;
    }
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>

<pre id="result"></pre>

<canvas width="500" height="500"></canvas>

Oto równoważny kod C # dla Unity:

public static bool IsPointInClockwiseTriangle(Vector2 p, Vector2 p0, Vector2 p1, Vector2 p2)
{
    var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y);
    var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y);

    if (s <= 0 || t <= 0)
        return false;

    var A = (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);

    return (s + t) < A;
}

-3

Jednym z najprostszych sposobów sprawdzenia, czy obszar utworzony przez wierzchołki trójkąta (x1, y1), (x2, y2), (x3, y3) jest dodatni, czy nie.

Obszar można obliczyć według wzoru:

1/2 [x1 (y2 – y3) + x2 (y3 – y1) + x3 (y1 – y2)]

lub kod python można zapisać jako:

def triangleornot(p1,p2,p3):
    return (1/ 2) [p1[0](p2[1]–p3[1]) + p2[0] (p3[1]–p1[1]) + p3[0] (p1[0]–p2[0])]
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.