I'm trying to create a Procedural Road system using L-system, but I have no idea that how can I detect is there intersection between two lines in L-system, I can use a for loop to check one line against the others but I think there must be a better way than this. Can someone give me some idea how can I solve this problem? thanks for help.
How can L-system detect intersections between two lines
Intersections are not a characteristic of L-systems that can generally be determined algorithmically. My first stab is to save the start and end grid coordinates for the road segments your L-system generates, and then check whether any other segment has been entered as having that grid point as one of its ends. In essence:
- Tweak your L-system to generate road segments as paired grid coordinates, for the start and end grid points. (It may need to generate other properties as well, for a road network that isn't perfectly rectilinear.
- Use both start and end grid points as indices into a multi-array (and array that holds multiple items at a given index; an array of arrays) and store whether this is the start or end coordinate for the road segment, as well as some identifier for the segment.
- With each segment generated, check whether any other items exist in the multi-array at either its start or end points. Any point where two road segments meet is a connection; it is an intersection if the tangent of the curves approaching the grid point is different for the two segments. (i.e., if the tangent is the same, then the road segment transitions in a straight line. We need an angle for there to be an intersection.)
Edit: kitman20022002's suggestions are excellent, and more general solutions.
As kitman20022002 suggests, the problem is finding all intersections between a bunch of line segments faster than the trivial quadratic-time algorithm. You might be able to take advantage of the L-system organization of your line segments by testing intersections hierarchically, between the bounding boxes of L-system pieces, in order to exclude large parts of the search space and apply general algorithms to relatively small subsets of the roads.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
