CODEWITHSUNDEEP
algorithmgeometry2dlineregion
darius16777
darius16777

Reputation: 31

Algorithm to evaluate pixels based on the minimum amount of line segments required to reach a certain point, while only crossing valid areas?

Given a 2D pixel array where any pixel can be either 0 or 1, what algorithm would output a new 2D pixel array, where each pixel with a value of 1 would get a new value based on the minimum amount of line segments required to reach a specific "light source" pixel, while only crossing pixels that have an input value of 1? Input values of 0 would not change.

Example of input array, magenta cross represents the "light source" pixel:

https://cdn3.imggmi.com/uploads/2019/1/8/2a5f6dd0ebdc9c72115f9ce93af3337a-full.png

Output array with output values 1 and 2 (Photoshopped, not a pixel perfect image):

https://cdn3.imggmi.com/uploads/2019/1/8/0025709aaa826c26ee0a8e17476419cb-full.png

(The algorithm wouldn't stop at 3, it would continue until every pixel is evaluated.)

EDIT: I'm not sure whether StackOverflow is the right Stack Exchange site to post this in, if not please let me know!

Upvotes: 3

Views: 62

Answers (1)

Prune
Prune

Reputation: 77860

Make your point of origin the origin of a polar coordinate system. Convert the block corners to polar coordinates.

Now, treat your point source as a searchlight, sweeping from 0 to 2*PI. The beam continues until it hits the frame edge or a black box. This defines a polygon that you fill with magenta (1 line segment, direct lighting).

That's the easy part. Now you get to repeat this for every pixel that lies on a magenta-white (1-0) boundary of the polygon. This defines a finite set of secondary polygons; fill those with yellow (code 2).

Repeat this process with the yellow-white (2-0) boundaries to identify the 3 pixels; iterate until you run out of pixels.

In other paradigms, I've applied interval algebra to blocking segments (e.g. where one block partially shadows another), but I think that the polar polygon attack will get you to a solution in fewer hours of coding.

Upvotes: 1

Related Questions