help with random lines in program

[wehttam2007]

i am simply trying to make a program with random lines which do not cross eachother. i am completely lost in how to do this though. i know that you can make multiple random lines using a for next loop but i dont know if you can still do that without any of them crossing eachother. please help!

thanks

 

[TheBigBasicQ]

If the lines must not cross each other( the proper word here would be intersect ) then they must be parallel. Unless you are talking about LINE SEGMENTS.

 

[wehttam2007]

thanks thebigbasicQ

i am trying to make random line segments which do not intersect*

 

[TheBigBasicQ]

That would be difficult. You would require some complicated math for it. Unfortunately I am not too good at Math. Sorry

 

[Cykadelyxx]

I just slapped this together in ten minutes in VB6 with some line functions I had already written.

Probably the most effecient approach would be to maintain an array of end points and each time you create a new random line segment, loop through each set and check if they intersect using Cramer's Rule or another intersection test. This would use memory and the performance would be proportional to how many line segments you wanted to have on the screen.

I just used a function called GetNextPoint which allows you to create a new line by assigning line properties in the variable LineInterpolation of type LineInterpolation. After you have initialized it, each subsequent call to GetNextPoint returns the next point in the line. You start off by setting LineInterpolation.Currentpoint to 0. Then I checked each point on the line before calling it valid, because if you were to simply draw your line points until your line intersected another, it would probably look a little messy because nearly every line you create would most often be able to be drawn at least a few points. The lines would eventually turn into dots.

This is VB6 but it shouldn't be to hard to convert to QB the language is almost identical for general stuff. If you want to try it out in VB paste this into a form with a Command Button.


Option Explicit

Private Type POINTAPI
X As Long
Y As Long
End Type

Private Type LineInterpolation
Distance As Integer
CurrentPoint As Integer
Origin As POINTAPI
Angle As Double
End Type

Const PI = 3.14159
Dim LineInterpolation As LineInterpolation


Private Function GetNextPoint() As POINTAPI

Dim X1%, X2%, Y1%, Y2%
With LineInterpolation
X1 = 0
Y1 = -.CurrentPoint
X2 = Cos(.Angle) * X1 - Sin(.Angle) * Y1
Y2 = Sin(.Angle) * X1 + Cos(.Angle) * Y1
GetNextPoint.X = X2 + .Origin.X
GetNextPoint.Y = Y2 + .Origin.Y
.CurrentPoint = .CurrentPoint + 1
End With

End Function


Private Sub Command1_Click()
Form1.ScaleMode = vbPixels
Form1.BackColor = 0
Randomize Timer

Dim I&

For I = 1 To 10000
CreateNewLineSegment
Next

End Sub

Private Sub CreateNewLineSegment()
Dim NoIntersect As Boolean, I&
Dim thisPoint As POINTAPI

Do Until NoIntersect

LineInterpolation.Angle = (Int(Rnd * 360) * PI) / 180
LineInterpolation.Distance = 50 'Int(Rnd * 500) ' tweak this for different results
LineInterpolation.CurrentPoint = 0
LineInterpolation.Origin.X = Int(Rnd * 800)
LineInterpolation.Origin.Y = Int(Rnd * 600)

NoIntersect = True
'check every point on this line to see if it intersects another
For I& = 1 To LineInterpolation.Distance

thisPoint = GetNextPoint()
If Form1.Point(thisPoint.X, thisPoint.Y) > 0 Then NoIntersect = False: Exit For

Next

Loop

'this line doesn't intersect with any others so draw it
LineInterpolation.CurrentPoint = 0
Dim lCol&

lCol = Int(Rnd * (2 ^ 24))

For I& = 1 To LineInterpolation.Distance

thisPoint = GetNextPoint()
If Form1.Point(thisPoint.X, thisPoint.Y) > 0 Then Exit Sub
Form1.PSet (thisPoint.X, thisPoint.Y), lCol

Next


End Sub

 

[shanley06]

make two random coordinates and then before you draw the line between the two coordinates use the POINT command to check the color of the pixel at those two points and if the pixel color is not equal to 0 then choose two new random coordinates

 

[Cykadelyxx]

shanley06 that will not work. the algorithm cannot know if there is a line passing between the two points that does not touch the endpoints. it only successfully tests for overlapping segments on a single horizontal or vertical line, one or the other and not both.

 

[shanley06]

You could make your own line sub that draws the line from point a to point b and before you draw each pixel you could test to see what color the pixel is and if it is not a certain color than you exit the sub

 

[CubeE101]

Are the lines Chained (one end is the next start point) or are they completely random?

Have Fun, Be Young... Code BASIC
-Josh Stribling

http://cubee.topcities.com

 

[qbasicking]

I would think that the easiest way to do what you want is to randomly pick a starting point, then randomly pick an angle (in radians) between 0 and 6.28, then draw the line pixil by pixil, checking using POINT before he pixil is drawn

 

[CubeE101]

Point Will NOT work...

if a line looks like this...

+-+-+-+-+
| | | |X|
+-+-+-+-+
| | |X| |
+-+-+-+-+
| |X| | |
+-+-+-+-+
|X| | | |
+-+-+-+-+

And You Draw A Line Like This...

+-+-+-+-+
|X| | | |
+-+-+-+-+
| |X| | |
+-+-+-+-+
| | |X| |
+-+-+-+-+
| | | |X|
+-+-+-+-+

Point Will Never see the other line...

+-+-+-+-+
|X| | |X|
+-+-+-+-+
| |X|X| |
+-+-+-+-+
| |X|X| |
+-+-+-+-+
|X| | |X|
+-+-+-+-+

You need to use an intersection formula to find out Where the lines cross... and then use The X1,Y1,X2,Y2 as a bounding box and check if the calculated point is inside it...

Have Fun, Be Young... Code BASIC
-Josh Stribling

http://cubee.topcities.com

 

[mgh730]

Okay, here's some code I wrote...
I might mention a few potential problems.
First of all, this uses a mathematical formula, so the display may look different to you than to the formula, therefore creating visual problems, two of which I have noticed:
1. horizontal and vertical lines don't work. I made my code so that no horizontal or vertical lines are generated. But if you use your own lines that or horizontal or vertical, there may be problems, I'm not sure.
2. lines very close to another line may not intersect, but they may have one pixel right next to another, so the lines may touch. No lines will cross, though.

Another note for those who don't want to read through the source code - the code works by storing every drawn line into an array. Therefore, if you want it to work with existing lines, you will have to store the coordinates of those lines into the array variable. I would recommend writing a function that draws lines with the LINE command, and also stores the coordinates for the LINE command into a DIM SHARED array.
Anyone interested in the actual formula for line intersection can find it in the source code. The x intersection coordinate is top1/bottom1 and the y intersection coordinate is top2/bottom2.


'Intersecting Lines
'By Martin Hunt

'The screenmode variable can be changed between 12 and 13

'12 = high res, low color
'13 = low res, high color

'--------------

screenmode = 12

'--------------

'The screenmode variable sets the maxX, maxY, minX, minY variables
'along with a maxC variable, standing for the maximum color number

SCREEN screenmode

IF screenmode = 12 THEN

maxX = 640: maxY = 480
minX = 0: minY = 0
maxC = 16

END IF

IF screenmode = 13 THEN

maxX = 320: maxY = 200
minX = 0: minY = 0
maxC = 256

END IF

RANDOMIZE TIMER
CLS
TYPE linearray
x AS INTEGER
y AS INTEGER
x2 AS INTEGER
y2 AS INTEGER
END TYPE

maxlines = 1
DIM lines(maxlines) AS linearray
'this holds the coordinates of every line drawn

'create an initial line segment

DO

lines(1).x = INT(RND * (maxX - minX) + minX)
lines(1).x2 = INT(RND * (maxX - minX) + minX)

lines(1).y = INT(RND * (maxY - minY) + minY)
lines(1).y2 = INT(RND * (maxY - minY) + minY)

LOOP WHILE lines(1).x = lines(1).x2 OR lines(1).y = lines(1).y2

'the formula does not work for vertical or horizontal lines
'so loop until the line is not vertical or horizontal

'Draw the first line
LINE (lines(1).x, lines(1).y)-(lines(1).x2, lines(1).y2), INT(RND * maxC)

DO
DO
'Generate the coordinates of a random line
DO
x1 = INT(RND * (maxX - minX) + minX)
x2 = INT(RND * (maxX - minX) + minX)

y1 = INT(RND * (maxY - minY) + minY)
y2 = INT(RND * (maxY - minY) + minY)

LOOP WHILE x1 = x2 OR y1 = y2
'make sure the line is not vertical or horizontal

intersect = 0

i = 1

DO

'test random line against every
'other line generated so far

'copy a line from the array into x3, y3 and x4, y4
x3 = lines(i).x: x4 = lines(i).x2
y3 = lines(i).y: y4 = lines(i).y2

top1 = (x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)
bottom1 = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
top2 = (x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)

'cannot divide by 0, so check if bottom1 <> 0
IF bottom1 <> 0 THEN

i1 = top1 / bottom1
j1 = top2 / bottom1
'x and y coordinates of intersection

xMax = x3: xMin = x4: IF x4 > x3 THEN xMax = x4: xMin = x3
yMax = y3: yMin = y4: IF y4 > y3 THEN yMax = y4: yMin = y3
xMax2 = x1: xMin2 = x2: IF x2 > x1 THEN xMax2 = x2: xMin2 = x1
yMax2 = y1: yMin2 = y2: IF y2 > y1 THEN yMax2 = y2: yMin2 = y1
'find max and min of the two line segments

IF i1 >= xMax OR i1 <= xMin OR j1 >= yMax OR j1 <= yMin OR i1 >= xMax2 OR i1 <= xMin2 OR j1 >= yMax2 OR j1 <= yMin2 THEN bottom1 = 0
'determine if the intersection coordinates are
'on both line segments based on max and min
'of both line segments

'If the interesection coordinates are outside of the
'line segments, then the two lines do not intersect

END IF

IF bottom1 <> 0 THEN intersect = 1

i = i + 1
'increase i and loop to test the new line
'for intersection with another existing line

LOOP WHILE i <= maxlines AND intersect <> 1
'break the loop of testing if the line intersects
'or if there are no more lines to test it against

LOOP WHILE intersect = 1

'If one of the lines intersected
'then it loops again, generating a new random line

'If the new line does not intersect anywhere, draw it and store it:

LINE (x1, y1)-(x2, y2), INT(RND * maxC)

maxlines = maxlines + 1
REDIM PRESERVE lines(maxlines) AS linearray
'increase size of line array by one

lines(maxlines).x = x1
lines(maxlines).y = y1
lines(maxlines).x2 = x2
lines(maxlines).y2 = y2

'the mathematically correct values are stored for comparisons

LOOP WHILE INKEY$ <> CHR$(27)

'loop until escape is pressed

SYSTEM