Re[2]: Найти количество точек лежащих внутри 2D фигуры
От: m1st  
Дата: 19.11.14 01:14
Оценка:
Здравствуйте, watchmaker, Вы писали:
W>Быстрое решение — через ориентированную площадь, наименьший общий делитель и теорему Пика.
Можно подробнее?

Формула Пика (или теорема Пика) — классический результат комбинаторной геометрии и геометрии чисел.
Площадь многоугольника с целочисленными вершинами[1] равна
В + Г/2 − 1,
где В есть количество целочисленных точек внутри многоугольника, а Г — количество целочисленных точек на границе многоугольника.
1. Точка координатной плоскости называется целочисленной, если обе её координаты целые.

Отредактировано 19.11.2014 1:17 m1st . Предыдущая версия .
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.