How to get collection of points inside polygon without holes?

Question

I have 2D polygon (integer vertices) without holes. I would like to have a collection of all the points (integer coordinates) inside polygon. Can I do it faster that checking all points within polygon's boundary and applying https://math.stackexchange.com/a/3441442/725387 for each of them? Can I apply any precomputation on polygon?

Answer 1

Since you want to implement this on a computer, here's a very simple approach, in Mathematica:

Define the region:

RR = Polygon[{{0, 0}, {5, 1}, {7, 3}, 
           {6, 8}, {4, 9}, {1, 4}, 
           {0, 0}}];

Graphics[
     {FaceForm[None], EdgeForm[Blue], RR},
     Axes -> Automatic]

Here are candidate points that span the region:

pts = Flatten[Table[{i, j}, {i, 0, 10}, {j, 0, 10}], 1];

Select the points inside the region (including boundary):

insidepts= Select[pts, RegionMember[RR]]

{{0, 0}, {1, 1}, {1, 2}, {1, 3}, {1, 4}, {2, 1}, {2, 2}, {2, 3}, {2, 4}, {2, 5}, {3, 1}, {3, 2}, {3, 3}, {3, 4}, {3, 5}, {3, 6}, {3, 7}, {4, 1}, {4, 2}, {4, 3}, {4, 4}, {4, 5}, {4, 6}, {4, 7}, {4, 8}, {4, 9}, {5, 1}, {5, 2}, {5, 3}, {5, 4}, {5, 5}, {5, 6}, {5, 7}, {5, 8}, {6, 2}, {6, 3}, {6, 4}, {6, 5}, {6, 6}, {6, 7}, {6, 8}, {7, 3}}

Show them:

Graphics[{Red, PointSize[0.03], Point[insidepts]}]

Note that there is no restriction on the region being convex, or not having holes... you just have to be careful defining such regions.

You seem concerned about timing, but this is blazingly fast on a Mac laptop..... 0.0032 seconds. For the entire code on $10^6$ points: 5.52 seconds.

Answer 2

Here’s a tip for the special case of a triangle ( e.g., as obtained from a triangulation of the original polygon: Given vertices $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ find a matrix $A\in SL_2(\Bbb Z)$ that maps the $(x_i,y_i)-(x_1,y_1)$ to $(0,0),(a,0),(0,b)$. Here the enumeration is very straightforward and can be mapped back via $A^{-1}$