0

Say I have two-dimensional grid with evenly-spaced integer coordinates, and each grid position (x,y) can either be ON or OFF. Is there a way to define what shape is created by the ON positions, as a list of vertices of the polygon? With the ON grid positions roughly creating the outline of a rectangles or triangle it isn't too hard. With more complex polygons, and perhaps non-convex ones (or perhaps even two polygons side-by-side) I cannot seem to wrap my head around how to approach this.

I've seen algorithms for point-in-polygon but I'm actually looking for the opposite I guess.

It's worth mentioning that no line created by the vertices could overlap a grid point that isn't ON because, well, otherwise it would be on. i.e. if a line overlapped at (2.8, 3.1), this would imply that grid position (2, 3) would have to be on.

turbo_laser
  • 261
  • 3
  • 16
DashAnimal
  • 935
  • 1
  • 7
  • 10
  • Just thinking aloud: would it work if you calculated the convex hull of all the ON points, then took all the contiguous areas of OFF points that were caught up in the hull, and found the convex hull for them...and so on until there are no points left? – biziclop Sep 28 '15 at 16:27
  • Have you considered a [Voronoi tessellation](https://en.wikipedia.org/wiki/Voronoi_diagram)? – Rowland Shaw Sep 28 '15 at 16:28
  • What exactly is the question? Should the program output one of : "Square, Triangle, octagon, ..." or just a set of waypoints on a closed path around the ON-points? – BitTickler Sep 28 '15 at 16:32
  • Your question isn't very clear. "Is there way to define what shape...": It's defined, you have the vertices; do you mean draw edges or do you mean spit out an answer such as 'triangle'? Do you have some constraints on the shape, such as convex, or some optimization you'd want to have, such as min/max area or circumference? How about start with the S:=min(p=>p.Y), then look for the point E with min angle between SE and X that hasn't been used and doesn't intersect anything, if you run out of points move back and pick another (recursion) - slow, simplistic solution – Sten Petrov Sep 28 '15 at 16:35
  • Sorry, just to make it clear, waypoints on a closed path around on points. The actual polygonal shape could be anything and the name itself isn't important. – DashAnimal Sep 28 '15 at 16:35
  • You could use some floodfill operation first to see how many unconnected ON-groups you deal with. Then for each of the groups, you could obtain the border "ON-Points" (points which do not exclusively have ON-neighbors). They are your way points, albeit not in the desired sequence. – BitTickler Sep 28 '15 at 16:45
  • Technically, if "*more complex polygons*" are allowed then an un-ordered set of vertices is insufficient, as there is more than one "complex polygon" that can be made from 4 or more points. You need their path-order around the polygon also. – RBarryYoung Sep 28 '15 at 19:55
  • @RBarryYoung Yes with my approach, that would be a subsequent step. The first and probably least useful solution for that could be to train a kohonen network with those border points so you can get a good sequence of the points. I am sure there is something more efficient available. – BitTickler Sep 28 '15 at 22:21
  • @BitTickler No, my point is that the problem is ***not*** solvable as given, because there is no single solution. In short, the problem, as stated, is ill-defined. – RBarryYoung Sep 29 '15 at 00:26
  • @DashAnimal look at [finding hles in 2D point sets](http://stackoverflow.com/a/21884021/2521214) ... you already have the map just invert it .... – Spektre Sep 29 '15 at 06:35

0 Answers0