CGameProgrammer

Members
  • Content count

    4264
  • Joined

  • Last visited

Community Reputation

640 Good

About CGameProgrammer

  • Rank
    Contributor
  1. Vectorizing a 1-bit raster image of polygon(s)

    I'm too lazy right now to make the code neatly arranged so attached is the quick'n'dirty code. It's a C# console application that reads an image, figures out the required points, and outputs an image showing them. It also outputs intermediate images showing the steps taken to get to that point. I've also attached one of these sample output images.   EDIT: Apparently it doesn't let me attach source code files. Well here is the entire file: using System; using System.Collections.Generic; using System.Drawing; using System.Drawing.Imaging; namespace Vector { struct Point { public static readonly Point Zero = new Point(0,0); public double X; public double Y; public Point (double x, double y) { X = x; Y = y; } public override string ToString () { return "{" + X + "," + Y + "}"; } } class Polygon { public List<Point> Points; public Polygon () { Points = new List<Point>(); } } class Path { public List<Point> Points; public bool[,] EdgeMap; public Path (bool[,] edgeMap, IEnumerable<Point> points) { EdgeMap = (bool[,])edgeMap.Clone(); Points = new List<Point>(); Points.AddRange(points); } } class Program { static readonly double EDGE_OFFSET_THRESHOLD = 1; static readonly string INPUT_PATH = @"A:\Data\shape.png"; static void Main (string[] args) { Bitmap bmp = (Bitmap) Image.FromFile(INPUT_PATH); bool[,] edgeMap; int edgeCount; FindEdges(bmp, out edgeMap, out edgeCount); Bitmap output = new Bitmap(bmp.Width, bmp.Height); for (int y = 0; y < bmp.Height; y++) for (int x = 0; x < bmp.Width; x++) { if (edgeMap[x,y]) output.SetPixel(x, y, Color.White); else output.SetPixel(x, y, Color.Black); } output.Save(INPUT_PATH + ".edges.png", ImageFormat.Png); // Now find the polygons: List<Polygon> polygons = new List<Polygon>(); while (edgeCount > 0) { // Remove any point to start a new polygon Point point = FindRandomEdge(edgeMap); edgeMap[(int) point.X, (int) point.Y] = false; // Create the first path Path path = new Path(edgeMap, new Point[0]); path.Points.Add(point); List<Path> paths = new List<Path>(); paths.Add(path); EvaluatePath(path, paths); // Now look through the list of paths to find the one(s) with the // most points. There may be two with the same number of points; // just choose the first one arbitrarily in that case. Path bestPath = null; int bestCount = 0; foreach (Path option in paths) { Point first = option.Points[0]; Point last = option.Points[option.Points.Count-1]; // Look for the path that has all the points and that // correctly forms a closed polygon. if (first.X >= last.X-1 && first.X <= last.X+1 && first.Y >= last.Y-1 && first.Y <= last.Y+1 && option.Points.Count > bestCount) { bestCount = option.Points.Count; bestPath = option; } } edgeCount -= bestCount; // Create the new polygon Polygon polygon = new Polygon(); polygon.Points.AddRange(bestPath.Points); polygons.Add(polygon); edgeMap = bestPath.EdgeMap; } output = new Bitmap(bmp.Width, bmp.Height); for (int y = 0; y < bmp.Height; y++) for (int x = 0; x < bmp.Width; x++) output.SetPixel(x, y, Color.Black); for (int n = 0; n < polygons.Count; n++) { for (int p = 0; p < polygons[n].Points.Count; p++) output.SetPixel((int) polygons[n].Points[p].X, (int) polygons[n].Points[p].Y, GetPolygonColor(n)); } output.Save(INPUT_PATH + ".polygons.png", ImageFormat.Png); // Now we need to remove useless edge pixels until we only have the corners remaining. foreach (Polygon polygon in polygons) { int p = 0; while (p < polygon.Points.Count) { Point start = polygon.Points[p]; int removeCount = 0; for (int n = 2; n < polygon.Points.Count; n++) { int endIndex = (p+n) % polygon.Points.Count; Point end = polygon.Points[endIndex]; bool removeToEnd = true; // Now see if all pixels between start and end are within the allowed distance // from the line from start to end. If so then keep going. Otherwise we are done // and can eliminate any pixels between start and end. for (int m = 1; m < n; m++) { int middleIndex = (p+m) % polygon.Points.Count; Point middle = polygon.Points[middleIndex]; double distance = GetPointSegmentDistance(middle, start, end); if (distance > EDGE_OFFSET_THRESHOLD) { // We've found a pixel that must not be removed so stop here. removeToEnd = false; break; } } if (removeToEnd) removeCount = n-1; else break; } if (removeCount > 0) { int firstRemoval = (p+1) % polygon.Points.Count; int lastRemoval = (p+removeCount) % polygon.Points.Count; // We've found at least one pixel to remove. if (firstRemoval <= lastRemoval) { polygon.Points.RemoveRange(firstRemoval, 1+lastRemoval-firstRemoval); p++; } else { polygon.Points.RemoveRange(firstRemoval, polygon.Points.Count - firstRemoval); polygon.Points.RemoveRange(0, 1+lastRemoval); break; } } else p++; } } for (int n = 0; n < polygons.Count; n++) { for (int p = 0; p < polygons[n].Points.Count; p++) output.SetPixel((int) polygons[n].Points[p].X, (int) polygons[n].Points[p].Y, Color.White); } output.Save(INPUT_PATH + ".corners.png", ImageFormat.Png); } static void FindEdges (Bitmap bmp, out bool[,] edgeMap, out int edgeCount) { edgeMap = new bool[bmp.Width, bmp.Height]; edgeCount = 0; // Important: do not count diagonals. for (int y = 1; y < bmp.Height-1; y++) { for (int x = 1; x < bmp.Width-1; x++) { if (bmp.GetPixel(x, y).R > 0) { // This is a foreground pixel (part of the polygon). // Count how many surrounded pixels are the background. int count = (bmp.GetPixel(x-1, y).R == 0 ? 1 : 0) + (bmp.GetPixel(x+1, y).R == 0 ? 1 : 0) + (bmp.GetPixel(x, y-1).R == 0 ? 1 : 0) + (bmp.GetPixel(x, y+1).R == 0 ? 1 : 0); if (count > 0 && count < 4) { // It counts as an edge edgeMap[x, y] = true; edgeCount++; } } } } // Now we have to eliminate any edge pixels that are adjacent (including diagonally) // to only one other edge pixel; they are dead-ends. bool outliersFound = true; while (outliersFound) { outliersFound = false; for (int y = 1; y < bmp.Height-1; y++) { for (int x = 1; x < bmp.Width-1; x++) { if (edgeMap[x, y]) { int count = (edgeMap[x-1, y-1] ? 1 : 0) + (edgeMap[x-1, y] ? 1 : 0) + (edgeMap[x-1, y+1] ? 1 : 0) + (edgeMap[x, y-1] ? 1 : 0) + (edgeMap[x, y+1] ? 1 : 0) + (edgeMap[x+1, y-1] ? 1 : 0) + (edgeMap[x+1, y] ? 1 : 0) + (edgeMap[x+1, y+1] ? 1 : 0); if (count == 1) { edgeMap[x, y] = false; edgeCount--; outliersFound = true; } } } } } } static double GetPointLineDistance (Point p, Point lineA, Point lineB) { double length = GetLength(lineA, lineB); double xAP = lineA.X - p.X; double yAP = lineA.Y - p.Y; double xBA = (lineB.X - lineA.X) / length; double yBA = (lineB.Y - lineA.Y) / length; return (xAP * yBA) - (yAP * xBA); } static double GetNearestPointOffsetOnLine (Point p, Point lineA, Point lineB) { double xAP = p.X - lineA.X; double yAP = p.Y - lineA.Y; double xAB = lineB.X - lineA.X; double yAB = lineB.Y - lineA.Y; double ABdotAB = (xAB*xAB) + (yAB*yAB); double APdotAB = (xAP*xAB) + (yAP*yAB); if (ABdotAB != 0) return APdotAB / ABdotAB; else return double.NaN; } static Point GetPointOnLine (Point lineA, Point lineB, double offset) { double x = lineA.X + (offset * (lineB.X - lineA.X)); double y = lineA.Y + (offset * (lineB.Y - lineA.Y)); return new Point(x, y); } static double GetPointSegmentDistance (Point p, Point segmentA, Point segmentB) { double offset = GetNearestPointOffsetOnLine(p, segmentA, segmentB); if (offset <= 0) return GetLength(p, segmentA); else if (offset >= 1) return GetLength(p, segmentB); else return GetLength(p, GetPointOnLine(segmentA, segmentB, offset)); } static double GetLength (Point p1, Point p2) { double dx = p1.X - p2.X; double dy = p1.Y - p2.Y; return Math.Sqrt((dx*dx) + (dy*dy)); } static Color GetPolygonColor (int index) { switch (index) { case 0: return Color.FromArgb(64, 0, 0); case 1: return Color.FromArgb(64, 64, 0); case 2: return Color.FromArgb(0, 64, 0); case 3: return Color.FromArgb(0, 64, 64); case 4: return Color.FromArgb(0, 0, 64); case 5: return Color.FromArgb(64, 0, 64); default: return Color.FromArgb(64, 64, 64); } } static void EvaluatePath (Path path, IList<Path> allPaths) { while (true) { List<Point> adjacent = FindAdjacentEdges(path.EdgeMap, path.Points[path.Points.Count-1]); if (adjacent.Count >= 2) { // Multiple options so create new paths for each option. for (int a = 0; a < adjacent.Count; a++) { Path branch = new Path(path.EdgeMap, path.Points); branch.Points.Add(adjacent[a]); branch.EdgeMap[(int) adjacent[a].X, (int) adjacent[a].Y] = false; allPaths.Add(branch); EvaluatePath(branch, allPaths); } // This path must be abandoned now. break; } else if (adjacent.Count == 1) { // Only one direction to go. path.Points.Add(adjacent[0]); path.EdgeMap[(int) adjacent[0].X, (int) adjacent[0].Y] = false; } else { // No more adjacent pixels; we're done with this path break; } } } static Point FindRandomEdge (bool[,] edgeMap) { for (int y = 1; y < edgeMap.GetLength(1)-1; y++) for (int x = 1; x < edgeMap.GetLength(0)-1; x++) { if (edgeMap[x, y]) return new Point(x, y); } return Point.Zero; } static List<Point> FindAdjacentEdges (bool[,] edgeMap, Point point) { List<Point> list = new List<Point>(); for (int y = (int) point.Y-1; y <= (int) point.Y+1; y++) for (int x = (int) point.X-1; x <= (int) point.X+1; x++) { if (x == point.X && y == point.Y) continue; if (edgeMap[x, y]) list.Add(new Point(x, y)); } return list; } } }
  2. Vectorizing a 1-bit raster image of polygon(s)

    Update: I had implemented the length-based solution but found that it did not work perfectly; it seemed to eliminate curve definition too much or it allowed unnecessary pixels to remain. I came up with a different technique: for each pixel, I find the longest chain of pixels following it that are near the line drawn from the first pixel to the last of the chain. Then I remove all the pixels between the start and end. This nicely handles all sloped lines and can precisely determine the corner pixels.   I'll post code and sample images later. The code is really sloppy right now but I'll try to clean it up a bit first.
  3. Anybody left from the 2003 crowd?

    I've been here since 1999 but barely post anymore...
  4. Vectorizing a 1-bit raster image of polygon(s)

    Actually I was thinking more about your original idea and I think it would be the solution after all. I was thinking that vertices would be eliminated if the length error of their absence is within a certain margin, but the actual solution (and what I believe you were trying to say) is to only remove the single least useful vertex after evaluating all of them, and then repeat, until the error from removing any remaining vertex is above the threshold. As the least useful vertices are removed, the error from removing the remaining ones becomes much larger and so they would not be erroneously removed.   Last night I wrote the code to complete step #2 (creating the ordered lists of points for each polygon) so today I will write the simplification algorithm and let you know how it goes.
  5. Vectorizing a 1-bit raster image of polygon(s)

    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.
  6. Vectorizing a 1-bit raster image of polygon(s)

    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).
  7. Vectorizing a 1-bit raster image of polygon(s)

    No, that would not work because I am not rendering a triangular mesh; the output must be the list of points that define the polygon's border.
  8. Vectorizing a 1-bit raster image of polygon(s)

    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
  9. 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?
  10. Get points of a 3d triangle relative to its own plane in 2d

    It's easiest to arbitrarily declare one of the triangle's sides as being parallel to the X or Y axis. So if you have a triangle and say its first side is 4 units long. You can just start by saying its two endpoints are at {0,0} and at {4,0}. Then you just have to calculate the position of the remaining point. You know the lengths of the other two sides; it's exactly same in 3D as in 2D since the triangle lies along a plane, and you can easily find equations online for finding the point given that you know all lengths (and all angles, as a result).
  11. Create a sphere that intersects another at right angles

    The solution I've come up with is, since as an input I have the circle's radius along the surface of the Earth (not straight-line radius): sphereRadius = earthRadius * tan(circleRadius / earthRadius); sphereCenterDistance = sqrt( earthRadius^2 + sphereRadius^2 ); CircleRadius / EarthRadius gives the radians of the arc covered by the circle (or half of it since this is radius and not diameter). sphereCenterDistance is the distance along the center axis where the sphere's center lies. So with those two things I have my sphere. I would assume any solution that does not involve trigonometric functions would be wrong; maybe you just hadn't realized my circle's radius is measured along the Earth's surface.
  12. Create a sphere that intersects another at right angles

    Wait, I think I can utilize what quasar3d noted about there being a right triangle from the earth's center, the red sphere's center, and a tangent point. I was thinking I only knew one side (earth's radius) and one angle (90 at the tangent) but of course I can calculate the angle at the Earth's center, and then that would be enough information to invoke Pythagorean. And I already know that angle since it's trivial to calculate given the radius of the intersection circle along the Earth's surface; you just divide by the Earth's radius and that gives you radians.
  13. Create a sphere that intersects another at right angles

    Speed matters and getting the intersection of two 3D vectors constrained to some arbitrary plane does not seem like the correct solution. There must be a more direct way.
  14. Create a sphere that intersects another at right angles

    I still can't come up with a solution. Remember that are an infinite number of points where the two spheres intersect because this is 3D. How do I find the 3D cartesian center and radius of the red sphere given its center axis (relative to the blue sphere's center) and the radius of the intersection circle?
  15. I need to find the center and radius of a 3D cartesian sphere that intersects another sphere at right angles. Illustration: [attachment=5946:Circles.png] [b]Knowns: * Center of the blue sphere, which is centered at the origin in fact (0,0,0) * Radius of the blue sphere * Axis along which the center of the red sphere lies (also intersection point of the axis with the blue sphere) * Distance between the two red dots[/b] Basically the blue sphere is Earth and I need to generate a cartesian sphere representing a circle on the surface of the Earth. I've done this already except that my circles are centered on the Earth's surface (red dot) which means they don't intersect the ground at right angles like the red circle roughly does. This causes certain math routines to fail. So I need to find the center/radius of the red circle drawn in the illustration. I know that, on a 2D picture, if you draw tangents of the blue circle where the red circle intersects it, the intersection of those two tangents marks the center of the red circle. Still don't know how to correlate this with the above 3D inputs to find what I need. Can anyone help?