Hi, I'm trying to find some algorithm to find the inner contour of a contour. What I want to do is this: There's a certain convex or concave polygon, and I want to draw it with a border with a certain thickness. So the outside of the border is the polygon itself, the inside of the border is the inner contour that I'm trying to find. Simply taking the points of the polygon and moving them inwards with the thickness as distance is not enough, because for example if the polygon is thinner than the thickness at some locations, then there's no inner contour at all there. Could someone point me to a description of such an algorithm? I've been trying to search for things like "polygon inner contour", "hollow polygon" and so on with Google but didn't find much...

Can you use something of this thread? It calculates on both sides, but maybe.

Quote:Original post by szecs
Can you use something of this thread? It calculates on both sides, but maybe.

Hmm, it seems similar, but also different, what the OP there asks I think is to draw a thick line around some points that make up a polyline. In my case it's a polygon instead of a polyline. Also, I don't need a triangularized version of the polygon, just the points.

Anyway there's a lot left for me to read in that thread, so I might still encounter the useful bits!

EDIT: I also found a definition of what I want (but not an algorithm description) on a website about CAD:

offset
Creates a polygon that is parallel every where to the input polygons, separated by a constant distance.

The useful stuff are the drawings, and my idea near the end of the thread (I'm so humble :P). The fact, that you only need one side, and that your polygon probably won't intersect itself makes it even simpler. And you have to deal with very small polygons as special cases, but as I recall, my algorithm can handle "disappearing" line segments too.
The essence of it that you calculate the offset segments, you intersect every segment with each other + some other simple conditions, that you "walk" through all the valid segments.
I guess you don't need it to be real time (I mean not recalculated 30 times/second)

It all seems less simple than it would appear at first sight, but I think I'm on to something:

-first calculate the offset polygon with all the problems like in your drawings
-then find the self intersections, and when there are self intersections, then there are positive and negative areas in the polygon (negative areas are those where the clockwise direction of the points around it are inverted)
-then remove the negative areas and keep the positive areas, so the result can be more than one polygon...

But that too sounds simpler than it probably is...

EDIT: about your sig: why "and probably last" demo? That tank demo looks friggin' cool!!

Thanks for that!
"Probably", because I don't think I will start another project that "big" again (I'm not a programmer, just hobbyist).

Some quotes:

////////////////////////////////////

Find all the intersection points (intersect all pre-calculated outline segments with all the others)

1.Find a valid point (valid point = if its distance of all the generator segments are greater or equal to the given distance ('width'))
2.Find the next (neighbour) valid point
3.If you are done with one outline, go for the next one.

for the distance form a segment:

in that area

///////////////////////


So intersect all parallel lines with all parallel lines. The intersection points that count on a segment are between its start and end points.

start from the first red segment and find the first valid (dark green) point, than go to the next segment (which shares that valid point), and go in the same direction, until the next valid point and so on. Do it on the other side of the black line too.

I don't know how to manage the closed areas (green circle with the green '?').
Maybe going along the first line (in the case the drawing shows) on the false direction (blue line), until finding valid points (the first has to be an intersection point, not an endpoint of the parallel segment).
If you reach the first point again, you can close the loop.

The biggest problem is to decide wich point is valid or not. A valid point is the closest intersection point to the current point on the red path (or endpoint) in the proper direction: arrow on the image.
If the starting point of the whole thing is valid, you can find all the edges this way (red lines).


//////////////////////


Self intersection is not an issue, if you think it over, at least for the outlines.
The inner lines, well if you find a valid line segment (that's not on the outlines), you can repeat the algorithm (until you find the segment you started with.)

valid segment: upper, invalid: lower


i, j, k, f, g, are the indexes of the parallel segments. (if you calculate in sequence)
If an intersection point from a line, that has a greater index, has greater 't' parameter value, than an intersection point from a line, that has a lesser index, that's a valid segment. (There can be more of it on a line).

A segment is invalid (the whole segment), if its direction is opposite to the generator line (t = 1 comes first, than t=0);
A segment is invalid if it seems valid (it fulfills the above conditions), BUT: one of its endpoints is nearer to the generator the line, than the 'distance' (loop through all the generator segments)

So:
1. find a valid segment, that's not included in the already found outlines
if not found: we're done!
if found, continue
2. Go through the path as I described in my previous post ('t' parameter increases)
3. Go through the opposite direction the same way('t' parameter decreases)
4. go to step 1

It works with self intersecting generator lines too, in any cases.
Because it only cares of going through the outline, and if you consider, if we're on a valid segment, we always can find the next valid (or reach the end, or the starting segment (inner outline loop))

Because you intersect all precalculated outline segment with all the others, so this method doesn't care of the topology.

All you have to do is index sequentially (that should be easy)

/////////////////

Sorry, I don't remember the final conclusion, but it was very simple, I hope that helps.

Take a look at the last drawing in the thread posted by Zipster.

Make those segments, that start to intersect every of them with every other.

You will have a bunch of intersection points. (Since you index the segments in sequence, you can index the intersection points to be in sequence too -> I think this one is not important).

Find a valid point from all the intersection points: valid, if it's distance is greater or equal to all the original segments, measured only in the trapezoidal areas (orange area, that you can see in the other thread).

If you have the first valid point, it's sure you can find the next, start going in the "growing" direction (I mean 't' parameter (p=p0+dir*t) of the line equation is growing). You can start along one or two segments, (since it's likely to be an intersection point). only one way will be valid: where the next valid point lies:
validity of these next points are the same as the first.

go through all lines until you reach the first again.

This should handle all cases by itself, but one:
When the polygon is so small, that there can't be inside polygon at all.
But maybe that means you can't find any valid points to start with, so maybe that's fine too.

Return with the results please!

Quote:Original post by szecs
Return with the results please!

I'll post when I'm done. That is not yet!

So far I already got something that can remove self-intersections by returning a list of contours that each are a closed non-self intersecting contour and together form the original contour with self-intersections.