polygon with intersecting line
Wallace Chigona
lies within P. The smaller polygon should have almost the same shape
(possible the number of points) as the bigger one (P).
What I am doing is as follows:
For each line of P get another line parallel. The new line should be to
the left of the old line and they should be M unit apart. Where M is
the desired margin.
My new polygon is then the intersection points of the consective (new)
lines.
PROBLEM:
For other values of M, some lines intersect.
I can go through the points to determine where the points cross each
other. However, I still don't have a solution on how to solve the
intersections.
Any ideas?
I don't even know where to look for a solution since I don't what this
problem is called.
Regards,
--
---{ Wallace Chigona chi...@isg.cs.uni-magdeburg.de }---
Institut fuer Simulation und Graphic, Uni. Magdeburg
Telephone: (M)++49 160 1236184 (W)++49 391 6718065
------{ http://isgwww.cs.uni-magdeburg.de/~chigona }------
Jack C. Ritter
but, assuming the poly is CONVEX, then dont consider lines, consider
*vertices* :
Calc. poly's center of gravity, cog. Then imagine spider-web-like lines
going from each vertex of poly to cog. For any desired fraction F < 1, where
inner poly 'size' will be F*outer-poly-size, just crawl (1-F) of the way
from each outer vertex to cog (along 'spider' radial lines), to arrive at
corrosponsing inner vertex. There's an infinite family of smaller polys (all
w/ same num of vertices), each member of which corrosponds to a value (>0)
of F. This effect can be seen in the (great) old video game "Tempest".
If poly is NOT convex, you've got multiple cogs, and you have to watch out
that inner poly doesnt cross over itself in the narrow parts - not trivial.
- Jack Ritter. ja...@you2peru.com
"Wallace Chigona" <chi...@mail.cs.uni-magdeburg.de> wrote in message
news:3B88163C...@mail.cs.uni-magdeburg.de...
Wallace Chigona
>
> I'm not sure what "other values of M" means (as opposed to "these" values?),
> but, assuming the poly is CONVEX, then dont consider lines, consider
> *vertices* :
>
M is the margin. The smaller polygon must always be contained within
the bigger polygon. M defines the distance between the corresponding
lines.
>
> If poly is NOT convex, you've got multiple cogs, and you have to watch out
> that inner poly doesnt cross over itself in the narrow parts - not trivial.
>
That's exactly my problem. The polygons are not convex, that's why the
inner polygon crosses itself. This is exactly where I need assistance.
Jack C. Ritter
walk around the poly and consider each sucessive adjacent pair as directed
edges. For each directed vector pair A & B, normalize each, call them nA &
nB, and compute sign of cross product nA X nB. Sign will be + for interior
angles <= 180 deg, and - for int. angles > 180 (or the other way around,
depending on the handedness of your coord. sys.). Call pair's shared vertex
V. Calc. point Q = V + (nB-nA). Calc. vector I = Q-V. Normalize I to nI. If
int. angle was found to be > 180, then nI -= 2*nI. nI now splits interior
angle. Walk along nI some fraction (1-F), starting at V, to get inner
vertex. Connect all the inner vertices. If any edges cross, you must try a
larger F (<1).
This is still vertex shrinking and not edge shrinking, and the new edges
wont all be the same lateral distance from their outer edges, but you can at
least back off F until you eliminate crossing, no matter how close the
original poly comes to touching itself.
If inner edges must be parellel to outers, and all the same lateral M from
outers, you'll need to seek spiritual guidance.
"Wallace Chigona" <chi...@mail.cs.uni-magdeburg.de> wrote in message
news:3B882358...@mail.cs.uni-magdeburg.de...
Hans-Bernhard Broeker
In comp.graphics.algorithms Wallace Chigona
<chi...@mail.cs.uni-magdeburg.de> wrote:
> What I am doing is as follows:
> For each line of P get another line parallel. The new line should be to
> the left of the old line and they should be M unit apart. Where M is
> the desired margin.
This task is usually referred to as the construction of an 'offset
polygon' --- a websearch with that as a keyword may prove helpful.
And it's known to be hard, so don't be surprised if your solution
doesn't work. The usual tool to solve it, IIRC, is the 'straight
skeleton'. That's essentially the set of all vertices positions of the
correct offset polygons for all possible values of M.
--
Hans-Bernhard Broeker (bro...@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.
Jack C. Ritter
I will stop pushing my less-that-perfect, vertex shrinking solution, and
simply ask:
Imagine a "bow-tie" polygon, where the "knot" is 2 opposite vertices that
"almost touch", say, they are M/3 apart. Vaddiya Gonna Doo?
the jack
"Hans-Bernhard Broeker" <bro...@physik.rwth-aachen.de> wrote in message
news:9mdb0t$phc$1...@nets3.rz.RWTH-Aachen.DE...