Re: looking for code

From: Chuck Dillon (spam_at_nimblegen.com)
Date: 05/19/05 

Date: Thu, 19 May 2005 08:34:21 -0500

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.

Relevant Pages

  • Re: How to draw with a PEN ?? Please help
    ... I would assume that the filling of shapes - rectangular or otherwise - is ... Given how your polygon matrix is defined, ... To try and simplify what I was talking about, if you fill a rectangle, the ... are you doing this entirely within GDI+? ...
    (microsoft.public.dotnet.framework.drawing)
  • looking for code
    ... I seek some code that will fracture a closed polygon into rectangles ... Could I take 3 line segments, make a rect out of these, then get the common ...
    (comp.unix.programmer)
  • Re: How to draw with a PEN ?? Please help
    ... Pamela - ... right sides of the rectangle. ... the bottom and right sides. ... I don't know whether that would offset all the additional polygon ...
    (microsoft.public.dotnet.framework.drawing)
  • Re: Is it possible to remove a slot when inheriting?
    ... You define an accessor method `points` that computes the ... How about shape and polygon and rectangle both inheriting from it? ... the representation of rectangle and the implementation of draw-on- ...
    (comp.lang.lisp)
  • Re: Moving GraphicsPath object with my mouse
    ... Find great Windows Forms articles in Windows Forms Tips and Tricks ... > rectangle, polygon). ... >> and moving. ...
    (microsoft.public.dotnet.framework.drawing)