确定三角形内部点的凸包算法
Convex hull algorithm to determine points inside of the triangle
我有一个双色集S，在平面一般位置上有红色和绿色点（S 的三个点没有共线）。制作红色三角形，使其所有三个顶点都是 S 的红色点。如果 p 位于内部，则称 S 的绿色点 p 被红色三角形包围那个三角形的。
我应该做一个算法来找到三角形内的所有绿点。
在从在线资源中看到一些信息后，我尝试制作自己的算法，例如：
http://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html
这是我的 "solution":
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。
我应该创建的这个算法应该是我能想到的最有效的算法，所以欢迎任何其他解决方案或建议！
如果所有可能的三角形（所有可能的三个红点选择），你可以做的更简单：
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)).
让我们从问题中显示的图像开始。它显示不属于三角形的红点。文本没有赋予它们特定的含义。所以在我的回答中，我忽略了它们。
这将问题转换为：
给定一组（绿色）点和一组三角形，报告任何三角形内的所有点。
希望这就是您要找的。
根据墨菲定律，每一个小问题都潜伏着一堆更大的问题，正在努力摆脱困境。这里，第一个更大的问题 是，如何测试一个点是否在三角形内。 Wiki, google 等表明有多种解决问题的方法。对于给定的问题，我认为重心坐标系方法是一个很好的（最好的？）候选者，因为我们必须重新测试每个点，并且这种方法允许为每个三角形计算一组参数，然后在每个三角形中重复使用点测.
第二个问题是在给定 K 个绿点和 N 个三角形的情况下，我们是否可以在执行的测试数量方面做得比天真的方法更好。
naive：#Tests = N * K（针对所有三角形测试每个点）。 （我看不出 O(N^3) 是如何产生的，但是问题的作者没有说 N 是什么）。
改进：尝试找到一种仅针对三角形子集测试点的方法。子集是“可能”的三角形：#Tests = K * N'，其中 N' 希望小于或等于 N。 K 此处不变 - 毕竟我们需要查看每个点。
因此，我提出一种扫描线算法作为（可能）改进的解决方案：
查看问题中的图片，想象一条垂直线在图片上从左到右延伸，无论何时移动，都会走到下一个绿点。
现在，根据给定时刻垂直扫描线的位置，只有与扫描线相交的三角形才是扫描线所在点的命中测试的候选对象。这是我们要测试点的三角形子集。
要实现扫描线算法，我们需要先做一些重新排序。
- 按 x 坐标升序排列所有绿色点。 (O (K log K)).
- 按 x 升序对每个三角形的所有三角形顶点进行排序。
- 根据最左边点的 x 坐标对所有三角形进行排序。 (O (N log N)).
Then, for each green point P:
* drop all of the remaining triangles which are entirely to the left of P.
* select all of the remaining triangles, which start but do not end to the left of P.
(open triangles)
* test P against each of the open triangles.
P is contained if it is contained in any of those open triangles.
虽然它比我预期的长了一点，但这是我用每个人最喜欢的语言实现的原型 Haskell:
import Data.List
-- While colors are part of the question, we have no real use for them in the solution.
-- data Color = Red | Green deriving (Show,Eq)
-- data Vertex = Vertex { loc :: Point, col :: Color } deriving (Show,Eq)
data Point = Point { x :: Float, y :: Float } deriving (Show,Eq)
data Triangle = Triangle [Point] deriving (Show,Eq)
data BaryParms = BaryParms
{ dt :: Float -- the DeTerminant.
, dy23 :: Float
, dx32 :: Float
, dy31 :: Float
, dx13 :: Float
, x3 :: Float
, y3 :: Float
} deriving (Show,Eq)
-- Get the list of points from a triangle. Of course that list is always of length 3.
triPoints :: Triangle -> [Point]
triPoints (Triangle ps) = ps
-- We do some sorting (of triangles and points) and this is our
-- ordering (left to right on the x-coordinates of a point.)
leftToRight :: Point -> Point -> Ordering
leftToRight p1 p2
| x p1 < x p2 = LT
| x p1 == x p2 = EQ
| otherwise = GT
-- Shortcut function, since we use it a few times.
-- Left To Right Sort.
ltrSort = sortBy leftToRight
-- rearrange the points of a triangle in left to right manner.
ltrTriangle :: Triangle -> Triangle
ltrTriangle (Triangle points) = Triangle $ ltrSort points
-- compute the bary coordinates for a point with respect to
-- the bary parameters of a given triangle.
toBaryCoords :: BaryParms -> Point -> (Float,Float,Float)
toBaryCoords bp p =
(l1,l2,l3)
where
l1 = (dy23 bp * (x p - x3 bp) + (dx32 bp * (y p - y3 bp))) / dt bp
l2 = (dy31 bp * (x p - x3 bp) + (dx13 bp * (y p - y3 bp))) / dt bp
l3 = 1 - l1 - l2
-- precompute some values we need for testing points against a triangle.
triToBaryParms :: Triangle -> BaryParms
triToBaryParms (Triangle [r1,r2,r3]) =
BaryParms
{
dt = det (x r1 - x r3) (x r2 - x r3) (y r1 - y r3) (y r2 - y r3),
dy23 = y r2 - y r3,
dx32 = x r3 - x r2,
dy31 = y r3 - y r1,
dx13 = x r1 - x r3,
x3 = x r3,
y3 = y r3
}
where
det x11 x12 x21 x22 = x11 * x22 - x12 * x21
-- test if a (green) point is contained in a given triangle.
triangleContainsPoint :: Point -> BaryParms -> Bool
triangleContainsPoint p parms =
l1 >= 0.0 && l2 >= 0.0 && l3 >= 0.0
where
(l1,l2,l3) = toBaryCoords parms p
-- our improved (?) scan line algorithm.
reportGreensInTriangles :: [Point] -> [Triangle] -> [Point]
reportGreensInTriangles greens triangles =
scan sgreens stris []
where
-- sort the green points left to right.
sgreens :: [Point]
sgreens = ltrSort greens
-- sort the triangles left to right by their leftmost vertex.
-- and compute the barycentric coordinate parameters.
stris :: [(Triangle,BaryParms)]
stris =
fmap (\t -> (t,triToBaryParms t))
. sortBy (\t1 t2 -> leftToRight (head . triPoints $ t1) (head . triPoints $ t2))
. fmap ltrTriangle
$ triangles
-- recursive iteration over each (green) point. It's tail recursive.
scan :: [Point] -> [(Triangle,BaryParms)] -> [Point] -> [Point]
scan [] _ found = found -- no more points to test
scan (g:gs) remainingTris found =
scan gs remainingTris' found'
where
found' =
if any (triangleContainsPoint g . snd) open
then g : found
else found
inScope (Triangle [r1,_,r3],_) = x r1 <= x g && x r3 >= x g
-- the list of open triangles
open = takeWhile inScope remainingTris
-- triangles not discarded yet.
remainingTris' = dropWhile (\ (Triangle [_, _, r3] ,_) -> x r3 < x g ) remainingTris
更新
现在，所缺少的只是创建一个外部函数，它懒惰地从红点创建一批三角形，并使用上面给出的函数根据该列表测试绿点。上面函数报告的任何绿点（包含在该特定调用的三角形中）都不需要再次测试。外部函数创建三角形批次并调用上面的函数直到：
- 剩余点集为空
- 没有更多的三角形（最坏的情况）。
后一种情况的剩余点集就是不包含在任何三角形中的点集。
因此，很容易控制 space 复杂度，因为三角形是懒惰地分批生成的。
我有一个双色集S，在平面一般位置上有红色和绿色点（S 的三个点没有共线）。制作红色三角形，使其所有三个顶点都是 S 的红色点。如果 p 位于内部，则称 S 的绿色点 p 被红色三角形包围那个三角形的。
我应该做一个算法来找到三角形内的所有绿点。
这是我的 "solution":
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。
我应该创建的这个算法应该是我能想到的最有效的算法，所以欢迎任何其他解决方案或建议！
如果所有可能的三角形（所有可能的三个红点选择），你可以做的更简单：
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)).
让我们从问题中显示的图像开始。它显示不属于三角形的红点。文本没有赋予它们特定的含义。所以在我的回答中，我忽略了它们。
这将问题转换为：
给定一组（绿色）点和一组三角形，报告任何三角形内的所有点。
希望这就是您要找的。
根据墨菲定律，每一个小问题都潜伏着一堆更大的问题，正在努力摆脱困境。这里，第一个更大的问题 是，如何测试一个点是否在三角形内。 Wiki, google 等表明有多种解决问题的方法。对于给定的问题，我认为重心坐标系方法是一个很好的（最好的？）候选者，因为我们必须重新测试每个点，并且这种方法允许为每个三角形计算一组参数，然后在每个三角形中重复使用点测.
第二个问题是在给定 K 个绿点和 N 个三角形的情况下，我们是否可以在执行的测试数量方面做得比天真的方法更好。
naive：
#Tests = N * K（针对所有三角形测试每个点）。 （我看不出 O(N^3) 是如何产生的，但是问题的作者没有说 N 是什么）。改进：尝试找到一种仅针对三角形子集测试点的方法。子集是“可能”的三角形：
#Tests = K * N'，其中N'希望小于或等于N。K此处不变 - 毕竟我们需要查看每个点。
因此，我提出一种扫描线算法作为（可能）改进的解决方案：
查看问题中的图片，想象一条垂直线在图片上从左到右延伸，无论何时移动，都会走到下一个绿点。
现在，根据给定时刻垂直扫描线的位置，只有与扫描线相交的三角形才是扫描线所在点的命中测试的候选对象。这是我们要测试点的三角形子集。
要实现扫描线算法，我们需要先做一些重新排序。
- 按 x 坐标升序排列所有绿色点。 (O (K log K)).
- 按 x 升序对每个三角形的所有三角形顶点进行排序。
- 根据最左边点的 x 坐标对所有三角形进行排序。 (O (N log N)).
Then, for each green point P:
* drop all of the remaining triangles which are entirely to the left of P.
* select all of the remaining triangles, which start but do not end to the left of P.
(open triangles)
* test P against each of the open triangles.
P is contained if it is contained in any of those open triangles.
虽然它比我预期的长了一点，但这是我用每个人最喜欢的语言实现的原型 Haskell:
import Data.List
-- While colors are part of the question, we have no real use for them in the solution.
-- data Color = Red | Green deriving (Show,Eq)
-- data Vertex = Vertex { loc :: Point, col :: Color } deriving (Show,Eq)
data Point = Point { x :: Float, y :: Float } deriving (Show,Eq)
data Triangle = Triangle [Point] deriving (Show,Eq)
data BaryParms = BaryParms
{ dt :: Float -- the DeTerminant.
, dy23 :: Float
, dx32 :: Float
, dy31 :: Float
, dx13 :: Float
, x3 :: Float
, y3 :: Float
} deriving (Show,Eq)
-- Get the list of points from a triangle. Of course that list is always of length 3.
triPoints :: Triangle -> [Point]
triPoints (Triangle ps) = ps
-- We do some sorting (of triangles and points) and this is our
-- ordering (left to right on the x-coordinates of a point.)
leftToRight :: Point -> Point -> Ordering
leftToRight p1 p2
| x p1 < x p2 = LT
| x p1 == x p2 = EQ
| otherwise = GT
-- Shortcut function, since we use it a few times.
-- Left To Right Sort.
ltrSort = sortBy leftToRight
-- rearrange the points of a triangle in left to right manner.
ltrTriangle :: Triangle -> Triangle
ltrTriangle (Triangle points) = Triangle $ ltrSort points
-- compute the bary coordinates for a point with respect to
-- the bary parameters of a given triangle.
toBaryCoords :: BaryParms -> Point -> (Float,Float,Float)
toBaryCoords bp p =
(l1,l2,l3)
where
l1 = (dy23 bp * (x p - x3 bp) + (dx32 bp * (y p - y3 bp))) / dt bp
l2 = (dy31 bp * (x p - x3 bp) + (dx13 bp * (y p - y3 bp))) / dt bp
l3 = 1 - l1 - l2
-- precompute some values we need for testing points against a triangle.
triToBaryParms :: Triangle -> BaryParms
triToBaryParms (Triangle [r1,r2,r3]) =
BaryParms
{
dt = det (x r1 - x r3) (x r2 - x r3) (y r1 - y r3) (y r2 - y r3),
dy23 = y r2 - y r3,
dx32 = x r3 - x r2,
dy31 = y r3 - y r1,
dx13 = x r1 - x r3,
x3 = x r3,
y3 = y r3
}
where
det x11 x12 x21 x22 = x11 * x22 - x12 * x21
-- test if a (green) point is contained in a given triangle.
triangleContainsPoint :: Point -> BaryParms -> Bool
triangleContainsPoint p parms =
l1 >= 0.0 && l2 >= 0.0 && l3 >= 0.0
where
(l1,l2,l3) = toBaryCoords parms p
-- our improved (?) scan line algorithm.
reportGreensInTriangles :: [Point] -> [Triangle] -> [Point]
reportGreensInTriangles greens triangles =
scan sgreens stris []
where
-- sort the green points left to right.
sgreens :: [Point]
sgreens = ltrSort greens
-- sort the triangles left to right by their leftmost vertex.
-- and compute the barycentric coordinate parameters.
stris :: [(Triangle,BaryParms)]
stris =
fmap (\t -> (t,triToBaryParms t))
. sortBy (\t1 t2 -> leftToRight (head . triPoints $ t1) (head . triPoints $ t2))
. fmap ltrTriangle
$ triangles
-- recursive iteration over each (green) point. It's tail recursive.
scan :: [Point] -> [(Triangle,BaryParms)] -> [Point] -> [Point]
scan [] _ found = found -- no more points to test
scan (g:gs) remainingTris found =
scan gs remainingTris' found'
where
found' =
if any (triangleContainsPoint g . snd) open
then g : found
else found
inScope (Triangle [r1,_,r3],_) = x r1 <= x g && x r3 >= x g
-- the list of open triangles
open = takeWhile inScope remainingTris
-- triangles not discarded yet.
remainingTris' = dropWhile (\ (Triangle [_, _, r3] ,_) -> x r3 < x g ) remainingTris
更新
现在，所缺少的只是创建一个外部函数，它懒惰地从红点创建一批三角形，并使用上面给出的函数根据该列表测试绿点。上面函数报告的任何绿点（包含在该特定调用的三角形中）都不需要再次测试。外部函数创建三角形批次并调用上面的函数直到：
- 剩余点集为空
- 没有更多的三角形（最坏的情况）。
后一种情况的剩余点集就是不包含在任何三角形中的点集。
因此，很容易控制 space 复杂度，因为三角形是懒惰地分批生成的。