如何确定一个点是否在二维三角形中?

有没有一种简单的方法来确定一个点是否在三角形内?是2D的，不是3D的。

334197 次浏览
小开
最佳答案

一般来说，最简单(也是最优)的算法是检查由边创建的半平面的哪一边是点。

这里有一些高质量的信息在这个GameDev主题，包括性能问题。

这里有一些代码让你开始:

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

一个简单的方法是:

找到连接 分别指向三角形的三个点 顶点和夹角之和 这些向量。如果它们的和 角度是2*那么点是

两个解释替代方案的好网站是:

blackpawn和沃尔夫勒姆

小开

求解如下方程组:

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

如果0 <= s <= 1和0 <= t <= 1和s + t <= 1，则点p在三角形内。

s，t和1 - s - t被称为点p的重心坐标。

小开

我在最后一次尝试谷歌和找到这个页面之前写了这段代码，所以我想我应该分享它。它基本上是Kisielewicz答案的优化版本。我也研究了重心法，但从维基百科的文章来看，我很难看出它是如何更有效的(我猜有一些更深层次的等价性)。不管怎样，这个算法的优点是不用除法;一个潜在的问题是边缘检测的行为取决于方向。

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

换句话说，思想是这样的:点s是在直线AB和直线AC的左边还是右边?如果是真的，它就不可能在里面。如果为假，它至少在“圆锥”之内;满足条件。现在，因为我们知道三角形(三角形)内的一个点必须与BC(以及CA)在AB的同一侧，我们检查它们是否不同。如果有，s就不可能在里面，否则s一定在里面。

计算中的一些关键字是线半平面和行列式(2x2叉乘)。也许一个更有教学意义的方法是将它看作是一个在AB、BC和CA的同一侧(左或右)的点。然而，上面的方法似乎更适合进行一些优化。

小开

我要做的是预先计算三个面法线，

  • 在三维中通过边向量和面法向量的叉乘得到。

  • 通过简单地交换分量和负一个，

对于任意一条边的内/外都是边法线和点到点向量的点积，改变符号。重复其他两(或更多)面。

好处:

  • 在同一个三角形上进行多点测试，很多都是预先计算好的。

  • 早期拒签的常见情况是外分多内分。(如果点分布偏向一侧，可以先测试这一侧。)

小开

我同意Andreas Brinck，重心坐标对于这个任务非常方便。注意，不需要每次都求解一个方程组:只需计算解析解。使用安德烈亚斯'表示法，解决方案是:

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

其中Area是三角形的(带符号的)区域:

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

只计算s， t和1-s-t。当且仅当它们都为正时，点p在三角形内。

编辑:请注意，上面的区域表达式假设三角形节点编号是逆时针方向的。如果编号是顺时针的，这个表达式将返回一个负的面积(但大小正确)。然而，测试本身(s>0 && t>0 && 1-s-t>0)并不依赖于编号的方向，因为如果三角形节点的方向改变，上面乘以1/(2*Area)的表达式也会改变符号。

编辑2:为了获得更好的计算效率，请参阅下面coproc的注释(该注释指出，如果三角形节点的方向(顺时针或逆时针)事先已知，则可以避免在s和t的表达式中除以2*Area)。也可以在Andreas Brinck的答案下面的注释中查看Perro Azul的jsfiddle-code。

小开

由andreasdr和Perro Azul发布的c#版本的重心方法。我添加了一个检查，当s和t有相反的符号(并且都不是零)时，放弃面积计算，因为潜在地避免三分之一的乘法成本似乎是合理的。

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


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


var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);
return d == 0 || (d < 0) == (s + t <= 0);
}

2021年更新:
这个版本正确处理任意一个缠绕方向(顺时针和逆时针)指定的三角形。请注意，对于恰好位于三角形边缘上的点，本页上的一些其他答案会给出不一致的结果，这取决于三角形三个点的排列顺序。这样的点被认为是“;in”;该代码正确地返回true，而不管缠绕方向如何。

小开

下面是一个高效的Python <强> < / >强实现:

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

和一个示例输出:

enter image description here

小开

如果你正在寻找速度，这里有一个方法可能会帮助你。

对三角形顶点的纵坐标进行排序。这最多需要三次比较。设Y0 Y1 Y2是三个排好序的值。通过画三条水平线，你可以把这个平面分成两个半平面和两块平板。设Y为查询点的纵坐标。

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

又花费了两次比较。如你所见，在“边界板”之外的点可以快速拒绝。

可选地，您可以在横坐标上提供一个测试，以便在左侧和右侧快速拒绝(X <= X0' or X >= X2')。这将同时实现一个快速的包围框测试，但您还需要在横坐标上排序。

最终，你需要计算给定点的符号，相对于三角形的两边，划定相关的板(上或下)。该测试形式为:

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

