3
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Triangulating a polygon is a good way to do this. The points on the sides of the triangles then become the only slightly tricky parts. $\endgroup$
    – hacatu
    Feb 9 at 4:16
1
$\begingroup$

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]

The region

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]}]

points in region

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.

$\endgroup$
1
$\begingroup$

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}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.