Create a search-route in a given area

[opus]

Hi,
I've posted the linked threat in the VB.Net Forum alre<ady, but didn't get anything in there.

I'm trying to auto-generate a seach-route in a given area.
I have an area (for start-up the area will allways be konvex) made up of an array of points (.latitude and .longitude).
In it a route (a sequence of points) has to be created in order that, if the route is followed, the complete area will be covered, the maximum distance between paralel route-legs will also be given.
Does anybody have a routine for something like that?

http://www.vbforums.com/showthread.php?t=497064

[Milk]

You have an area, with obstacles, and you want to generate a route that will encompass the entire area. How does your route cover the area? How far can one see from the route, one pixel?

[opus]

The area is given by its corners, no obstacles in the area.
The maximum distance between parallel search-legs is given.
Consider it like mowing a lawn.

[Milk]

I assume konvex is the same as convex, every internal angle of the given area is less than 180°. I don't have an algorithm but I fancy a go at one. Do you have any criteria for measuring the efficiency of a route, i.e. shortest, least turns, longest runs etc.

[opus]

What could there be? The only criteria is that the whole area has be to be covered (that is any point of the area has to have bee nin the radius R of the present position of the object that is moving alone that route)

[edit] also, I need to calculate the route, as in I need to calculate the points that make the route.
[/edit]

[opus]

my present approach is like that (pseudo-code)
1. Since the turnpoints will be separated from the boundary by half the distance between the parallel search legs, I reduce the area accordingly.
2. For easy calculation of parallel search legs, I turn and move this area in order that the first point is at (0,0) at the direction to point 1 is 0°.
3. I create parallel legs(vertical) from x=0 until the maximum or minimum x (depending on direction of area). The length of those legs is initially from the minimum y-value of all points to the maximum y value of all points.
4. Find the intersection of all parallel legs with the boundaries to set the correct start and end points of those legs.
5. Turn and move all calculated turnpoints back (using values stored in Step 2).

Presently I'm struggeling at steps 3 to 4, number 5 is done already.

Does anybody have a better approach?

[Milk]

I tried this last night... I started working up a spiral around the edge code and then moved on to zig-zag code as it seemed easier, neither are fully working. I will have another look tomorrow.

[jemidiah]

If I'm reading this right...

To do #3 and #4:
1. Iterate through all valid x's by going from x=0 to x=x_end using a step size of D, the distance between parallel legs.
2. For each valid x_i, look up the appropriate points of intersection in your points array--those that have x-values equal to the current x coordinate.
3. Since it's a polygon and you've taken care of the edge cases with your reduction step, each leg should have two points of intersection. Call the two y coordinates y_min and y_max.

If you've done reduction the way I think you have (I dunno for sure), these should be the start and end points of this leg in the y-direction. So, this leg goes from the point (x_i, y_min) to the point (x_i, y_max). Now you have a list of your legs. Connect them up however you wish--perhaps just add lines between the endpoints of each adjacent leg, alternating which end point you use at each leg (which will work for a convex polygon).



This method presumes two things: 1. you can figure out all boundary cases (what happens if the width of the polygon is a multiple of D? etc.), and 2. you have a lookup-table like I described, and for each x-direction pixel you have a corresponding boundary pixel in the y direction. That is, the polygon is "continuous" without breaks on the screen.

If these are fulfilled, it should work fine.




Note: I think the "best" way to do this (but not the simplest) would be to just go around the polygon by "holding the right wall" all the time. This method of search is used in some mazes. In this case, it would allow you to start by "mowing" over the edges of the polygon, which would produce a smaller polygon. You can repeat the pattern you "mowed" on a slightly smaller scale inside the legs you've already made as many times as needed. Technically, this could be done fairly elegantly using recursion--or, you could optimize it more with some loops.

Good luck, I hope I understood it all right!

[opus]

Hi, jemidiah
thanks for the reply, I'm answering a bit late because I stayed in hospital for a week.

I used the time in there to do some thinking on the problem.
Basicly I've done steps #3 and #4, however I used a function to calculate each intersection instead of a lookup-table.
It is all very easy if I take a polygon with 4 corners and angles of 90°. The size of the polygon will allways be any multiple of D, that doesn'Tdo any harm.
The problem comes with special cases, for example the corners are not 90°, in this case the parallels will cross not only the top and botton edge-line, the bounding line with the maximum x-value will be crosses by some paralles also (look at the picture from milk). The get the correct coding for those situations is getting tricky.
The other problem arises if you have more than 4 corners. Consider the end of a parallel, you have to move the X-distance of D to the next parallel, if the polygon has an edge somewhere along that line, this leg has to be divided in two parts., tricky in coding also.


I'm still on it.

thanks!

[Milk]

The first version I worked on used something like this to work out where non perpendicular lines intersected, but this became awkward accounting for the rare vertical line scenarios and inaccurate for the near vertical line scenarios (Y intercept can become very very large leading to floating point errors). The version I have only part worked up was using pure Trigonometry and Pythagoras, which I think can be done and will be a lot more accurate all in the long run. I've not worked out all the formulas yet, I'm not really working on it all atm to be honest. I'm still undecided as to whether zigzag or spiral-round is the best solution, they both involve various different, not immediately apparent problems.

[opus]

In the current solution I'm using, I have a custom function that does calculate the intersection (for sure using the same formula). It will give a solution for any angle (a position with values outside the allowed range equals no intersection!).

I can't see the real difference in your "pure Trig. and Pythagoras" approach, the problem as above (intersecting lines) has to be calculated somewhere as well!

As you are still undecided wether to use "zigzagging" (Called "Parallel Track Search" or PTS) or spiral around (called "Expanding Square Search" or ESS), here are some comments from my side, since I've been using and teaching them in real world (to be honest used the Expanding Square in real world only once!).
The ESS is used when you have a position with no known error data, that means you can not access up to which distance from the given point you have to search. The area would be covered evenly starting from the given position. The area that will be searched will expand evenly around the position started from, normally forming a square.
The PTS will take an area and cover it evenly using parallel tracks throughout the area. This one is most commonly used by the search units in the maritime search&rescue environment.