🔒 Locked

Search Pattern Algorithm

Started by Ali_nz Aug 4, 2006 at 2:36 PM 0 replies 700+ views

Original Post

Aug 4, 2006 at 2:36 PM

Hi Folks, I am trying to write a program for a real world project, although the maths could easily be applied to gaming projects too. I am using openGL and VC++ Express. What I am trying to do is make a instrument for a pilot in a aeroplane to fly a search pattern, like what you would do for a missing people at sea. The search pattern i want to impliment initally is a creeping line search pattern which looks like so: (2)-----<----* | | *------>-----* | | *-----<-----(1) The search pattern is general defined by Map Grid coordinates of the two corners of a box (1) and (2). And a sweep width, which is not shown above, but is the vertical spacing in my diagram. Note that although my picture is aligned with the x/y axis the box could be offset to any angle. The problem is coming up with an algorithm definging the turning points (*) If anyone can help out here I would be really grateful. I have kinda hashed the maths of it on some paper, but wouldnt really know how to get it into code. Cheers -AL

Solias

Aug 4, 2006 at 4:21 PM

A is the start, B is the end.
w = abs(A.x - B.x)
h = abs(A.y - B.y)

sw = sweep width

Assuming you start flying parallel to the x axis, half a sweep width will be outside the box. So the total coverage along the y axis for n rows will be

c = n * sw - (sw / 2).
(c + (sw / 2)) / sw = n

n = ciel( (h + sw / 2) / sw )

Where n is the number of rows.

There are two turns per row except the first and last row which have 1 each so

t = (n - 1) * 2

where t is the number of turns.

The x coordinate of each turn will switch back and forth between A.x and B.x every two turns. The y coord will increase by sw every two turns.

t | x    y--|-------------1 | B.x, A.y + 02 | B.x, A.y + sw3 | A.x, A.y + sw4 | A.x, A.y + 2sw5 | B.x, A.y + 2sw. | ...  ...

for t = i
x = (i / 2) % 2 == 0 ? B.x : A.x
y = (i / 2) * sw + A.y

Assume integer division with truncation and that i starts at 1 (use i + 1 if you want to start at 0). This also assumes that A.y < B.y, you'll need to reverse a few things to handle the other case.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.