Есть  массив точек, координаты которых могут быть только целыми.
Даны три точки. Нужно найти точки, принадлежащие треугольнику, заданному этими тремя вершинами.
Так как для меня это не абстрактная задача, а часть конкретной программы на Delphi, то
и описывть ее я буду в терминах этого языка программирования.



нужно сделать функцию


которая выдает массив точек, находящися внутри треугольника.

Вот... Основное условие - выокая скорость работы. А то у меня всегда получаются громоздкие и медленые алгоритмы.
 
У меня, конечно, есть собственный алгоритм, но чую я ,что он далек от идеала.

Сначала я создаю 3 массива точек, соответствующих отрезкам трегольника.
Потом иду от крайней левой точки к крайней правой (то есть по возрастанию Х), и для каждого Х
выбираю точки, лежащие между ограничивающими сверху и снизу (то есть по У) отрезками.
Это если в двух словах.
Код же будет подлиннее  :


Все это работает, но хотелось бы применять менее забористый алгоритм.



Это сообщение отредактировал(а) Чупакабро - 19.2.2009, 21:58

Начни с отсева заведомо НЕ лежащих внутри треугольника точек - это уже сократит перебор.
А затем воспользуйся следующим свойством: если точка лежит снаружи треугольника, то сумма трёх углов, образованных точкой и парами вершин треугольника, менее 360 градусов, если она лежит внутри, то равно 360, если на одной из сторон - один из этих углов 180 градусов.

Решение данной задачи на много проще чем вы думаете
Немного теории
1.  Векторное произведение векторов есть площадь //-мма (причем тут вектора станет понятно позже)
2.  Если точка Pi лежит внутри треугольника  P1P2P3, то площадь большого треугольника равна сумме площадей треугольников PiP2P3 + P1PiP3 + P1P2Pi
3.  Векторное произведение векторов есть определитель матрицы составленной из координат векторов
Ща все это на пальцах
1. Что бы узнать где лежит точка Pi  надо найти площадь треугольника  P1P2P3 и сумму площадей  PiP2P3 + P1PiP3 + P1P2Pi, а затем их сравнить.
2. Как найти площадь?
    Оооочень просто

3.  Как узнать лежит ли точка внутри?
   Нефиг делать

4. Осталось лишь в цикле перебрать все точки и вывести только те которые удовлетворяют условию  InTrg(P,P1,P2,P3,S)=t
-------------------
Надеюсь вам не составит труда собрать все это в одну кучу, удачи   

С углами будет дольше: это тригонометрические функции...
Чупакабро, алгоритмы бываю либо эффективные, либо простые. Конечно, есть и исключения, но это как правило.
Я в твоем коде не разбиралась, но то что ты описал на словах, напоминает алгоритм сканирующей линии и является вполне достойным выбором. Хотя в данном случае, как мне представляется (т.е. для треугольника) проверка каждой точки по отдельности методом Жордана особо по быстродействию не проиграет. А вот код будет простой.
И, разумеется, как сказал Akina, для начала нужно отсеять точки, не лежащие внутри экстента треугольника, это быстро.

)))) Дело в том, что я ВООБЩЕ не использую здесь перебор. Конечно идея простая как веник - взять прямоугольник, описанный вокруг треугольника и перебирать
все его точки, проверяя на принадлежность треугольнику. Но мы же не ищем простых путей! Не знаю почему, но мне в голову не пришло использовать такой 
простой способ.
Я сравню быстродействие своего алгоритма и перебора и отпишусь.
Rimch, спасибо за алгоритм определения принадлежности точки треугольнику. А то я всегда использовал другой способ: проводил отрезки от точки к вершинам треугольника и проверял их на пересечение со сторонами треугольника. Вот так: изобретаю велосипед, а получается танк с педалями.
А насчет функции TrgSqr: она же выдает вещественное число? А при вычислениях с плавающей точкой неизбежны погрешности. Так что возникает вопрос,
а может ли оказаться так, что сумма трех частей не будет равняться целому? Просто в одной моей программе из-за таких косяков строгие равенства с вещественными числами часто не работали.

   А мне вот приходится разбираться в своем коде)) Это очень непросто. Хотя что с меня взять, у меня образование очень далекое от программирования.

А вот мне интересно, как осуществляется закраска треугольников в GPU?

Тест внутри\снаружи по теореме Жордана имеет меньшую вычислительную сложность чем метод Rimch.
Привожу код на С++ для произвольного полигона; для треугольника можно использовать его же, только теругольник должен описываться 4 точками (первая равна последней):

На пальцах: проводим через точку горизонтальную прямую и считаем, сколько раз она пересекла стороны треугольника... 


Да примерно так же: определяем пересечения каждой линии сканирования со сторонами треугольника и заполняем серединку.

На счёт ошибок округления, мой студенты часто используют этот метод при решении лабораторных работ, и не разу еще не оказывалось так чтобы ошибка повлеяла на результат принадлежности. В любом методе сидит ошибка округления

касательно погрешностей - раз уж координаты точек целые вполне можно обойтись целочисленной арифметикой, где никаких погрешностей нету

касательно алгоритма в целом - не представляю, чтобы хоть какой-нибудь алгоритм, который делает какие-либо вычисления для каждой точки внутри треугольника обогнал алгоритм, который проводит только вычисления для граничных точек (по сути - немного изменённая версия исходного алгоритма в первом сообщении), т.е. вычисляем граничные точки и идём от меньшей к большей

для начала можно разбить задачу так:
- находим вершину, которая по вертикали находится между двумя другими
- разрезаем треугольник горизонтальной линией на две части
- обрабатываем отдельно обе части (для обоих будет одинаковый алгоритм)

только получившиеся части стоит представлять не в виде трёх вершин, а в виде двух лучей (либо оба вверх, либо оба вниз) и ограничивающей горизонтальной прямой, а то точка разреза не всега будет иметь целые координаты, а значит, начнутся всякие ненужные погрешности

Earnest, СРР для меня "иностранный" язык, но, насколько я понял, должен быть массив pts, а его еще нужно заполнить...
А на это тоже тратится время.
С другой стороны, если полигон - треугольник, то нечего в таком случае и перебор устраивать. Все точки от i до j будут внутри.

Сделал я вариант функции с перебором, и вот что у меня получилось:
  - мой старый алгоритм - 188 миллисекунд
  - перебор - 166 миллисекунд.
Но вот в чем фишка: у меня обсчитывается около 18000 треугольников, и у большей части из них координаты всех трех вершин совпадают.
Так что адекватно сравнить скорость работы у меня не получилось.