i, j, k组合的完整讨论(根据排序的结果，有六个组合)超出了这个答案的范围，“留给读者练习”;为了提高效率，它们应该被硬编码。

如果您认为这个解决方案很复杂，请注意，它主要涉及简单的比较(其中一些可以预先计算)，加上6个减法和4个乘法，以防边界盒测试失败。后者的代价是难以克服的，因为在最坏的情况下，你无法避免将测试点与两边进行比较(在其他答案中，没有哪种方法的代价更低，有些方法的代价更低，比如15个减法和6个乘法，有时是除法)。

< p >更新: 剪切变换

更快

如上所述，您可以使用两次比较快速定位由三个顶点纵坐标分隔的四个水平带之一内的点。

您可以选择执行一个或两个额外的X测试来检查边界框(虚线)的内部性。

然后考虑由X'= X - m Y, Y' = Y给出的“剪切”变换，其中m是最高边的斜率DX/DY。这个变换会使三角形的这条边是垂直的。因为你知道你在中间水平线的哪一边，所以只用三角形的一条边来测试符号就足够了。

enter image description here

假设你预先计算了斜率m，以及剪切三角形顶点的X'和边的方程系数X = m Y + p，你将需要在最坏的情况下

  • 纵向分类的两个纵坐标比较;
  • 可选的一个或两个横坐标比较用于边界框拒绝;
  • X' = X - m Y的计算;
  • 与剪切三角形的横坐标作一两次比较;
  • 一个符号测试X >< m' Y + p'对剪切三角形的相关边。
小开

我需要在“可控环境”中检查三角形中的点，当你绝对确定三角形是顺时针的时候。因此，我取了Perro Azul的jsfiddle，并根据coproc的建议对其进行了修改;还去掉了多余的0.5和2乘法因为它们互相抵消了。

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>

以下是Unity的等效c#代码:

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

如果你知道这三个顶点的坐标和特定点的坐标，那么你就可以得到整个三角形的面积。然后，计算三个三角形段的面积(一个点是给定的点，另外两个是三角形的任意两个顶点)。这样，你将得到三个三角形段的面积。如果这些面积的和等于总面积(你之前得到的)，那么，这个点应该在三角形的内部。否则，该点不在三角形内。这应该有用。如果有什么问题，请告诉我。谢谢你！

小开

重心法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;
}

上面的代码可以准确地处理整数，假设没有溢出。它也适用于顺时针和逆时针三角形。它不适用于共线三角形(但您可以通过测试det==0来检查)。

如果你要用同一个三角形测试不同的点，以重心为中心的版本是最快的。

重心版本在3个三角形点上是不对称的，所以它可能不如Kornel Kisielewicz的边缘半平面版本一致，因为浮点舍入误差。

图片来源:我根据维基百科关于重心坐标的文章制作了上面的代码。

小开

有一些恼人的边条件，即一个点恰好在两个相邻三角形的公共边上。这个点不可能在两个三角形中，也不可能不在两个三角形中。你需要一种任意但一致的方式来分配点。例如，画一条横线穿过这个点。如果这条直线与三角形的另一边在右侧相交，则该点被视为在三角形内。如果交点在左边，则该点在外面。

如果该点所在的直线是水平的，则使用above/below。

如果该点位于多个三角形的公共顶点上，则使用该点与中心点形成的角最小的三角形。

更有趣的是:三个点可以在一条直线上(零度)，例如(0,0)-(0,10)-(0,5)。在三角剖分算法中，“耳朵”(0,10)必须被切掉，生成的“三角形”是直线的退化情况。

小开

通过使用重心坐标的解析解(由Andreas Brinck指出)和:

  • 不是把乘法分布在括号里的项上
  • 通过存储相同的项来避免多次计算
  • 减少比较(如coproc和托马斯·埃德所指出的)

可以最小化“昂贵”操作的数量:

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

代码可以粘贴在Perro Azul jsfiddle中，或者通过点击下面的“运行代码片段”来尝试

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>

导致:

  • 变量“召回”:30
  • 可变存储:7
  • 补充:4
  • 减法:8
  • 乘法:6
  • 部门:没有
  • 比较:4

这与Kornel Kisielewicz解决方案(25次召回，1次存储，15次减法，6次乘法，5次比较)相比非常好，如果需要顺时针/逆时针检测(它本身需要6次召回，1次加法，2次减法，2次乘法和1次比较，使用解析解行行式，正如rhgb指出的那样)，可能会更好。

小开

我在JavaScript中改编的高性能代码(文章如下):

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) -用于逆时针三角形
  • pointInTriangle(p, p0, p1, p2) -用于顺时针三角形

在jsFiddle(包括性能测试)中，在一个单独的函数中也有绕线检查。或按下面的“运行代码片段”

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>

启发: http://www.phatcode.net/articles.php?id=459 < / p >

小开

