Need algorithm suggestions: gradient-fill the polygon - how?

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Need algorithm suggestions: gradient-fill the polygon - how?

Postby makc » Mon Mar 01, 2010 10:43 pm UTC

I have specified point inside polygon, and - well - polygon. I want to paint the point white, and polygon perimiter black, and then smooth gradient inbeween. I can see how to do this easily (although not really quickly) for convex polygons, but I was thinking maybe someone on the internet knows how to do it in general case? you know, just for the sake of solution' completeness? Everything goes - pathfinding, flood-fills, etc - as long as you have an idea how to come from particular known algorithm to this specific application, please post it.
Last edited by phlip on Tue Mar 09, 2010 2:43 am UTC, edited 1 time in total.
Reason: Removed unnecessary abbrev.s in thread title.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Yakk » Tue Mar 02, 2010 3:43 pm UTC

For convex polygons, an option is to just create one triangle per side, with the 3rd vertex being the white point.

Now your problem is reduced to painting a single triangle with one corner white, and the opposite edge black, in "a smooth gradient". Can you imagine how to do this reasonably quickly?

For a non-convex polygon, the problem may become one of pathing and/or flavour, because "a smooth gradient" isn't very well defined.

For a somewhat pathological case, take a polygon that is a maze, and the white point is some arbitrary point. To determine the distance of any point in the maze from the white point, you need to solve the pathing problem on the maze. Heck, to determine what the furthest point in the maze is from the white point, you need to fully path the maze.

And even then, what you want isn't clear. You need to decide what you mean by "smooth gradient", or (even) "smooth enough gradient", because there may be solutions that are fast and easy that aren't perfectly ideal.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Tue Mar 02, 2010 5:08 pm UTC

Yakk wrote:Now your problem is reduced to painting a single triangle with one corner white, and the opposite edge black, in "a smooth gradient". Can you imagine how to do this reasonably quickly?
Well yeah, I originally thought of casting a ray from selected point through every pixel and color accordingly, but later thought about triange fan too, which is basically the same but without computation overhead.

Yakk wrote:To determine the distance of any point in the maze from the white point, you need to solve the pathing problem on the maze.
That's not a big deal, but the question is still how to map the distance into color?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Berengal » Tue Mar 02, 2010 5:46 pm UTC

makc wrote:That's not a big deal, but the question is still how to map the distance into color?
The "obvious" way is simply

Code: Select all

normalDist = dist / totalDist # where totalDist is where black begins, i.e. the point furthest from the center.
colour = white * (1 - dist) + black * dist # for some values of white, black, * and +
return colour
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Tue Mar 02, 2010 6:02 pm UTC

not so obvious, because we don't know totalDist. there's whole perimeter of black pixels, which one do we take to calculate totalDist?

User avatar
Berengal
Superabacus Mystic of the First Rank
Posts: 2707
Joined: Thu May 24, 2007 5:51 am UTC
Location: Bergen, Norway
Contact:

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Berengal » Tue Mar 02, 2010 6:16 pm UTC

Well, that depends on your definition of distance and smooth gradient, as Yakk pointed out. It's orthogonal to mapping distance -> colour.
It is practically impossible to teach good programming to students who are motivated by money: As potential programmers they are mentally mutilated beyond hope of regeneration.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Tue Mar 02, 2010 6:48 pm UTC

besides, ieven if you do have totalDist value, imagine an edge on the same line with white point. an edge itself has to be black, but line segment infinitely close to it would have significant distance gradient - how do you maintan smooth color mapping in this case?

User avatar
Aaeriele
Posts: 2127
Joined: Tue Feb 23, 2010 3:30 am UTC
Location: San Francisco, CA

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Aaeriele » Tue Mar 02, 2010 9:12 pm UTC

Yakk wrote:For a somewhat pathological case, take a polygon that is a maze, and the white point is some arbitrary point. To determine the distance of any point in the maze from the white point, you need to solve the pathing problem on the maze. Heck, to determine what the furthest point in the maze is from the white point, you need to fully path the maze.


