Давайте начнем с изображения, показанного в вопросе. Это показывает красные точки, которые не являются частью треугольников. И текст не дает им конкретного значения. Поэтому в своем ответе я их игнорирую.
Это превращает вопрос в:
Учитывая набор (зеленых) точек и набор треугольников, сообщите все точки, которые находятся внутрилюбой из треугольников.
Я надеюсь, что это то, что вы ищете.
Согласно закону Мёрфиса, внутри каждой маленькой проблемы скрывается куча больших проблем, изо всех сил пытающихся выбраться. ,Здесь первая большая проблема заключается в том, как проверить, находится ли точка внутри треугольника. Вики, гугл и т. Д. Показывают, что существуют различные варианты решения проблемы. Для данного вопроса я считаю подход Барицентрической системы координат хорошим (лучшим?) Кандидатом, учитывая, что мы должны повторно протестировать для каждой точки, и этот подход позволяет вычислить набор параметров для каждого треугольника, который затем повторно используется в каждомточечный тест.
Второй вопрос заключается в том, можем ли мы добиться большего успеха, чем наивный подход, с точки зрения количества проведенных испытаний, учитывая K зеленых точек и N треугольников.
наивный: #Tests = N * K (проверить каждую точку на соответствие всем треугольникам). (Я не могу понять, как O (N ^ 3) входит в это, но тогда автор вопроса не говорит, что такое N).
улучшено: попытаться найти способтолько для проверки точек против подмножества треугольников. Подмножеством являются треугольники, которые "вероятны": #Tests = K * N', где N', мы надеемся, меньше или равны N. K здесь не меняется - в конце концов нам нужно взглянуть на каждую точку.
Итак, я предлагаю алгоритм линии сканирования в качестве (потенциально) улучшенного решения: посмотрите на изображениев этом вопросе и представьте вертикальную линию, идущую слева направо по изображению, переходя к следующей зеленой точке, всякий раз, когда она движется.
Теперь, в зависимости от того, где находится эта вертикальная линия сканирования в данный момент, только треугольники, которые пересекаютсяс линией сканирования - кандидаты на тестирование попадания в точку, в которой расположена линия сканирования. Это наше подмножество треугольников, с которым мы хотим проверить точку.
Чтобы реализовать алгоритм линии развертки, нам нужно сначала выполнить некоторое переупорядочение.
- сортировка всех зеленых точек по координате х в порядке возрастания. (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