Bagaimana cara menentukan suatu titik dalam segitiga 2D? [Tutup]

Apakah ada cara mudah untuk menentukan apakah suatu titik berada di dalam segitiga? Ini 2D, bukan 3D.

Secara umum, algoritma yang paling sederhana (dan cukup optimal) adalah memeriksa di sisi mana dari setengah-pesawat dibuat oleh ujung-ujungnya.

Berikut adalah beberapa info berkualitas tinggi dalam topik ini tentang GameDev , termasuk masalah kinerja.

Dan inilah beberapa kode untuk Anda mulai:

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);
}

Selesaikan sistem persamaan berikut:

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

Intinya padalah di dalam segitiga jika 0 <= s <= 1dan 0 <= t <= 1dan s + t <= 1.

s, tdan 1 - s - tdisebut koordinat barycentric dari titik tersebut p.

Saya setuju dengan Andreas Brinck , koordinat barycentric sangat nyaman untuk tugas ini. Perhatikan bahwa tidak perlu menyelesaikan sistem persamaan setiap saat: cukup evaluasi solusi analitiknya. Menggunakan notasi Andreas , solusinya adalah:

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);

di mana Areaarea (ditandatangani) dari segitiga:

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

Cukup evaluasi s, tdan 1-s-t. Intinya padalah di dalam segitiga jika dan hanya jika semuanya positif.

EDIT: Perhatikan bahwa ekspresi di atas untuk area mengasumsikan bahwa penomoran simpul segitiga berlawanan arah jarum jam. Jika penomorannya searah jarum jam, ungkapan ini akan mengembalikan area negatif (tetapi dengan magnitudo yang benar). Tes itu sendiri ( s>0 && t>0 && 1-s-t>0) tidak tergantung pada arah penomoran, namun, karena ekspresi di atas yang dikalikan dengan 1/(2*Area)juga mengubah tanda jika orientasi simpul segitiga berubah.

EDIT 2: Untuk efisiensi komputasi yang lebih baik lagi, lihat komentar coproc di bawah ini (yang menyatakan bahwa jika orientasi simpul segitiga (searah atau berlawanan arah jarum jam) diketahui sebelumnya, pembagian oleh 2*Areadalam ekspresi untuk sdan tdapat dihindari). Lihat juga kode jsfiddle Perro Azul dalam komentar di bawah jawaban Andreas Brinck .

Saya menulis kode ini sebelum upaya terakhir dengan Google dan menemukan halaman ini, jadi saya pikir saya akan membagikannya. Ini pada dasarnya adalah versi yang dioptimalkan dari jawaban Kisielewicz. Saya melihat ke metode Barycentric juga tetapi menilai dari artikel Wikipedia saya mengalami kesulitan melihat bagaimana itu lebih efisien (saya kira ada beberapa kesetaraan yang lebih dalam). Lagi pula, algoritma ini memiliki keuntungan karena tidak menggunakan divisi; masalah potensial adalah perilaku deteksi tepi tergantung pada orientasi.

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;
}

Dengan kata lain, idenya adalah ini: Apakah titik s di sebelah kiri atau ke kanan dari kedua garis AB dan AC? Jika benar, itu tidak bisa berada di dalam. Jika salah, setidaknya di dalam "kerucut" yang memenuhi kondisi tersebut. Sekarang karena kita tahu bahwa titik di dalam trigon (segitiga) harus berada di sisi AB yang sama dengan BC (dan juga CA), kami memeriksa apakah ada perbedaan. Jika ya, tidak mungkin ada di dalam, jika tidak pasti ada di dalam.

Beberapa kata kunci dalam perhitungan adalah garis setengah bidang dan penentu (produk silang 2x2). Mungkin cara yang lebih pedagogis mungkin untuk menganggapnya sebagai suatu titik berada di dalam jika itu ke sisi yang sama (kiri atau kanan) untuk masing-masing garis AB, BC dan CA. Namun cara di atas tampaknya lebih cocok untuk beberapa optimasi.

Versi C # dari metode barycentric diposting oleh andreasdr dan Perro Azul. Perhatikan bahwa perhitungan area dapat dihindari jika sdan tmemiliki tanda-tanda yang berlawanan. Saya memverifikasi perilaku yang benar dengan unit test yang cukup menyeluruh.

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);
}

_{[ sunting ]}
^{menerima modifikasi yang disarankan oleh @Pierre; lihat komentar}

Metode Java versi barycentric:

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;
}

Kode di atas akan bekerja secara akurat dengan bilangan bulat, dengan asumsi tidak ada kelebihan. Ini juga akan bekerja dengan segitiga searah jarum jam dan berlawanan arah jarum jam. Ini tidak akan bekerja dengan segitiga collinear (tetapi Anda dapat memeriksanya dengan menguji det == 0).

