Advertisement Jump to content
Sign in to follow this  
CGameProgrammer

Vectorizing a 1-bit raster image of polygon(s)

This topic is 1830 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a one-bit image (each pixel is either black or white) of a polygon or polygons - the edges of the image are always black. I would like to convert this to a set of one or more polygon vectors, where each vector is simply an ordered list of points (one list per polygon) describing the corners or approximating curves.

 

Attached is an example input image with red dots overlayed to show what the output points should be. It should be two lists of points of course. The threshold for placing points around a curve is arbitrary and not important.

 

The input polygons will never have holes.

 

Speed is irrelevant; this is not being done at realtime and is just precomputed.

 

The actual scenario, if you're wondering, is that I have airspace regions defined as simple polygonal regions (one list of coordinates per polygon) which are either unioned or subtracted. The sample image illustrates an example of this (not actual airspace, just a simple test). I started with a hexagon, then subtracted from it a quadrilateral (which splits the hexagon in two), then I added (unioned) a circle. Trying to directly generate vector polygons from these input polygon vectors would be maddening; I figure it's simpler to render them as raster polygons temporarily (additive is drawn in white, subtractive in black) and then convert that.

 

Step one, edge detection, becomes trivial obviously; it's any white pixel adjacent to a black pixel.

 

Step two is to create huge unsimplified ordered lists of edge points. My plan is to create a bucket of all edge pixels, then (sloppy pseudocode):

point = bucket.pop()
 
isDone = false
 
while !isDone
{
    isDone = true
 
    for all edge pixels in bucket
    {
        if this edge pixel is adjacent to point
        {
            append edge pixel to polygon points
            point = edge pixel
            isDone = false
            break;
        }
    }
}

Then if there is anything remaining in the bucket, repeat the process for the next new polygon.

 

The third and final step, and one that I definitely can't seem to figure out, is to simplify these lists of every edge into just the ones that mark the corners (or that approximate to some threshold the curves).

 

Can anyone help?

Edited by CGameProgrammer

Share this post


Link to post
Share on other sites
Advertisement

Trying to directly generate vector polygons from these would be maddening; I figure it's simpler to render them as raster polygons temporarily (additive is drawn in white, subtractive in black) and then convert that.

 

I disagree, this should be simpler, though it depends on what you want to use it for. What is the purpose of having a representation as a concave polygon?

 

If you need to check intersections or similar with the resulting shapes, then I would not precompute a final polygon shapes at all, but rather use the original simple polygons, including subtractions. This is not terribly difficult for boolean operations on constructive solid geometry (CSG). For example checking if a point is inside a tree of polygons combined through boolean operations can be easily reduced to checking only if a point is inside the simple sub-polygons and then inverting the answer depending on subtraction. You can even do subtractions of subtractions with ease, for example subtracting a rectangle from a circle, then subtracting the resulting shape from another circle, etc.

 

If you wish to go backwards from rasterization, I would probably use a flood-fill algorithm to find each complete white shape and then trace the edge of each such shape. Go through every pixel until you find a white one, flood-fill around it to find every white pixel that is connected to that pixel, and you have one shape. Then trace around it. Then remove all points that are exactly on a straight line between two other points to reduce the number of edge-points to corners.

EDIT: Actually there are easier ways, but I'll await your reply.

Edited by Erik Rufelt

Share this post


Link to post
Share on other sites

I know it's very easy to test if something is within the original simple polygons; my problem is rendering them. There is no way to directly render the original polygons that would look correct. Now it is trivial to render the raster polygons with a border; I'd just draw a circle (diameter = border thickness) at each edge pixel. The problem with that is of course it'll look blurry when stretched and pixellated when shrunk. I'd be rendering them on a map so the user would zoom a lot.

 

Also since we're dealing with pixels, they are not on a straight line due to interpolation. For example:

X
 XX
   X
    XX
Edited by CGameProgrammer

Share this post


Link to post
Share on other sites

I see. I would do CSG of the polygons. Triangulate each simple polygon for rendering, then for the subtractions you can reduce the problem to triangle/triangle subtraction, which is rather simple, especially when you don't care too much about limiting the number of triangles, and you get rid of any interpolation problems.

Share this post


Link to post
Share on other sites
I appreciate you trying to help but you keep suggesting inappropriate alternatives instead of the solution to the question I asked. In this case the polygon is added to Google Maps as a list of coordinates so it can be properly vector-drawn; adding it as a raster image would look much worse as I mentioned in the original post.

If it wasn't obvious, and maybe it wasn't, the answer I really need is the solution to step #3 in the original post: reducing an ordered list of points along the edges to just the corners (except for curves).

Share this post


Link to post
Share on other sites

the simplest way I can think of is

 

1. calculate for every vertex and line that you could 'remove' what error it would cause

2. remove the vertex or line with the lowest error.

3. goto 1

 

calculating the error:

assume you have

struct line
{
  int IndexVertex0;
  int IndexVertex1;
  std::vector<int> RemovedVertices;
};
struct Shape
{
std::vector<vec2> Vertices;
std::vector<line> Lines;
};

 

in a stupidly simple way:

cheapest=invalid;
minerror=infinity;
for_each vertex
  Shape Tmp=SourceShape
  Tmp.remove(vertex)
  error=calculate_cost(Tmp);
  if(error<minerror)...
 
for_each line
  Shape Tmp=SourceShape
  Tmp.remove(line)
  error=calculate_cost(Tmp);
  if(error<minerror)...
 
 
if(minError>maxAllowedError) return;
 
SourceShape.remove(...)

 

"remove"

not only removes a vertex or a line, BUT

-the removed vertex is added to line.RemovedVertices 

-the removed line (which also removes two vertices!) is added to line. Remove

... of the new line that spans in place of the old vertex or line

 

"calculate_cost"

accumulates the cost for every line in the shape

the cost of every line is the sum of squared shortest distances of all vertices in "RemovedVertices"

error=0;
for_each vertex in Line.RemovedVertices
    Dist=vertex.ShortestDistanceTo(Line)
    Error+=Dist*Dist

 

that's similar to quadric error metric in mesh simplification, yet with your dicritized source shape, you have a very blocky source and you want to end up with a smoother 'better' shape, that will lead to an error that will usually increase at first, but once the lines get longer and fit better the real lines, the error will decrease again. that's why you need to calculate the error per line again.

 

hope that helps :)

Share this post


Link to post
Share on other sites

I appreciate you trying to help but you keep suggesting inappropriate alternatives instead of the solution to the question I asked. In this case the polygon is added to Google Maps as a list of coordinates so it can be properly vector-drawn; adding it as a raster image would look much worse as I mentioned in the original post.

If it wasn't obvious, and maybe it wasn't, the answer I really need is the solution to step #3 in the original post: reducing an ordered list of points along the edges to just the corners (except for curves).

 

I assure you that skipping rasterization is not an inappropriate solution. But obviously there is more than one way to do things, and apologies if I misunderstood anything and good luck :)

Share this post


Link to post
Share on other sites

Your idea may have some merit Krypt0n. I'm not positive that calculating length is the right way to determine error; I worry it may either cut vital corners if it's too aggressive or fail to remove enough points on curves if it's not aggressive enough. Or both. But I can try it and see.

Edited by CGameProgrammer

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!