用于确定三角形内部点的凸包算法

Question

我有一个双色集S，在平面常规位置有红色和绿色的点（S的三个点都不共线）。制作红色三角形时，要使其所有三个顶点均为S的红点。如果S的绿色点p被红色三角形包围，则p处于该三角形的内部。

我应该制定一种算法，以找到三角形内的所有绿色点。在看到一些在线资源后，我尝试制作自己的算法：http://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html

这是我的“解决方案”：

green_inside = all_the_greens
for each triangle T in get_all_triangles()
  for each greenie G in green_inside
    if G in T
      remove G from green_inside

greenies_in_triangles = all_the_greens - green_inside

我不知道此算法是否有效。其运行时间为n ^ 3。另外，我不确定是否可以说get_all_triangles。我应该创建的这种算法应该是我能想到的最有效的算法，因此，欢迎任何其他解决方案或建议！

Answer 1

您可以更简单地完成它：

Create the convex hull (CH) of the red points.
Check each of the green points is in the CH or not.
    If it is, there is a red triangle that contains that point.
    If it is not, there is no red triangle that contains the point.

在N中创建O(N log(N))红色点的凸包，并在O(log(N))中检查点是否在凸多边形内。因此，如果绿点的数量为M，则上述算法的总复杂度为O((M+N)log(N))。