Versi barycentric tercepat jika Anda akan menguji poin yang berbeda dengan segitiga yang sama.

Versi barycentric tidak simetris pada 3 titik segitiga, sehingga kemungkinan kurang konsisten daripada versi setengah-bidang tepi Kornel Kisielewicz, karena kesalahan pembulatan floating point.

Kredit: Saya membuat kode di atas dari artikel Wikipedia tentang koordinat barycentric.

Cara sederhana adalah dengan:

temukan vektor yang menghubungkan titik ke masing-masing dari tiga simpul segitiga dan jumlah sudut antara vektor tersebut. Jika jumlah sudutnya 2 * pi maka intinya ada di dalam segitiga.

Dua situs bagus yang menjelaskan alternatif adalah:

blackpawn dan wolfram

Dengan menggunakan solusi analitik untuk koordinat barycentric (ditunjukkan oleh Andreas Brinck ) dan:

• tidak mendistribusikan perkalian di atas syarat yang di dalam tanda kurung
• menghindari komputasi beberapa kali istilah yang sama dengan menyimpannya
• mengurangi perbandingan (seperti yang ditunjukkan oleh coproc dan Thomas Eding )

Satu dapat meminimalkan jumlah operasi "mahal":

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;
}

Kode dapat disisipkan di Perro Azul jsfiddle atau coba dengan mengeklik "Jalankan cuplikan kode" di bawah ini

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>

Menuju ke:

• variabel "penarikan": 30
• penyimpanan variabel: 7
• tambahan: 4
• pengurangan: 8
• perkalian: 6
• divisi: tidak ada
• perbandingan: 4

Ini membandingkan dengan cukup baik dengan solusi Kornel Kisielewicz (25 penarikan, 1 penyimpanan, 15 pengurangan, 6 multiplikasi, 5 perbandingan), dan mungkin lebih baik jika diperlukan deteksi searah jarum jam / berlawanan arah jarum jam (diperlukan 6 penarikan, 1 penambahan, 2 pengurangan , 2 perkalian dan 1 perbandingan dalam dirinya sendiri, menggunakan penentu solusi analitik, seperti yang ditunjukkan oleh rhgb ).

Apa yang saya lakukan adalah menghitung ulang tiga wajah normal,

• dalam 3D oleh produk silang vektor sisi dan vektor normal wajah.

• dalam 2D ​​dengan hanya menukar komponen dan meniadakan satu,

kemudian di dalam / luar untuk setiap satu sisi adalah ketika produk titik dari sisi normal dan titik ke titik vektor, ubah tanda. Ulangi untuk dua (atau lebih) sisi lainnya.

Manfaat:

• banyak yang dihitung sebelumnya sangat bagus untuk pengujian beberapa titik pada segitiga yang sama.

• penolakan awal atas kasus umum lebih banyak di luar daripada di dalam poin. (juga jika distribusi titik tertimbang ke satu sisi, dapat menguji sisi itu terlebih dahulu.)

Berikut ini adalah implementasi Python yang efisien :

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))

dan contoh output:

Jika Anda mencari kecepatan, berikut adalah prosedur yang mungkin membantu Anda.

Urutkan simpul segitiga pada ordinat mereka. Ini membutuhkan tiga perbandingan terburuk. Biarkan Y0, Y1, Y2 menjadi tiga nilai yang diurutkan. Dengan menggambar tiga horizontal melalui mereka Anda mempartisi pesawat menjadi dua pesawat setengah dan dua lempengan. Biarkan Y menjadi ordinat dari titik kueri.

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

Biaya dua perbandingan lagi. Seperti yang Anda lihat, penolakan cepat dicapai untuk poin di luar "slab pembatas".

Secara opsional, Anda dapat memberikan tes pada absis untuk penolakan cepat di sebelah kiri dan di kanan ( X <= X0' or X >= X2'). Ini akan menerapkan tes kotak terikat cepat pada saat yang sama, tetapi Anda juga perlu mengurutkan abscissas.

Akhirnya, Anda perlu menghitung tanda titik yang diberikan sehubungan dengan dua sisi segitiga yang membatasi lempengan yang relevan (atas atau bawah). Tes memiliki bentuk:

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

Diskusi lengkap i, j, kkombinasi (ada enam di antaranya, berdasarkan hasil semacam itu) berada di luar cakupan jawaban ini dan "dibiarkan sebagai latihan untuk pembaca"; untuk efisiensi, mereka harus hard-coded.

