following a boustrophedon path in a given room with obstacles

edit

Hi all,

I have a mobile robot which is navigating around a room, I already have the map of the room. I am using the navigation_stack of ROS. I am using rotary encoders for odometry. I am fusing the data from Rotary encoders and IMU using robot_pose_ekf. I am using amcl for localization and move_base for planning. Now, I have to write a Complete coverage Path planning algorithm and I am following this paper and I would like to ask what is the best way to generate the Boustrophedon path (simple forward and backward motions) in a cell (can be rectangular, trapezium, etc.) with no obstacles? If someone can suggest how to implement it in ROS, that will be great.

Update:
In cases like shown here (taken from here):

To come up with divisions in the 2nd or 3rd cell (center top or center bottom), I dont know whether knowing all the corner points will be enough (I might be wrong) or should we have all the boundary points (If yes, I am not sure how exactly to find it). Does anyone have any idea how to generate boustrophedon path in a cell like this?

Please let me know if you need more information from me. Any help will be appreciated.

Thanks in advance.
Naman Kumar