Cocoa: A "random" line between two points?
In my Cocoa hobby project (on OSX) I have a view with specific points. Something like that:
NSPoint pt1 = NSMakePoint(20,100);
NSPoint pt2 = NSMakePoint(100,30);
I would like to create a curving line (which never crosses itself) between these two points. Of course, the points may differ. I am familiar with NSBezierPath
but I am not a graphics widget.
There are two options for this. Considering NSBezierPath *p ...
and setting[p moveToPoint:pt1]
- Use
[p lineToPoint:ptx]
where I create a winding line that is jagged and - Use
[p curveToPoint:ptx controlPoint1:cpt1 controlPoint2:cpt2]
with sparkling line.
The second case seems to be more difficult as reasonable control points have to be calculated.
Finally, I would like to be able to adjust the amount with which the mosque line. If I set the type variable int numOfIntermediatePoints
to 1, then there is a smooth curve between pt1
and pt2
. If I set it numberOfIntermediatePoints
to 10, there will be a lot more movement in the line. I don't want the last intermediate points to be very far from the last point (leaving a big change at the end of the line).
I've looked into using Perlin noise, but it looks like it would be difficult to trace the line to its end point. It sounds like it makes sense to calculate an array of elements NSPoint
(and possibly an array of breakpoints for the second case) and then loop through them to create a string.
What's the best approach to this?
Update
Following Tommy's advice, I brought me to a port of Raymond Hill's Javascript-Voronoi library in Obj-C. You can find it here: https://github.com/ccheaton/objcvoronoi
Another update
Another update - I was playing with Dijkstra's algorithm and thought it was too much for what I was trying to achieve. I ended up using a simplified variation that allows me to define guide nodes for a random string. In this image, the beginning of the line is in the middle on the left, the end of the line is in the middle on the right, and there are direction points at (xMax * 0.33, 0) and (xMax * 0.66, yMax).
Final update
To make it a little less jagged, I added an additional relaxation algorithm. The performance is not great right now, but it doesn't matter for the use I mean.
source to share
There are many approaches that spring to mind.
In terms of code, you can pull straight from the internet, you can demolish the random maze generator and maze solver, and then create a maze with entry and exit points as needed and make a decision.
With that in mind, you can try a recursive approach - start with a straight line from beginning to end, then for each straight line:
- Imagine that you are going to split a line in two by dividing it by a center point and moving it; So...
- follow the normal line
- figure out how far along the line you can move the imaginary cutoff point of the center before your lines overlap the pre-existing lines (the easiest way to do this, I think, would be a binary search, not an analytical one)
- If the two extremes are too close to each other, return
- otherwise choose a random position between the two extremes, split the string, and recurse
For other interesting ideas, you throw a load of random points between the start and end points, compute a Voronoi diagram, then go (i) from the start point to any point on its boundary; (ii) along the cell boundaries along the shortest path to the end point boundary (for example, using Dijkstra's algorithm); and then (iii) to the end point. Then you can go through each vertex-to-vertex link added in (ii) and find the shortest route with all currently selected links excluded from the potential set and repeat this several times to make the path more interesting.
From roughly the same school of thought, throwing a bunch of random obstacles between points and running an A * -type finder might bring something interesting.
source to share