Jika Anda berpikir bahwa solusi ini kompleks, amati bahwa itu terutama melibatkan perbandingan sederhana (beberapa di antaranya dapat dikomputasi), ditambah 6 pengurangan dan 4 kali lipat jika uji kotak terikat gagal. Biaya yang terakhir sulit dikalahkan karena dalam kasus terburuk Anda tidak dapat menghindari membandingkan titik uji dengan dua sisi (tidak ada metode dalam jawaban lain yang memiliki biaya lebih rendah, beberapa memperburuknya, seperti 15 pengurangan dan 6 berlipat ganda, kadang-kadang pembagian).

PEMBARUAN: Lebih cepat dengan transformasi geser

Seperti dijelaskan di atas, Anda dapat dengan cepat menemukan titik di dalam salah satu dari empat band horisontal yang dibatasi oleh tiga ordinat verteks, menggunakan dua perbandingan.

Anda secara opsional dapat melakukan satu atau dua tes X tambahan untuk memeriksa insideness ke kotak pembatas (garis putus-putus).

Kemudian pertimbangkan transformasi "geser" yang diberikan oleh X'= X - m Y, Y' = Y, di mana mkemiringan DX/DYuntuk tepi tertinggi. Transformasi ini akan membuat sisi segitiga ini vertikal. Dan karena Anda tahu di sisi horizontal tengah mana, cukup untuk menguji tanda sehubungan dengan satu sisi segitiga.

Dengan asumsi Anda menghitung kemiringan m, serta X'untuk simpul segitiga yang dicukur dan koefisien dari persamaan sisi seperti X = m Y + p, Anda akan perlu dalam kasus terburuk

• dua perbandingan ordinat untuk klasifikasi vertikal;
• opsional satu atau dua perbandingan absis untuk penolakan kotak terikat;
• perhitungan X' = X - m Y;
• satu atau dua perbandingan dengan abscissas dari segitiga yang dicukur;
• satu uji tanda X >< m' Y + p'terhadap sisi yang relevan dari segitiga yang dicukur.

Jika Anda tahu koordinat dari tiga simpul dan koordinat dari titik tertentu, maka Anda bisa mendapatkan luas segitiga lengkap. Setelah itu, hitung luas tiga segmen segitiga (satu titik menjadi titik yang diberikan dan dua lainnya merupakan dua simpul segitiga). Dengan demikian, Anda akan mendapatkan luas tiga segmen segitiga. Jika jumlah area-area ini sama dengan total area (yang Anda dapatkan sebelumnya), maka titik tersebut harus berada di dalam segitiga. Kalau tidak, intinya tidak di dalam segitiga. Ini seharusnya bekerja. Jika ada masalah, beri tahu saya. Terima kasih.

Fungsi lain dalam python , lebih cepat dari metode Developer (setidaknya untuk saya) dan terinspirasi oleh solusi 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  )

Anda dapat mengujinya dengan:

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')

Dibutuhkan banyak untuk merencanakan, tetapi kisi tersebut diuji dalam 0,0195319652557 detik terhadap 0,0844349861145 detik dari kode Pengembang .

Akhirnya komentar kode:

# 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

Karena tidak ada jawaban JS,
searah jarum jam & berlawanan arah jarum jam:

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 

}

EDIT: ada kesalahan ketik untuk perhitungan det ( cy - aybukan cx - ax), ini diperbaiki.

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>

Di sini saya menggunakan metode yang sama seperti yang dijelaskan di atas: sebuah titik ada di dalam ABC jika masing-masing berada di sisi "sama" pada setiap baris AB, BC, CA.

Saya hanya ingin menggunakan beberapa vektor matematika sederhana untuk menjelaskan solusi koordinat barycentric yang telah diberikan Andreas, akan lebih mudah untuk dipahami.

1. Area A didefinisikan sebagai vektor apa pun yang diberikan oleh s * v02 + t * v01, dengan kondisi s> = 0 dan t> = 0. Jika ada titik di dalam segitiga v0, v1, v2, itu harus berada di dalam Area A.

2. Jika lebih lanjut membatasi s, dan t adalah milik [0, 1]. Kami mendapatkan Area B yang berisi semua vektor s * v02 + t * v01, dengan kondisi s, t milik [0, 1]. Perlu dicatat bahwa bagian rendah dari Area B adalah cermin dari Triangle v0, v1, v2. Masalahnya muncul jika kita dapat memberikan kondisi tertentu s, dan t, untuk lebih lanjut mengecualikan bagian rendah dari Area B.

3. Asumsikan kita memberikan nilai s, dan t berubah dalam [0, 1]. Pada gambar berikut, titik p ada di tepi v1v2. Semua vektor s * v02 + t * v01 yang berada di sepanjang garis putus-putus dengan penjumlahan vektor sederhana. Pada v1v2 dan garis silang titik p, kita memiliki:

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

kita mendapatkan 1 - s = tp, lalu 1 = s + tp. Jika ada t> tp, yang 1 <s + t di mana berada pada garis garis ganda, vektor berada di luar segitiga, setiap t <= tp, yang 1> = s + t di mana berada pada garis garis tunggal, vektornya adalah di dalam segitiga.

