I seek some code that will fracture a closed polygon into rectangles
The polygons contain no slanted lines.
Here's a sample of the concept I need to do:
THe one on the left is the original.  The one on the right with the xx's sho
w
possible locations to fracture the polygon. Not necessarily on the x axis.
________              ________
|      |              |      |
|      |              |      |
|  ____|              |xx____|
|  |                  |  |
|  |                  |  |
__________|  |        __________|xx|
|            |        |            |
|      ______|        |xxxxxx______|
|      |              |      |
|______|              |______|

I'm rattling here.
I think that I extend a line unitXunit then check each point to be the cross
product -1,0,1 of all other lines, then this would tell me where points
intersected with other lines.  I believe this would I would have to keep the
point being checked within the bounding box.
Assume the poly is always in a clockwise direction.

I have kbool compiled and working.
Could I take 3 line segments, make a rect out of these, then get the common
area of the rect and the original fig?  No It would be hard to tell when to
stop and when there was overlapping rects.

I'm open to suggestions, algorithms, plagerism ...


___  _ ____       ___       __  __
/ _ )(_) / /_ __  / _ \___ _/ /_/ /____  ___
/ _  / / / / // / / ___/ _ `/ __/ __/ _ \/ _ \
/____/_/_/_/\_, / /_/   \_,_/\__/\__/\___/_//_/
/___/
Texas Instruments ASIC Circuit Design Methodology Group
Dallas, Texas, 214-480-4455,  b-patton@ti.com

[ Post a follow-up to this message ]

In <Pine.LNX.4.61.0505180907520.8339@holster07.dal.design.ti.com> Billy Patt
on <bpatton@ti.com> writes:

> I seek some code that will fracture a closed polygon into rectangles
> The polygons contain no slanted lines.
> Here's a sample of the concept I need to do:
> THe one on the left is the original.  The one on the right with the xx's s
how
> possible locations to fracture the polygon. Not necessarily on the x axis.
>            ________              ________
>            |      |              |      |
>            |      |              |      |
>            |  ____|              |xx____|
>            |  |                  |  |
>            |  |                  |  |
> __________|  |        __________|xx|
> |            |        |            |
> |      ______|        |xxxxxx______|
> |      |              |      |
> |______|              |______|

> I'm open to suggestions, algorithms, plagerism ...


It appears that there is always at least one rectangle that has three
complete sides and a partial side (the upper-right and lower-left
rectangles in this example).

Find one of these rectangles and complete it by extending the partial
side until it meets at a corner.  Repeat.

I'm wondering, though, if there are some hidden requirements here.  Does
your solution need to find the fewest possible number of rectangles?

--
John Gordon            "It's certainly uncontaminated by cheese."
gordon@panix.com

[ Post a follow-up to this message ]

On Wed, 18 May 2005, John Gordon wrote:

> In <Pine.LNX.4.61.0505180907520.8339@holster07.dal.design.ti.com> Billy Pa
tton <bpatton@ti.com> writes:
> 
> 
>
>
> It appears that there is always at least one rectangle that has three
> complete sides and a partial side (the upper-right and lower-left
> rectangles in this example).
>
> Find one of these rectangles and complete it by extending the partial
> side until it meets at a corner.  Repeat.
>
> I'm wondering, though, if there are some hidden requirements here.  Does
> your solution need to find the fewest possible number of rectangles?

The fewest possible rectangle would be nice. wouldn't want a 10k point poly
turning into 10k rect's 

I'll look into the to corners method tomorrow.

>
> --
> John Gordon            "It's certainly uncontaminated by cheese."
> gordon@panix.com
>
>

___  _ ____       ___       __  __
/ _ )(_) / /_ __  / _ \___ _/ /_/ /____  ___
/ _  / / / / // / / ___/ _ `/ __/ __/ _ \/ _ \
/____/_/_/_/\_, / /_/   \_,_/\__/\__/\___/_//_/
/___/
Texas Instruments ASIC Circuit Design Methodology Group
Dallas, Texas, 214-480-4455,  b-patton@ti.com

[ Post a follow-up to this message ]

Billy Patton wrote:
> I seek some code that will fracture a closed polygon into rectangles
> The polygons contain no slanted lines.

This is off topic for c.u.p you should follow up to a forum about
algorithms or geometry not programming with standard UNIX APIs.

Having said that consider that any inscribed rectangle's center must be
inside the polygon.  One approach would be to inscribe a rectangle
anywhere two consecutive complete segments of the polygon are sides of
a rectangle whose center is inside the polygon.  The corner of such a
rectangle opposite the vertex between the two sides used identifies
where to split and extend opposite sides.  Create a reduced polygon
from that knowledge that doesn't include the rectangle just and repeat
until there's nothing left.  Note that an iteration could split the
polygon into more than one sub-polygons.

-- ced

> Here's a sample of the concept I need to do:
> THe one on the left is the original.  The one on the right with the xx's
> show possible locations to fracture the polygon. Not necessarily on the
> x axis.
>           ________              ________
>           |      |              |      |
>           |      |              |      |
>           |  ____|              |xx____|
>           |  |                  |  |
>           |  |                  |  |
> __________|  |        __________|xx|
> |            |        |            |
> |      ______|        |xxxxxx______|
> |      |              |      |
> |______|              |______|
>
> I'm rattling here.
> I think that I extend a line unitXunit then check each point to be the
> cross product -1,0,1 of all other lines, then this would tell me where
> points intersected with other lines.  I believe this would I would have
> to keep the point being checked within the bounding box.
> Assume the poly is always in a clockwise direction.
>
> I have kbool compiled and working.
> Could I take 3 line segments, make a rect out of these, then get the
> common area of the rect and the original fig?  No It would be hard to
> tell when to stop and when there was overlapping rects.
>
> I'm open to suggestions, algorithms, plagerism ...
>
>
>    ___  _ ____       ___       __  __
>   / _ )(_) / /_ __  / _ \___ _/ /_/ /____  ___
>  / _  / / / / // / / ___/ _ `/ __/ __/ _ \/ _ \
> /____/_/_/_/\_, / /_/   \_,_/\__/\__/\___/_//_/
>            /___/ Texas Instruments ASIC Circuit Design Methodology Group
> Dallas, Texas, 214-480-4455,  b-patton@ti.com


--
Chuck Dillon
Senior Software Engineer
NimbleGen Systems Inc.

[ Post a follow-up to this message ]

Billy Patton <bpatton@ti.com> writes:

> I seek some code that will fracture a closed polygon into rectangles
> The polygons contain no slanted lines.

As stated, the problem is trivial: Take the gcd of all the side
lengths, and split the polygon in small squares with sides this gcd.
Another trivial solution would be just to split horizontal lines of
the polygon (taking care of concave forms): even less computing.

Perhaps you want to minimize something. What?


--
__Pascal Bourguignon__                     http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush

[ Post a follow-up to this message ]

Billy Patton wrote:

> I seek some code that will fracture a closed polygon into rectangles

IIRC, Binary Space Partitioning ought to do the job. However, you will
get a better answer by asking your question on comp.graphics.algorithms.

--
mail1dotstofanetdotdk

[ Post a follow-up to this message ]