Re: Найти количество точек лежащих внутри 2D фигуры
От: Mr WeL Россия  
Дата: 15.11.14 13:16
Оценка:
Здравствуйте, m1st, Вы писали:

M>Условие задачи:

M>Image: 11.15.2014-10.32.png

M>Подскажите, куда копать?


Cоставить уравнение прямой проходящей через две точки.

ax + by + c = 0

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

берем точки (x1, y1) (x2, y2) (x3, y3) (x4, y4) (x1, y1)

и составляешь 4 прямые:

p1(x,y): (x1,y1)(x2,y2)
p2(x,y): (x2,y2)(x3,y3)
p3(x,y): (x3,y3)(x4,y4)
p4(x,y): (x4,y4)(x1,y1)

для точек лежащих внутри 2д фигуры, значение всех выражение pi (i=1..4) будет одного знака
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.