# Fill a surface based on waypoints

Hi all,

I’m currently developping an URcap for a company, and fortunately, it works great so far.

But now, I’m facing a problem. I would like to know if anyone tried to generate a path based on the waypoint that the user would define.

For example, the user define 5 waypoints with my URcap. When he clicks on a button “Fill”, I would like to generate a robot path that would fill the area defined by the waypoints.

How can I achieve that ? Looping with offset ?

Thank you.

Br;

Hi c.jardin…

Assuming you by “fill” mean a path that “covers” an area?

I would do it this way

1. extract the poses defined by the waypoints
2. project them on to the 2D plane I want to move in.
3. calculate the convex hull of these five poses (you can easily google your way to some nice algorithms)
4. fill the convex hull with points that are spaced appropriately (properly based on the tool size and the speed I need to use)
5. create a nice path through them (zig zag, spiral etc., This might also influence how you choose to place your point in step 4)
6. project them back to the base coordinate system if needed
7. test until I find a nice way of handling the borders

Best Regards Casper.

Hey,

Alright, I can see how to calculate the convex hull in Java, but can’t find a solution to fill it with points…

Br;

if you can create a function that tells you if you are inside or outside the hull you should be able to just brute force your way through it…

by moving a set amount in your plane (in a pattern of your choice) and ask if its out side the hull and only save the point if its inside.

Many thanks, I see how I can do this now

Br;

No Problem
PS: if you want to take it to the next level you should consider using a Concave Hull instead but the complexity will also sky rocket, for more then 4 waypoints.

BR;