Actually, it seems like it'd still be fairly straightforward, since you're filling the entire maze anyways - just do a breadth-first traversal through all of the pixels in the image, starting from your white point, and treating any connected adjacent pixels as connected for traversal purposes. Each time you come across a pixel that has one or more neighbors without already-assigned values, you assign those neighbors a value of one more than your current pixel's value, and then add them to the list to visit. At the end of this traversal, you'll have each pixel numbered with a value from 0 to the maximum distance, then just rescale these values to the range of your color space (fairly trivial, especially for greyscale) and you're done.

Overall algorithm still runs in O(N^2) for an NxN image.


Now, if you're instead wanting to make it so that any time you touch a wall, you're at black in the gradient (instead of only the farthest point being black), then yes, that would be a much more difficult problem.
Vaniver wrote:Harvard is a hedge fund that runs the most prestigious dating agency in the world, and incidentally employs famous scientists to do research.

afuzzyduck wrote:ITS MEANT TO BE FLUTTERSHY BUT I JUST SEE AAERIELE! CURSE YOU FORA!

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Tue Mar 02, 2010 9:21 pm UTC

Aaeriele wrote:you'll have each pixel numbered with a value from 0 to the maximum distance, then just rescale these values to the range of your color space (fairly trivial, especially for greyscale) and you're done.
Again, you are second one to miss the condition that edges must be black. Your way, only one the most distant pixel will be black.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Tue Mar 02, 2010 9:25 pm UTC

my version at the moment is this:
1 for each pixel, find path and then distance to white point (d1),
2 find distance to closest perimeter point (d2),
3 assuming 0 black and 1 white, assign color d2 / (d1 + d2).
this is still not garanteed to be smooth, but at least does not seem to have the edge problem described above. I think I will implement it and make some tests, however it is also pretty cpu intensive algorithm. there have to be a better way.

User avatar
Aaeriele
Posts: 2127
Joined: Tue Feb 23, 2010 3:30 am UTC
Location: San Francisco, CA

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Aaeriele » Tue Mar 02, 2010 9:50 pm UTC

makc wrote:
Aaeriele wrote:you'll have each pixel numbered with a value from 0 to the maximum distance, then just rescale these values to the range of your color space (fairly trivial, especially for greyscale) and you're done.
Again, you are second one to miss the condition that edges must be black. Your way, only one the most distant pixel will be black.

I didn't miss it, see my comment at the end of my post. :)

That said, I wonder if there's a way that would work for the latter problem by essentially combining the results of two breadth-first fills: one that starts at the white point, and the other which starts from the edges and fills in a reverse direction.
Vaniver wrote:Harvard is a hedge fund that runs the most prestigious dating agency in the world, and incidentally employs famous scientists to do research.

afuzzyduck wrote:ITS MEANT TO BE FLUTTERSHY BUT I JUST SEE AAERIELE! CURSE YOU FORA!

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Tue Mar 02, 2010 9:58 pm UTC

Aaeriele wrote:I wonder if there's a way that would work for the latter problem by essentially combining the results of two breadth-first fills: one that starts at the white point, and the other which starts from the edges and fills in a reverse direction.
ha, inverse flood-fill :) that may be feasible.

User avatar
Aaeriele
Posts: 2127
Joined: Tue Feb 23, 2010 3:30 am UTC
Location: San Francisco, CA

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Aaeriele » Tue Mar 02, 2010 10:20 pm UTC

makc wrote:
Aaeriele wrote:I wonder if there's a way that would work for the latter problem by essentially combining the results of two breadth-first fills: one that starts at the white point, and the other which starts from the edges and fills in a reverse direction.
ha, inverse flood-fill :) that may be feasible.


