3

I'm trying to build a function that extends from a specific coordinate at a given angle, and loops through the pixels on that line until it encounters a black pixel.

This is easily implemented if the angle is, for example, 180 degrees. In this case, the search would only extend downwards, adding 1 to the column coordinate in each iteration. However, an angle of e.g. 10 degrees is more complex. I therefore need to presumably mathematically calculate the next pixel at pixel position X.

This answer in a similar question did not help me as the values on the y-axis don't change as expected:

import numpy as np
angle = 90*np.pi/180

x = np.arange(0, 10)
y = np.round(np.sin(angle)*x).astype(int)
print([(x, y) for x, y in zip(x, y)])

prints: [(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7), (8, 8), (9, 9)]
Which is wrong since I don't expect the y-axis to change, given the 90-degree angle.

The answer to this other question requires a second 'end' coordinate, which I don't have.

Lastly, I found this question, which unfortunately does not have a valid answer. The code in the question seems to return no offsets but floats, whose meaning I am unsure of. When I round the floats, the offsets are wrong:

import numpy

def pol2cart(rotdist, cwangle):
    x = rotdist * numpy.cos(cwangle)
    y = rotdist * numpy.sin(cwangle)
    return round(x), round(y)

print(pol2cart(1, 180))

prints: (-1.0, -1.0) while the expected output is (1.0, 0.0)

The above answer however would also give a consistent offset at each iteration. This would result in only three different angles (horizontal, vertical, and 45 degrees). This is not what's required, as I'd end up with another angle then I put into the function.

EDIT: Example of input

Below image is an example of the image data. The red dot indicates a possible starting position. This dot has a direction, which is not indicated. If the red dot is pointed straight down, then its direction is 180 degrees.

A nested dictionary contains each pixels's coordinates (row, column) and colour values: {1: {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0, 7: 255, 8: 255,...

enter image description here

Tim Stack
  • 3,209
  • 3
  • 18
  • 39
  • What's your sample input look like? A straight line in an image is digitized – Mad Physicist Feb 23 '20 at 16:50
  • I have an input 1-bit bitmap picture. A nested dictionary contains keys of rows, columns and values of the corresponding pixel. So e.g.: [3][4] = 255 – Tim Stack Feb 23 '20 at 16:53
  • Please show an example – Mad Physicist Feb 23 '20 at 16:55
  • 1
    If you know the starting position, and the angle, you can easily work out the other end! No line in the image can be longer than the diagonal, so make a line as long as the diagonal +10 starting from the start position and the other end will be outside your image. Then you can use Bresenham https://en.wikipedia.org/wiki/Bresenham%27s_line_algorithm to move towards the other end. – Mark Setchell Feb 23 '20 at 20:38
  • Show some examples. Line width, termination conditions, different angles. There are many ways to do this, so your problem is still not well defined. – Mad Physicist Feb 23 '20 at 21:39
  • @MarkSetchell brilliant, that algorithm seems just what I need! I'll work with that. If you want to make an answer out of that comment, I'll gladly accept it. – Tim Stack Feb 23 '20 at 22:02

2 Answers2

1

I think you can use Bresenham's "Line Algorithm" described here on Wikipedia.

I know you said you only have the start point and no end point, but you know the angle (direction) of travel, and you know that the longest straight line in a rectangle is the diagonal, so if you imagine a line longer than the diagonal, starting at your start point and heading the right direction, you can generate and end point beyond the edges of your rectangle and use that for the other end in the Bresenham algorithm.

Mark Setchell
  • 191,897
  • 31
  • 273
  • 432
-1

The first proposed answer can be fixed by checking first whether your line is more horizontal or more vertical, and using that dimension as the iteration dimension (x in your example).

Regarding the second proposed answer: You can of course calculate an arbitrary far-away end point and apply those algorithms for a line with known start and end point you mentioned. You could then iterate through the points returned by that to check for a black pixel, and even restart the algorithm if none was found until you hit your arbitrary end point.

nnnmmm
  • 7,964
  • 4
  • 22
  • 41