Shrinking a contour


#1

Hi All,

I am looking for a way to shrink/expand a contour…I know juce supports paths…What I would like to do is shrink or expand this path…By shrink and expand I dont mean “scaling”… which is simple to do using juce…I would like to bring the outlines of a closed path closer/away to/from each other…

Is there any way I can do this using juce?Also,is there a way to maintain the number and order of vertices in the resulting contour?

I am enclosing an image link…which depicts exactly what I am looking for…

Link…
http://docs.google.com/Doc?id=dr47z5r_0hscb8shd

Regards
Praveen


#2

oooh… that’s a lot harder than it sounds!

I think the way to do it would be to generate a stroke for the path, then subtract the stroke from the original path. Unfortunately the juce path doesn’t have a method to subtract two paths… (which is a very difficult geometric operation!)


#3

erosion and dilation of non-discrete paths is a bit of a nightmare. :frowning:

If you can treat the path as a collection of linears, it’s quite a bit easier as long as you only have to deal with simple polygons, even then though, you might need to implement a hull following method to catch cases where the dilation causes overlaps.

If you can solve your problem in discrete space, then clearly the solution is trivial(ish), but in floating point space, especially if your path contains non-linear segments, you might be better served just looking for a decent geometry library.


#4

actually, I wasn’t being entirely clear above[1]:

dilation is exactly equal to scaling, if your path is convex. It’s concavities that screw you up[2]. If you have a decent amount of a-priori knowledge about your path though, there is a solution of sorts to be mined from this.

If you can pre-segment your path into nice discrete sections that can be scaled normally (remember that a dilation or erosion essentially a scale with the object centered on the origin), you can then re-composite those parts into a whole path. The best possible place to be here is to have a shape that can be created through use of a collection of parametric functions. So rather than giving JUCE a complete path and having it render it, consider breaking your object into separate paths, and rendering them manually. Now you can simply apply appropriate scaling to the paths with an optimum center point for each. It should also be easier here to test for intersections between paths so that where dilations collapse concavities you can handle that scenario gracefully.

An alternative approach, which works for shapes like your S, but less so for others, is to define a skeleton for the shape, then simply scale it, and cast vectors along its path to apply a line thickness.

There are far better approaches to both of these methods, but most of them require a lot of auxiliary code to be written first. :frowning:

[1] stupid daylight savings…

[2] In my darker moments, I have contemplated the beauty of world with no concavities.


#5

Hi All,
After a bit of work I have found a way in which I can shrink or expand the contours…
All I do is first divide the path into a number of edges(lines) joined with each other…Then I move these edges towards/away from their normals with a magnitude of my choice…After this I find the intersection of the adjacent edges and these intersection points would actually give me my resulting path…Not sure if it is the best way to do it though…

Thanks and Regards
Praveen


#6

It depends on how robust your algorithm has to be - if you’ve got lines that cross over each other, then your idea won’t work… There’s also the problem of choosing which direction is “inwards”, and I’m sure there are many more edge-cases…


#7

Hi,

I can understand that this idea wouldnt work for self intersecting polygons but I generally deal with non-self intersecting polygons…Will have to try and make it more robust…

Regards
Praveen


#8

Assuming I’m following your approach properly, the easiest[1] way of getting the outer hull of a potentially self intersecting polygon is to:

1] convert the poly into a mesh. I.E. an unordered list of points which contain pointers to the points to which they are connected. Typically each point will have two connections. Points that lie on intersections will have more than two.

2] find the intersection points on the poly, and insert them into the mesh. Disconnect the lines in the mesh that were intersected, and connect them to the new intersection points. I.E. the line AB is intersected at P. Add P to the mesh, disconnect AB, and connect AP and PB.

3] choose a suitable extreme starting point. Essentially you just need a point that has to lie on the outer hull. Typically you can just find the points that lie on the smallest X, and then find the highest Y in that set (assuming your co-ordinate system is normal euclidean, for rasterized Y co-ordinates, you’ll want the lowest value of Y).

4] Walk through your mesh one point at a time. When you reach an intersection, take the path that forms the largest clockwise angle (without being 2 Pi of course :wink: ) from your current path. Repeat until you reach the start point.

This will always return the outer hull of the mesh. As such, if you dilate your ‘S’ to the extent that the concavities collapse, and the structure becomes self intersecting, this’ll provide a robust method for getting just the outer part of the polygon.

[1] not necessarily the fastest, but most of the cost is in the intersection detection stage. Fast intersection detection is a whole other story. :frowning: