0

I have been given a lattice convex polygon. All I want to do is iterate through all vertices and grab the interior points near it (if possible) and only in 4 directions and of unit distance from the point.How do I do that?
Brief of what I did,
I iterate through all vertices. I take a vertex calculate slope between current vertex and the next and
if the slope is positive and Y-coord is increasing I print the (curX-1,curY).
else I print (curX+1,curY)
Similarly for slope being negative.

I leave the the cases where the slope is INF or 0.And also the cases where the previous slope was INF or 0. (optional,better methods would consider this too)

Any other better method?Is my algorithm correct? (curX=current X,curY=current Y)

Assume that the vertices are given in CCW.

Convex Polygon,the 4 valid accessible points and the two interior valid points

Sathyaram
  • 143
  • 6
  • What makes this problem so complex? The four adjacent points have nothing to do with the slope of a side. For point (x, y), the points you need are simply (x-1, y), (x+1, y), (x, y-1), (x, y+1). Please clarify. – Prune Feb 09 '18 at 19:31
  • @Prune Those are valid accessible points but I need both accessible and interior. – Sathyaram Feb 09 '18 at 19:39
  • You have both -- is the problem to *differentiate* between the two sets? – Prune Feb 09 '18 at 21:13
  • @Prune Yes differentiate and take only the interior. – Sathyaram Feb 09 '18 at 21:41
  • Possible duplicate of [How can I determine whether a 2D Point is within a Polygon?](https://stackoverflow.com/questions/217578/how-can-i-determine-whether-a-2d-point-is-within-a-polygon) – Prune Feb 09 '18 at 21:45
  • @Prune that uses a ray casting algo,Which costs O(n) complexity. So here for every vertex it requires O(4*n^2)? – Sathyaram Feb 09 '18 at 21:49
  • Your posted algorithm doesn't work: it checks only against the current segment. The point under consideration could be outside the opposite boundary of the polygon. If the algorithm doesn't have to be accurate, I can give you an **O(zero)** algorithm :-). Also, ray-casting is only one of the algorithms given; the winding algorithm is another cited. Overall, if you're doing this in C++ or compatible implementation environment, check out the `polygon` package by Lucanus Simonson in the BOOST libraries. – Prune Feb 09 '18 at 21:56
  • @Prune Well does my algo work for larger polygons(more than 10 vertices)? – Sathyaram Feb 10 '18 at 04:54
  • The failure isn't from the quantity of vertices: it's the sharpness or width of the polygon at any given vertex. – Prune Feb 12 '18 at 16:52

0 Answers0