Генерировать сочетания из N по 4. (алгоритм генерации сочетаний) Для каждой четверки:
1)Проверить прямоугольник на невырожденность
2)Подсчитать количество прочих N-4 точек внутри (алгоритм проверки попадания точки в полигон или в два треугольника)

Представь что четырехугольник - это 4 вектора V(4). Причем конец каждого вектора смотрит в начало следующего. Направление обхода - против часовой стрелки. Для каждого вектора V:
1) Вычислить вектор U начало которого совпадает с V а конец с искомой точкой.
2) Векторное произведение (U,V) должно быть положитным для всех четырех случаев. Если оно отрицательно, значит точка по правую сторону от вектора V. То есть НЕ ПРИНАДЛЕЖИТ четырехугольнику.

Эту формулу можно использовать для любых многоугольников без самопересечений.

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

MargekMayton а почему векторное произведение вычисляется? По логике вещей там скалярное должно быть. А алгоритм хорош...
По какой логике? Поясни, почему.

РенатХмм я чуток так подумал, если нужен способ найти принадлежит ли точка многоугольнику каторый работает и для невыпуклых прямоугольников то можно сделать так?

1. перекинуть начало отчета в любую точку.
2. перебрать все возможные комбинации треугольников, где одна из вершин начало кординат
3. построить прямую через искомую точку паралельно тем двум оставимся.
4. найти расстояние между прямыми и началом кординат (привести к каноноческому виду вроде так называеться)
5. найти углы какие имеют точки относительно нач коорд.
6. если расстояние искомой точки найденой из пункта 4 по знаку одинаково и меньше чем для двух остльных, затем если угол искомой находиться между этими двумя то точка внутри треугольника, из каторого состоит искомая фигура

Когда речь идёт о комбинациях, в алгоритм вводится "комбинаторная" сложность. Это значит, что время работы алгоритма зависит не линейно а факториально от количества исходных данных. В данном случае, это будет количество вершин твоего многоугольника. Грубо говоря, для большого количества вершин (10-20) можно спокойно отправляться курить или пить кофе (или спать), пока твой алгоритм закончит работу (для проверки одной точки).

Для проверок углов ты будешь использовать сложные формулы тригонметрии, хотя тебе дан в руки аппарат, который называется "векторная алгебра". Суть твоих проверок сводится к определению следующего - "как лежит точка относительно прямой (отрезка или луча)". Я это делаю перемножением векторов. Знак векторного произведения даст тебе ориентацию точки относительно прямой. Векторное произведение вычисляется мгновенно и не имеет побочных эффектов, типа "области допустимых значений", периодичности для функций семейства arc*, которые ты обязательно впихнёшь.

Почитай также алгоритм Метод Трассировки Луча у Ласло. Подходит для невыпуклых многоугольников.

Если полигон состоит из большого количества вершин, и точек очень много (порядка 1000 и более), его можно индексировать. Я-бы предложил разбить его на трапеции, с основанием, параллельным оси X (или Y) и проверять попадение точки в соотв. Трапецию. Поиск трапеций можно выполнять дихотомически. Это позволит уйти от факториальной сложности к логарифмической (только во время проверки естесственно).

Почитай

1. Ласло, "Вычислительная геометрия и компьютерная графика на С++"
2. Шикин, Боресков "Компьютерная графика и полигональные модели".