Yeah, it seems like something along the lines of "value = c*(X+a)/Y" where X is the value filled increasing from 0 at the border inwards, and Y is the value increasing from 1 at the white point outwards, then adjusted by some constants a and c, could result in fairly smooth fills that generally satisfy the requirements. Probably not that exact formula, but some kind of combination where a zero value for X would result in the minimum value, and the maximum value would be achieved when Y is at its minimum.
Vaniver wrote:Harvard is a hedge fund that runs the most prestigious dating agency in the world, and incidentally employs famous scientists to do research.

afuzzyduck wrote:ITS MEANT TO BE FLUTTERSHY BUT I JUST SEE AAERIELE! CURSE YOU FORA!

User avatar
Xanthir
My HERO!!!
Posts: 5426
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Xanthir » Fri Mar 05, 2010 10:17 pm UTC

This seems like it should be a really easy problem. Just scale and skew the polygon to match.

Start with a black polygon. Drawing lines from the white point to each point on the polygon, move along those lines proportionately, transforming the color appropriately as well, and draw the resulting polygon at each step with the new color. At the end the polygon will converge to all points coincident and white.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Fri Mar 05, 2010 10:42 pm UTC

not easy to do without self-intersections.

I am currently want to go with local gradient minimization problem solver (I'm not the one to come up with this clever-looking title) where black and white pixels serve as constraints. to put it simpler, you repeatedly draw constraints and blur the image.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Yakk » Fri Mar 05, 2010 10:48 pm UTC

It depends on what you want it to look like.

For example, you can calculate the distance your white point is from any edge.

Now, for each other point, you calculate the distance to the nearest edge, and use that to colour it.

This ends up with extra white, but you never said it couldn't have extra white.

Another option is to take the distance from the given location to both the white point and the nearest edge. This gives you two values -- W and B.

When W = 0, we want all white. When B = 0, we want all-black.

Imagine a quadrant of the plane. The x axis is white, the y axis is black, and the (0,0) point is undefined. The rest of the square is a gradient between white and black, determined by the ratio of x and y (if x=y, then it is 50% grey).

Use that to map your W and B values to a greyscale value.

Now, all you need is for each pixel to have the distance to the white point, and the distance to the nearest black edge.

Oh, and toss in a gamma function, so you can change the shape of the curve between white and black. Otherwise, black will dominate most of a really complex structure. You could even have the gamma function be determined in such a way that the figure will be, on average, 50% grey.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Sun Mar 07, 2010 7:15 pm UTC

makc wrote:I am currently want to go with local gradient minimization problem solver (I'm not the one to come up with this clever-looking title) where black and white pixels serve as constraints. to put it simpler, you repeatedly draw constraints and blur the image.
this does not work http://megaswf.com/view/dc3441f43c7f246 ... 4955d.html back to flood-fills idea.


makc wrote:3 assuming 0 black and 1 white, assign color d2 / (d1 + d2).
this does not work at all, ha ha... sigh :(


Aaeriele wrote:"value = c*(X+a)/Y"
this looks promising:
http://megaswf.com/view/52ec1983b12c8f8 ... 5b8fb.html

now to figure out how to speed it up...


Triple post condensed. Please use the edit feature instead of making multiple consecutive posts. -Hodge.

User avatar
Emu*
Posts: 689
Joined: Mon Apr 28, 2008 9:47 am UTC
Location: Cardiff, UK
Contact:

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby Emu* » Wed Mar 10, 2010 9:21 am UTC

Here's an idea I had, not sure if this would make the fill you wanted. [Assumes this is not purely raster graphics]
Image

Take one nice fill, about 1 pixel per shade (i.e. 256 pixels usually)

Divide polygon into triangles.

Calculate distance between point and line (white line on diagram), and scale the gradient accordingly.

draw the gradient along the line (e.g. in the direction of the arrow)

use the triangle as a mask to snip off any excess

repeat.

result: white at point, black at edge, linear colour change along any edge point and the centre point.
Cosmologicon wrote:Emu* implemented a naive east-first strategy and ran it for an hour, producing results that rivaled many sophisticated strategies, visiting 614 cells. For this, Emu* is awarded Best Deterministic Algorithm!

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby makc » Wed Mar 10, 2010 9:41 am UTC

Thanks, but...
Yakk wrote:For convex polygons, an option is to just create one triangle per side, with the 3rd vertex being the white point.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby jaap » Wed Mar 10, 2010 9:43 am UTC

That works if the polygon is convex (in fact, you only need every boundary point to be visible from the chosen point).
But what if that is not the case? For example a U-shaped area with the chosen point in one of the arms of the U.

User avatar
Zamfir
I built a novelty castle, the irony was lost on some.
Posts: 7605
Joined: Wed Aug 27, 2008 2:43 pm UTC
Location: Nederland

Re: need alg. sugg.: gradient-fill the polygon - how?

Postby Zamfir » Wed Mar 10, 2010 1:19 pm UTC

Yakk wrote:It depends on what you want it to look like.

For example, you can calculate the distance your white point is from any edge.

Now, for each other point, you calculate the distance to the nearest edge, and use that to colour it.

This ends up with extra white, but you never said it couldn't have extra white.

Another option is to take the distance from the given location to both the white point and the nearest edge. This gives you two values -- W and B.

When W = 0, we want all white. When B = 0, we want all-black.

Imagine a quadrant of the plane. The x axis is white, the y axis is black, and the (0,0) point is undefined. The rest of the square is a gradient between white and black, determined by the ratio of x and y (if x=y, then it is 50% grey).

Use that to map your W and B values to a greyscale value.

Now, all you need is for each pixel to have the distance to the white point, and the distance to the nearest black edge.

Oh, and toss in a gamma function, so you can change the shape of the curve between white and black. Otherwise, black will dominate most of a really complex structure. You could even have the gamma function be determined in such a way that the figure will be, on average, 50% grey.


This could work I guess, but you would probably want to calculate the distance to the white point through a path internal to the polygon, which is doable but not trivial.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby Yakk » Wed Mar 10, 2010 3:14 pm UTC

Ya -- how you define W and B can change the look a lot.

In general, if you want the white/black to reflect the "on ground" distance, you have to solve the pathing problem, as you can extract the pathing problem from the colour of the pixels.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

not baby Newt
Posts: 110
Joined: Wed Feb 03, 2010 11:30 pm UTC

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby not baby Newt » Fri Mar 12, 2010 5:55 pm UTC

I'll call the white point 'start'. Let's say we have a maze-like polygon, and that for any edge point there should exist a smooth gradient to the start along some path. This path should also stay reasonable far away from any edge.

First, put a grid over the polygon.

For each point in the polygon, let A be the distance to the closest edge. (Breadth first from the edge?)

From each edge point, pathfind to the start using a (or 1/a rather) as the cost to traverse a point. Perhaps by a breadth first search from the start.

For each edge point, in decending distance from start:
- Find the first colored point along the path towards the start.
- Paint a gradient along this path, from black to whatever color was found.

Then do the same for any still blank non-edge points.

Done!

Not sure how bad the complexity for this is, but you didn't say it had to be fast :)

User avatar
jroelofs
Posts: 77
Joined: Tue Apr 01, 2008 9:26 pm UTC
Location: Nashua, NH
Contact:

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby jroelofs » Wed Mar 31, 2010 8:53 pm UTC

Your polygons can probably be realized as a finite union of convex polyhedra, in which case you can use fourier-motzkin elimination to scan across all the points of each of the convex parts. Then you would need to use a little bit of trig to figure out the point of intersection of the ray drawn from the centroid through the point to the bounding line that it first intersects with. Take the color of the point to be the ratio: dist(edge point, point to color) / dist(point to color, centroid). This gives a polygon where edges that are near the outside of the polygon scale toward black, however it may not do what you are expecting for concave polygons. You'd have to come up with a smarter way of figuring out which constraints are used to define the color.

Correct me if I'm wrong, but I believe this gives an O(C*N^2) algorithm where N is the number of constraints in each chunk, and C is the number of chunks.

nzqrc
Posts: 2
Joined: Mon Apr 26, 2010 4:00 am UTC

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby nzqrc » Mon Apr 26, 2010 4:10 am UTC

Two questions.
1: How important is it that the brightness converge to a single point? For example, if your polygon was shaped like a french fry, would you want the ends to be almost totally black, or would it be OK to have a white line going down the fry?
2: Are you working on a bitmap grid of finite resolution, or do you need scalability?

If the single point isn't vital, and you're using bitmaps, you could use binary morphological operators. First render the polygon as 1s in a field of zeros on your 2D array. Then use morphological erode repeatedly, and keep track of which pixels get eroded each time. Use a second integer array to keep track. For example, if a pixel goes from white to black on the 37th erode, its value should be 37. Eventually, all the pixels will be black. Scale the grey values up to 255, and you've got the gradient.

shieldforyoureyes
Posts: 342
Joined: Sat Apr 19, 2008 9:00 am UTC
Contact:

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby shieldforyoureyes » Mon Apr 26, 2010 5:10 am UTC

Make the perimeter black, and the point white, then average all other points with their neighbors repeatedly until they stop changing.

Or do a full heat-flow simulation.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby makc » Mon Apr 26, 2010 5:29 am UTC

shieldforyoureyes wrote:Make the perimeter black, and the point white, then average all other points with their neighbors repeatedly until they stop changing.
That does not work, lots of black points outweight single white dot, and the polygon turns out very dark.

shieldforyoureyes
Posts: 342
Joined: Sat Apr 19, 2008 9:00 am UTC
Contact:

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby shieldforyoureyes » Mon Apr 26, 2010 5:50 am UTC

makc wrote:
shieldforyoureyes wrote:Make the perimeter black, and the point white, then average all other points with their neighbors repeatedly until they stop changing.
That does not work, lots of black points outweight single white dot, and the polygon turns out very dark.


That sounds like a very trivial scaling problem for converting to the final image format.

makc
Posts: 181
Joined: Mon Nov 02, 2009 12:26 pm UTC

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby makc » Mon Apr 26, 2010 6:08 am UTC

no it doesnt. in fact, i have problems to even imagine what "a very trivial scaling problem for converting to the final image format" is :(

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby Yakk » Mon Apr 26, 2010 3:27 pm UTC

Rescaling it isn't hard. The problem is that the described algorithm takes forever.

To rescale, do it at a ridiculous precision (to avoid aliasing in the next step). Then build a histogram of the values, and place the pixels uniformly along the gradient you want. Finally, possibly do some blurring along the edges of any large clumps.

The "smoothing" is O(number of pixels) or so, while the initial "repeated averaging" is going to be ridiculously computationally expensive and completely infeasible on any decent sized image. The influence of the white pixel will spread at a rate of 1 pixel/average, and each average takes O(# of pixels). So just to hit the point where any white influence reaches the edge of the image takes O(n^(3/2)) time. How long it takes to stabilize (if it ever does -- I could believe it would, but I would want to see a proof and many experiments before signing off) is yet another question.

(With the above, I'm assuming that the edge/center pixel is never changed by the averaging process).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
StickFigure206
Posts: 12
Joined: Mon Jan 31, 2011 7:06 pm UTC
Location: Ballard, Seattle, Washington

Re: Need algorithm suggestions: gradient-fill the polygon -

Postby StickFigure206 » Wed Feb 02, 2011 4:35 pm UTC

this looks promising:
http://megaswf.com/view/52ec1983b12c8f8 ... 5b8fb.html

now to figure out how to speed it up...


Out of everything I have seen listed on this thread, this link is the one that helped me out the most. I'm not going to lie, I didn't mess around with this kind of stuff at all until I saw this thread, so I am not the best resource, but I guess I am saying that for usability and complexity this is a pretty good place to start speedy or not. At least it helps right?

StickFig
"I'm a stick figure sprinter. Sometimes my legs break, sometimes I slip and fall, but I'm fast I tell ya, darn fast!"
http://www.youtube.com/watch?v=4396710


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 8 guests