我只是想用一些简单的向量数学来解释安德里亚斯给出的重心坐标解，它会更容易理解。

  1. 区域A定义为s * v02 + t * v01给出的任意向量，条件s >= 0, t >= 0。如果三角形v0 v1 v2内的任意一点，它一定在区域A内。

enter image description here

  1. 如果进一步限制s, t属于[0,1]。得到包含s * v02 + t * v01的所有向量的区域B，条件s, t属于[0,1]。值得注意的是，区域B的下部是三角形v0, v1, v2的镜像。问题来了，我们是否可以给定一定的s和t条件，来进一步排除区域B的低部分。

enter image description here

  1. 假设我们给出一个值s, t在[0,1]内变化。在下图中，点p位于v1v2的边缘。s * v02 + t * v01的所有向量沿着虚线通过简单向量和得到。在v1v2和虚线交点p处，我们有:

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

得到1 - s = tp，然后1 = s + tp。如果任意t > tp，其中1 <S + t在双虚线上，向量在三角形外，任意t <= tp，即1 >= S + t在单虚线上，向量在三角形内。

如果我们给出[0,1]中的任意s，对应的t必须满足1 >= s + t，对于三角形内的向量。

enter image description here

最后我们得到v = s * v02 +t * v01, v在三角形内，条件s, t, s+t属于[0,1]。然后翻译到点，我们有

P - p0 = s * (p1 - p0) + t * (p2 - p0)， and s, t, s + t in [0,1]

这和Andreas解方程组的解是一样的 P = p0 + s * (p1 - p0) + t * (p2 - p0)，与s, t, s + t属于[0,1].

小开

最简单的方法，适用于所有类型的三角形，就是确定P点A点B点C点的角。如果任何一个角大于180.0度，那么它在外面，如果是180.0度，那么它在圆周上，如果acos欺骗了你，小于180.0度，那么它在里面。看一下如何理解http://math-physics-psychology.blogspot.hu/2015/01/earlish-determination-that-point-is.html

小开

老实说，它就像Simon P Steven的回答一样简单，但是使用这种方法，你没有一个可靠的控制，你是否想要包含三角形边缘上的点。

我的方法有点不同，但非常基本。考虑下面的三角形;

enter image description here

为了在三角形中有这个点我们必须满足三个条件

  1. ACE角(绿色)应小于ACB角(红色)
  2. ECB角(蓝色)应小于ACB角(红色)
  3. 当点E和点C的x和y值应用于|AB|直线方程时，点E和点C的符号应该相同。

在此方法中，您可以完全控制单独包含或排除边缘上的点。所以你可以检查一个点是否在三角形中，例如，只包括|AC|边。

所以我的JavaScript解决方案是这样的;

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

没有比这更有效率的了!三角形的每边都可以有独立的位置和方向，因此需要进行l1、l2和l3三个计算，每个计算需要进行2次乘法。一旦l1, l2和l3是已知的，结果只是一些基本的比较和布尔运算。

小开

python中的其他函数，比开发人员的方法快(至少对我来说)，并受到塞德里克·杜福尔解决方案的启发:

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  )

你可以用:

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

绘制网格需要花费很多时间，但是该网格在0.0195319652557秒内测试，而开发人员的代码的0.0844349861145秒。

最后是代码注释:

# 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
小开

因为没有JS的答案，
顺时针,逆时针方向的解决方案:< / p > 

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


}

编辑:修正了两个拼写错误(关于符号&比较)。

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>

enter image description here

我在这里使用与上面描述的相同的方法:如果一个点分别位于"same"每条线AB BC CA的边。

triangle inclusion example .

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

从质心转换而来的几乎完美的笛卡尔坐标 在*v (x)和*w (y)双精度内导出。 在每种情况下，两个导出双精度对象前面都应该有一个*字符，可能是*v和*w 代码也可以用于四边形的另一个三角形。 特此签名只写三角形abc从顺时针abcd的四边形。< / p > 

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

o点在ABC三角形内 对于带有第二个三角形的测试，调用此函数CDA direction，并且对于

的四边形，*v=1-*v;和*w=1-*w;之后的结果应该是正确的
小开

下面是一个python解决方案，它是高效的，文档化的，包含三个单元测试。它具有专业级的质量，并且可以以模块的形式放入您的项目中。

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)

上面的算法有一个额外的可选图形测试，以确认其有效性:

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

制作以下图表:

Test the point_in_triangle function

小开

这是确定一个点是在三角形的内、外还是在三角形的臂上的最简单的概念。

用行列式确定三角形内的点:

由决定因素确定一个点在三角形内

最简单的工作代码:

#-*- 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)
小开
一个最简单的方法来检查区域是否由三角形的顶点组成 (x1,y1)，(x2,y2)，(x3,y3)是否为正

面积可由公式计算:

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

或者python代码可以写成:

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

提交答案