All points on a given 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. :grin:

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.
image

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.

be3c40aa7e1f1f57e73c8d1add7b29792b5ff80d

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.

line012 - copie

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… :slight_smile: (“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. :frowning: 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.
image
image

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

Possibly the fudge factor?

1 Like