Разложить треугольник запроса на n * 3 строки.Для каждой тестируемой точки вы можете оценить, на какой стороне каждой линии она находится.Все остальное - логическая логика.
РЕДАКТИРОВАТЬ: поскольку ваши точки растеризуются, вы можете предварительно вычислить точки на линиях сканирования, где линия сканирования входит в конкретный треугольник запроса или выходит из него (= пересекает одну из 3n строк выше && включена«внутрь» двух других линий, которые участвуют в этом конкретном треугольнике)
ОБНОВЛЕНИЕ: инициировано другой темой ( Как узнать, находится ли точка в треугольнике в 3D? )Я добавлю код, чтобы доказать, что невыпуклый случай можно выразить в терминах "на какой стороне каждой линии находится точка".Поскольку я ленивый, я буду использовать L-образную форму.ИМХО другие невыпуклые формы можно обрабатывать аналогично.Линии параллельны осям X и Y, но это опять-таки лень.
/*
Y
| +-+
| | |
| | +-+
| | |
| +---+
|
0------ X
the line pieces:
Horizontal:
(x0,y0) - (x2,y0)
(x1,y1) - (x2,y1)
(x0,y2) - (x1,y2)
Vertical:
(x0,y0) - (x0,y2)
(x1,y1) - (x1,y2)
(x2,y0) - (x2,y1)
The lines:
(x==x0)
(x==x1)
(x==x2)
(y==y0)
(y==y1)
(x==y2)
Combine them:
**/
#define x0 2
#define x1 4
#define x2 6
#define y0 2
#define y1 4
#define y2 6
#include <stdio.h>
int inside(int x, int y)
{
switch( (x<x0 ?0:1)
+(x<x1 ?0:2)
+(x<x2 ?0:4)
+(y<y0 ?0:8)
+(y<y1 ?0:16)
+(y<y2 ?0:32) ) {
case 1+8:
case 1+2+8:
case 1+8+16:
return 1;
default: return 0;
}
}
int main(void)
{
int xx,yy,res;
while (1) {
res = scanf("%d %d", &xx, &yy);
if (res < 2) continue;
res = inside(xx, yy);
printf("(%d,%d) := %d\n", xx, yy,res);
}
return 0;
}