How to define corner / vertex cells in freeform made up of grid cells
I am dealing with polygons made up of square slabs on a 2D grid. The polygon is simply stored as a list of tuples, with each tuple representing the coordinates of a tile. Polygons are always adjacent and have no holes.
What I want to do is determine which of the slices represents the vertices along the border of the polygon, so that later I could track between them to create the border of the polygon, or determine the distance between two successive vertices to find the length of the side, etc. ...
Here's an example of a polygon (a 5x4 rectangle with a 3x2 rectangle subtracted from the top-left corner to create an inverse "L"):
polygon_tiles = [(3, 0), (4, 0), (3, 1), (4, 1), (0, 2), (1, 2), (2, 2), (3, 2), (4, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
Ideally, the algorithm I'm looking for will give a result that looks like this:
polygon_verts = [(3, 0), (4, 0), (4, 3), (0, 3), (0, 2), (3, 2)]
with the vertices indicated to trace around the border in a clockwise direction.
Just fiddling around with some test cases, this problem seems a lot harder than I would think, especially in weird situations like when the polygon has a 1 slab width extrusion (in which case one of the tiles could be saved as vertices twice).
I am working in Python, but any understanding is appreciated, even if it is in pseudocode.
source to share
Assuming your figure has no inner holes.
Find the top line. Select the left side of this line. This will ensure that we start at the corner.
From this tile, try to go straight to the right. If you cannot, go straight ahead, straight down, etc., until you get a direction. This ensures that we can trace the perimeter clockwise of the polygon.
Continue taking steps in the direction you choose. After each step:
- If the next step is on a tile, turn counterclockwise and look again.
- If the next step is on an empty spot, rotate it clockwise and look again.
Stop spinning as soon as you move to an empty spot and return to the tile again.
If we turned from the starting direction, we should be at the top. Mark it as such.
Mark all other pieces that you cross as part of the edge.
Continue along the edge until you reach the starting tile. You can walk over the tiles more than once in the case of 1 tile extrusion.
If this algorithm doesn't make sense in your head, try pulling out some paper and after it by hand :)
source to share
I would just calculate the slopes of the lines between the vertices
# Do sort stuff
vertices = []
for position, polygon in enumerate(polygon_tiles):
# look for IndexErrors
try:
polygon_tiles[position+1]
except IndexError:
break
try:
polygon_tiles[position+2]
except IndexError:
# Bad practice
position = position - 1
# calculate the slope of the line between of vertex 1 and vertex 2
s1 = (polygon_tiles[position+1][1] - polygon[1]) / (polygon_tiles[position+1][0] - polygon[0])
# calculate the slope of vertex 2 and vertex 3
s2 = (polygon_tiles[position+2][1] - polygon_tiles[position+1][1]) / (polygon_tiles[position+2][0] - polygon_tiles[position+1][0])
# if the slopes differ then you have a vertex
if d1 != d2:
vertices.append(polygon_tiles[position+1])
source to share
This problem is a variant of a convex hull , for which, for example, a gift wrapping algorithm can be applied . Limitations of discrete coordinates and direction of lines lead to simplifications. Here is some python code that gives the desired answer (Patash's answer in the same vein):
#!/usr/bin/python
import math
def neighbors(coord):
for dir in (1,0):
for delta in (-1,1):
yield (coord[0]+dir*delta, coord[1]+(1-dir)*delta)
def get_angle(dir1, dir2):
angle = math.acos(dir1[0] * dir2[0] + dir1[1] * dir2[1])
cross = dir1[1] * dir2[0] - dir1[0] * dir2[1]
if cross > 0:
angle = -angle
return angle
def trace(p):
if len(p) <= 1:
return p
# start at top left-most point
pt0 = min(p, key = lambda t: (t[1],t[0]))
dir = (0,-1)
pt = pt0
outline = [pt0]
while True:
pt_next = None
angle_next = 10 # dummy value to be replaced
dir_next = None
# find leftmost neighbor
for n in neighbors(pt):
if n in p:
dir2 = (n[0]-pt[0], n[1]-pt[1])
angle = get_angle(dir, dir2)
if angle < angle_next:
pt_next = n
angle_next = angle
dir_next = dir2
if angle_next != 0:
outline.append(pt_next)
else:
# previous point was unnecessary
outline[-1]=pt_next
if pt_next == pt0:
return outline[:-1]
pt = pt_next
dir = dir_next
polygon_tiles = [(3, 0), (4, 0), (3, 1), (4, 1), (0, 2), (1, 2), (2, 2), (3, 2),
(4, 2), (0, 3), (1, 3), (2, 3), (3, 3), (4, 3)]
outline = trace(polygon_tiles)
print(outline)
source to share