```
Public Sub TestLine(g as Graphics)
Var p1 as new Point(120,134)
Var p2 as new Point(140, 130)
g.DrawLine(p1.X,p1.y,p2.x,p2.y)
End Sub
```

Is there a Xojo function or mathematical algorithm to get all points that form a line?

```
Public Sub TestLine(g as Graphics)
Var p1 as new Point(120,134)
Var p2 as new Point(140, 130)
g.DrawLine(p1.X,p1.y,p2.x,p2.y)
End Sub
```

Is there a Xojo function or mathematical algorithm to get all points that form a line?

Google Bresenhamās line algorithm.

If the maths is obscure It looks tricky to meā¦ :> )

, the next question would be āwhy do you need itā?

if the answer is *āto determine if a mouse down happens on the lineā,* then simpler math is to calculate the Y co-ordinate for the given X co-ordinate, and see if it is within an acceptable distance.

(eg **abs(expectedy - actualy) < somevalue** )

The formula for a line is **y=mx+c**

slope (m) is (134 - 130) / (140 - 120)

(remembering that in xojo, y gets bigger downwards)

=============

And a nasty slow brute force method to find āpoints on the lineā is to draw a black line on a white picture , with antialias turned off, then scan the picture for dark pixels.

Maybe you can step back one level and tell us why you need them. That will help us help you.

Got a grid of hexes.

Draw an imaginary line from the center of a Hex to the center of another hex, I need to know which hexes the line pass through.

As Iāve methods that return the hex reference of a point, if Iām able to check all points I will get all hexes the line cross over

If the imaginary segment crosses a side of a hexagon, then it enters this hexagon.

If two sides of a hexagon are crossed, then the hexagon is crossed.

So it is sufficient to have a function to know if the imaginary segment crosses another segment.

An there is the case of coincident lines to take into account.

Based on some code I found online, and using API1 syntax:

```
Dim X, Y ,dx,dy As double
dim p1 as new xojo.core.Point(120,134)
dim p2 as new xojo.core.Point(140, 130)
Dim Distance_X As Integer
Dim Distance_Y As Integer
Dim Range As Integer
Dim newPoint As xojo.core.Point
dim thePoints() as xojo.core.Point
Distance_X = Abs(P1.X - P2.X)
Distance_Y = Abs(P1.Y - P2.Y)
If Distance_X < Distance_Y Then
Range = Distance_Y
Else
Range = Distance_X
End If
dx = (P2.X - P1.X) / Range
dy = (P2.Y - P1.Y) / Range
X = P1.X
Y = P1.Y
newPoint = P1
For i as integer = 1 To Range
thePoints.Append newpoint
X = x + dx
Y = y + dy
newPoint = New xojo.core.Point(X, Y)
Next
msgbox format(thePoints.Ubound +1,"0") + " points created"
```

Thanks Jeff, I adapted your code and it works great.

1 Like

Yes, this is what I was going to suggest.

For each hexagon, keep track of the line segments that form its outside edge. If your center-to-center line intersects any outside line of a hexagon, the line can be considered to intersect the hexagon itself. Line intersection algorithms are algebraic and donāt rely on the precision of the points you might calculate on the line.

Thereās a huge optimization to be made here: presuming your hexagons are packed together with all sides touching, like a honeycomb, then all of the sides of each hexagon share a line definition with the neighboring hexagon. You would cut down your calculations by a large factor by only testing each line segment once.

Thanks Eric,

The Jeff code is pretty efficient. If latter, I found I need optimization Iāll try that you suggested.

Thatās true Eric,

and another idea now that I see the specificity of the problem more concretely, would be to calculate the shortest distance *di* from each hexagon center to the segment *AB*.

If *ri* is the radius of the inscribed circle of the regular hexagons, an hexagon can only be traversed if *di < ri*. This eliminates again many polygons.

For the remaining hexagons, we now know the imaginary line traverses the inscribed circles, so we only need now to compare the slopes.

For a remaining hexagon, they are first considered as intersecting, but if one of the slope of an edge is the same as the slope of the imaginary line, then the hexagon is not traversed. All the 6 edges need to be tested.

It would use much less CPU.

Geometry nerd here: I thought of an even better optimization.

For each hexagon, create a line that goes from each point to the opposing point on the hexagon. Test each of these three lines for intersection with your center-to-center line.

I believe this reduces the number of comparisons even lower than my original suggestion.

As a precaution, with the Jeff code I would try with a line like the one that goes from #0503 to #0205.

Uh, this code will fail with a Divide by Zero error if the line is horizontal or vertical.

Uh, this code will fail with a Divide by Zero error if the line is horizontal or vertical.

Which is what testing is forā¦ (āBased on some code I found onlineā)

That said, there are some great ideas coming out here.

My example was just a leg-up, and easy to add checks for vertical/horizontal lines to.

Easiest āhackā ?

```
If Distance_X < Distance_Y Then
Range = Distance_Y + 0.0001
Else
Range = Distance_X + 0.0001
End If
```

Ewww, arbitrary fudge factor. Besides, that will fail if the original range is equal to the fudge factor.

2 Likes

The Jeff code do well if the line is horizontal or vertical.

In the bottom: why arenāt 0205 and 0405 highlighted?

Possibly the fudge factor?

1 Like

Forum for Xojo Programming Language and IDE. Copyright Ā© 2024 Xojo, Inc.