Kemudian jika kita memberikan s dalam [0, 1], t terkait harus memenuhi 1> = s + t, untuk vektor di dalam segitiga.

Jadi akhirnya kita mendapatkan v = s * v02 + t * v01, v berada di dalam segitiga dengan kondisi s, t, s + t milik [0, 1]. Kemudian terjemahkan ke poin, kita punya

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

yang sama dengan solusi Andreas untuk menyelesaikan sistem persamaan p = p0 + s * (p1 - p0) + t * (p2 - p0), dengan s, t, s + t milik [0, 1].

Berikut adalah solusi dalam python yang efisien, didokumentasikan dan berisi tiga unittests. Ini kualitas kelas profesional dan siap untuk dimasukkan ke proyek Anda dalam bentuk modul apa adanya.

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)

Ada tes grafis opsional tambahan untuk algoritma di atas untuk mengonfirmasi validitasnya:

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")

Memproduksi gambar berikut:

Ada kondisi tepi sial di mana titik tepat di tepi umum dari dua segitiga yang berdekatan. Intinya tidak bisa di keduanya, atau tidak dari segitiga. Anda membutuhkan cara yang sewenang-wenang tetapi konsisten dalam menetapkan poin. Misalnya, gambar garis horizontal melalui titik. Jika garis berpotongan dengan sisi lain dari segitiga di sebelah kanan, titik diperlakukan seolah-olah berada di dalam segitiga. Jika persimpangan di sebelah kiri, titik di luar.

Jika garis di mana titik terletak horizontal, gunakan di atas / bawah.

Jika titik tersebut berada pada simpul umum dari beberapa segitiga, gunakan segitiga yang pusatnya membentuk sudut terkecil.

Lebih menyenangkan: tiga poin bisa berada dalam garis lurus (nol derajat), misalnya (0,0) - (0,10) - (0,5). Dalam algoritma triangulasi, "telinga" (0,10) harus dipotong, "segitiga" yang dihasilkan menjadi kasus degenerasi garis lurus.

Ini adalah konsep paling sederhana untuk menentukan apakah suatu titik berada di dalam atau di luar segitiga atau pada lengan segitiga.

Penentuan titik ada di dalam segitiga dengan faktor penentu:

Kode kerja paling sederhana:

#-*- 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)

Cara termudah dan bekerja dengan semua jenis segitiga adalah menentukan sudut P titik A, B, C, sudut. Jika salah satu sudut lebih besar dari 180.0 derajat maka di luar, jika 180.0 maka di lingkar dan jika acos selingkuh dan kurang dari 180.0 maka di dalamnya. Coba lihat untuk memahami http: // matematika-fisika -psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

Jujur itu sesederhana jawaban Simon P. Steven namun dengan pendekatan itu Anda tidak memiliki kontrol yang kuat pada apakah Anda ingin poin di tepi segitiga dimasukkan atau tidak.

Pendekatan saya sedikit berbeda tetapi sangat mendasar. Pertimbangkan segitiga berikut;

Untuk mendapatkan titik dalam segitiga, kita harus memenuhi 3 syarat

1. Sudut ACE (hijau) harus lebih kecil dari sudut ACB (merah)
2. Sudut ECB (biru) harus lebih kecil dari sudut ACB (merah)
3. Titik E dan Titik C harus memiliki tanda yang sama ketika nilai x dan y diterapkan pada persamaan | AB | baris.

Dalam metode ini Anda memiliki kontrol penuh untuk memasukkan atau mengecualikan titik di tepi secara individual. Jadi, Anda dapat memeriksa apakah suatu titik dalam segitiga termasuk hanya | AC | tepi misalnya.

Jadi solusi saya dalam JavaScript adalah sebagai berikut;

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));

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);
}

Tidak bisa lebih efisien dari ini! Setiap sisi dari sebuah segitiga dapat memiliki posisi dan orientasi independen, maka tiga perhitungan: l1, l2 dan l3 pasti diperlukan yang melibatkan 2 perkalian masing-masing. Setelah l1, l2 dan l3 diketahui, hasilnya hanyalah beberapa perbandingan dasar dan operasi boolean.

Seharusnya kode berkinerja tinggi yang saya adaptasi dalam JavaScript (artikel di bawah):

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) - untuk segitiga berlawanan arah jarum jam
• pointInTriangle(p, p0, p1, p2) - untuk segitiga searah jarum jam

Lihat di jsFiddle (termasuk tes kinerja), ada juga yang berkelok-kelok memeriksa dalam fungsi yang terpisah. Atau tekan "Run snippet code" di bawah ini

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) }
    };
}