filling up a ploygon with a rope

filling up a ploygon with a rope

Post by Norbert Harre » Sat, 17 Feb 2001 01:42:24



* I have a polygon with not intersecting edges.
* I also have a robe of any length I want. The robe has also a thickness.
* I attach the robe somewhere at one edge of the polygon (my starting
point).
* Now I want to lay out the robe inside the polygon, so it covers the whole
(or at least a maximum area) of the polygon. The robe is not allowed to
cross itself though.

I am looking for an algorithm that would find me a rope layout so it would
fill out as much as possible of the area of the polygon.

Such an algorithm could come in handy for calculating the layout of
underfloor heatings or
sprinkler systems and so on. I am sure some people already did this...

Thanks,
Norbert.

 
 
 

filling up a ploygon with a rope

Post by Fernando Cacciol » Sat, 17 Feb 2001 02:48:09




Quote:> * I have a polygon with not intersecting edges.
> * I also have a robe of any length I want. The robe has also a thickness.
> * I attach the robe somewhere at one edge of the polygon (my starting
> point).
> * Now I want to lay out the robe inside the polygon, so it covers the
whole
> (or at least a maximum area) of the polygon. The robe is not allowed to
> cross itself though.

> I am looking for an algorithm that would find me a rope layout so it would
> fill out as much as possible of the area of the polygon.

> Such an algorithm could come in handy for calculating the layout of
> underfloor heatings or
> sprinkler systems and so on. I am sure some people already did this...

> Thanks,
> Norbert.

Search for 'offset polygon', which in turn can be obtained from a 'voronoi
diagram of a polygon', or a 'medial axis' or a 'straight skeleton'.

You can start out at:

http://www.ics.uci.edu/~eppstein/geom.html

--
Fernando Cacciola
Sierra s.r.l.

www.gosierra.com

 
 
 

filling up a ploygon with a rope

Post by Jukka Liimatt » Sat, 17 Feb 2001 03:04:10


Quote:> * Now I want to lay out the robe inside the polygon, so it covers the
whole
> (or at least a maximum area) of the polygon. The robe is not allowed to
> cross itself though.

At first glance it looks like you need the same amount of *rope* no matter
how you lay it out. I'd just start from some corner/vertex, start rolling
the *rope* inwards in a "spiral" pattern. This assumes the polygon is
convex, if not, then it requires some additional thinking.. ;-)

-j

 
 
 

filling up a ploygon with a rope

Post by Norbert Harre » Sat, 17 Feb 2001 04:31:29


Yes, that's the problem. It can be a non-convex polygon too.

Besides, I apologize for my poor spelling. Of course I meant rope when I
wrote robe (sorry).

Thanks,
Norbert.

On Thu, 15 Feb 2001 20:04:10 +0200, "Jukka Liimatta"


>At first glance it looks like you need the same amount of *rope* no matter
>how you lay it out. I'd just start from some corner/vertex, start rolling
>the *rope* inwards in a "spiral" pattern. This assumes the polygon is
>convex, if not, then it requires some additional thinking.. ;-)

 
 
 

filling up a ploygon with a rope

Post by Jukka Liimatt » Sat, 17 Feb 2001 05:04:31


Quote:> Yes, that's the problem. It can be a non-convex polygon too.

Outch, then it's not that trivial anymore. Maybe you want to check the URL
the other reply gave. I did some quick, 30-second-thinking though, here's
some thoughts:

I am still assuming contraint that the area is still continuous-- no
self-intersecting edges. You would split the area into convex areas ( for
example by splitting the areas with edges of the polygon ). You could "fill"
each area with zig-zag pattern, which allows ( should allow ) to enter+leave
the convex areas at leisure.

What kind of algorithm you would use, is beyond me for such short thinking.
I think you wanted advice of someone who actually tackled the problem
before, and has the obvious answers at hand, atleast that's the impression I
got from your original post so I won't try to make fool of myself in greater
length.

Hope the URL's help, or someone with in-hands experience steps in and helps
you. ;-)

Quote:> Besides, I apologize for my poor spelling. Of course I meant rope when I
> wrote robe (sorry).

No need to apologize, I just thought it was kind to point out the spelling
error. I know you won't be using rope anyhow, it was just example to
visualize the problem... atleast that's how I understood it to be.

Cheers!

 
 
 

filling up a ploygon with a rope

Post by Jukka Liimatt » Sat, 17 Feb 2001 05:06:45


Additional 5-second thought... if it's a sprinker system, cannot the
pipes/ropes BRANCH? This would allow to implement the system with less pipe
and so on. Just a thought, since don't know what it's precisely for. ;-)

-j

 
 
 

filling up a ploygon with a rope

Post by Norbert Harre » Sat, 17 Feb 2001 05:38:36


Thank you, Jukka and Fernando, for the help.

Actually, branching of the ropes or pipes is not allowed. And yes, the
area is continuous.

As a matter of fact, I would like to use such an algorithm for generating
layouts of underfloor heaters. That's a long pipe in the floor of a room.
It enters the room somewhere at a wall and has to be laid out in a way
that it covers the whole floor without intersecting itself.

Thanks,
Norbert.

On Thu, 15 Feb 2001 22:06:45 +0200, "Jukka Liimatta"


>Additional 5-second thought... if it's a sprinker system, cannot the
>pipes/ropes BRANCH? This would allow to implement the system with less pipe
>and so on. Just a thought, since don't know what it's precisely for. ;-)

>-j

 
 
 

filling up a ploygon with a rope

Post by Jon Cohe » Sat, 17 Feb 2001 06:32:19




Quote:>Thank you, Jukka and Fernando, for the help.

>Actually, branching of the ropes or pipes is not allowed. And yes, the
>area is continuous.

>As a matter of fact, I would like to use such an algorithm for generating
>layouts of underfloor heaters. That's a long pipe in the floor of a room.
>It enters the room somewhere at a wall and has to be laid out in a way
>that it covers the whole floor without intersecting itself.

It definitely sounds like you should be using a scan-conversion type of
algorithm (parallel lines going back and forth), but you may need to
occasionally follow along the border of the polygon to get to a
different section. I assume the pipe has to exit the room as well as
enter.

Jon

 
 
 

filling up a ploygon with a rope

Post by Fernando Cacciol » Sat, 17 Feb 2001 22:25:50


The URL's I gave you should get you in the right track.
I strongly recommend that you follow it. Your's is a standard offseting
problem.

As soon as you understood the general procedure (or if you get lost in the
references) post a new message and we'll see.
I need you to get familiar -at least- with voronoi-diagram-like structures
and their application to offseting before we can go on further.

Alternatively, you can use the following procedure which is very time-space
consuming but really easier to implement:

1.Draw your polygon as a black-filled area in a white background binary
image.
2.Extract the boundary pixels from that image. The extraction procedure will
return a connected sequence of points.
This secuence is a 'n-level offset polygon'.
3.Erode the boundary pixels (paint them white).
4.Go on step 2 until no boundary pixels are left.

From the above procedure you will obtain a set of 'rings', each ring is a
cycle of connected pixels. You can join selected pixels in two adjacent
rings so as to connect the rings inward, thus transforming the ring set into
a spiral-like singly connected path. Then you can construct your pipes from
that path.

Look in www.MagicSoftware.com for the image procesing tools.

--
Fernando Cacciola
Sierra s.r.l.

www.gosierra.com