CODEWITHSUNDEEP
mathgraphics
tune2fs
tune2fs

Reputation: 7705

Find all integer points in area defined by two lines

I need an efficient way to get all integer points in an area defined by two lines.

I start with a line defined by two points Pt1 and Pt2. This line is then moved such that I get two new points Pt1new and Pt2new. I then need to find all eulerian points which are in the area generated by the movement of the lines.

For the easy case it is no problem as I there will simply generate an rectangle area between the mimimal x and y value to the maximal x and y value. And then check if the founded intersection points with the eulerian grid are actually inside the area generated by my points. (By going of the points in clockwise direction and check if the point is always on the right side)

However for the second problem (the lower one in the image) this seems not to work as I cannot easy check if the point is actually inside the area. How can I find all those points in an fast ane easy way.

In the graphic I am interested to find the green points. Which lay on the eulerian grid (e.g. x and y coordinates are integer values).

image of problem

Upvotes: 0

Views: 190

Answers (2)

Phil H
Phil H

Reputation: 20131

I think you need to change your reference.

Imagine your origin is anchored to your line, and it is actually the grid that is moving. You can clearly see then that in the first the grid points highlighted have moved up over the line. In the second, the grid has rotated and only the highlighted point has moved over the line.

Since everything is linear (there are no curves here), if a point is 'below' the line before the transformation, and below it afterwards, then it has never crossed it.

Define, then a measure of whether a point is below or above the line. If the furthest either end of your line moved was 3 units, then we only need to consider grid points up to 3 units away from the line. For each of these points, test whether it is below or above the line before and after the transformation. If its status changed, then the line passed it. If not, then it didn't.

The above/below measure, then. The line is defined by

y = mx + c.

A point p (px,py) is above the line if

py > m.py + c.

In matrices, we can first translate both the line AB (ax,ay to bx,by) and the point (px,py) to put A at the origin:

Q' = Q + | -ax |
         | -ay |

We can then rotate it to align the axis with the line. Since the angle between the line and the x axis is given by sin(θ) = (dy / d), and cos(θ) = (dx / d):

d = sqrt((by-ay)^2 + (bx-ax)^2)
s = (by-ay)/d
c = (bx-ax)/d

The rotation matrix for an angle is given in this wikipedia page, and using s and c we get:

R = |  c  s |
    | -s  c |

Applying the translation and then rotation to the line brings the lie along the x axis, from the origin up to x=d. The point will then have either a positive or negative y value. So applying this to point p:

q = R(p+T) = |  c  s | ( |px| + |-ax|  
             | -s  c |   |py|   |-ay|  )

p'x = px - ax
p'y = py - ay
qx =  c * p'x + s * p'y
qy = -s * p'x + c * p'y

Suppose we perform this on point P, for two different lines AB and CD. We will get two points F and G (the transformed points before and after). The point has crossed the line (as it were) if:

if( signof(fy) != signof(gy) ) {
    // crossed the origin
}

But note that this only tests y. The point could have been merely passed by the line, if the line is too short to reach the point. So, test whether the x value has also changed:

if( (fx < 0) && (gx < 0) ||
    (fx > d) && (gx > d) ) {
    // whooshed past
}

So if you test both of these, you'll know whether the point crossed the line without whooshing past or not.

Hope that's clear...

Upvotes: 1

Peter Schneider
Peter Schneider

Reputation: 1701

If the two lines Pt1-Pt2 and Pt1new-Pt2new intersects at Point P0, find all the eulerian the Points in the triangle Pt1-Pt1new-P0 and Pt2-Pt2new-P0.

The simplest approach is the same as you use for the Quadrilateral. Calculate the bounding box and test every eulerian point inside. You may want to use barycentric coordinates to check this.

As a further generalization, you may want to always use triangles: Pt1-Pt2-Pt1new + Pt2-Pt2new-Pt1new in the normal and Pt1-Pt1new-P0 + Pt2-Pt2new-P0 in the degenerated one.

Upvotes: 3

Related Questions