@szecs: Your approach is currently similar to our current solution. The issue with it, as you pointed is a posssible intersection of your black line.

We did some fallback paths for those kind of solution but it turned out that the client is twisting this damned polyline as long as he find some instability, e.g. intersections.

@xissburg: Im sure this isnt stable too. Or there is an additional AND-ing done to create a correct description of the area.
You could try to draw szecs first image and create a very thick outline and check whethere the inner edge does intersect or not

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)

But of course this process is real slow. So only update when the generator line changes.

The "slow" factor is key issue here. We have of course cached drawing so no recalculating if not necessry but at some point when redrawing occurs, it always occurs on all such lines at the same time (of course only within view bounding rect) but a typical test case which we somehow 'must' pass is a recalc of several hundred polylines with dense packed path coordinates resulting in some >10.000 vertices for which intersection and reiterion must be done.
Oh and of course this is not the only part of the draw, there textures and so on.


It's like wanting a great AI but only giving 1% of the computation power to it

Ok then the question, the others have asked already: Why is has to be perfect?
I tell you that you will never find a method that finds the outlines perfectly, in realtime.
It's like looking for the perpetuum mobile.

A path-finding problem is nothing compared to this problem.

Last idea:
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

The client wants it to be. No matter how you turn it. The previous tool was able to do that (even on a entirely different base) and the new tool must be able to do at least as good as the old one.

My current apporach is: Since I am able to detect two vertices which would produce a degenerated triangle, I do an intersection test with those and the original direction to determine a new intersection point. The generation algorithm would create two triangles on the same coordinate (since I made one coordinate from two this is of course replicated) To avoid double drawing on the same coords I need to drop one triangle which then interferes with my triangle drawing algorithm. *sigh*

Ok, so is your problem to find the outlines, or you already solved that, so I talk to the air?

If you have the outlines (I think my 2nd idea can be done in real time), I think there are many solutions to the triangulation you can find, since the problem is more general now, so you can google it with more chance. Maybe: "area holes triangulation",
or: "area holes triangulation library"

It's not solved even though I have an approach atm :)

It isn't like I am not able to solve it but I hoped to find a library that has already done it

But thanks for some helpful tipps :)

No, no access to the former tool but we know that it was based on TCL.

There are even more requirements like stipple pattern on the resulting line which is a daunting task by itself