-1

Given plane points p,q,r how do you decide whether the triangle contains an integral point? I want to list all such points.

It has a subproblem: Given a fourth point s. How do you decide whether s is inside the triangle?

Henrik4
  • 464
  • 3
  • 13
  • A plane is an infinite surface. It contains infinite points whose some of `x,y,z` is integer. – Ripi2 May 23 '20 at 23:38
  • [Point inside a triangle in 3D](https://stackoverflow.com/questions/37545304/determine-if-point-is-inside-triangle-in-3d) – Ripi2 May 23 '20 at 23:40
  • @Ripi2 The question you refer to is related to the subproblem albeit not quite the same. – Henrik4 May 24 '20 at 07:32

1 Answers1

1

You need triangle rasterization.

enter image description here

Possible approach: sort vertices by Y-coordinate, for every vertical interval between vertices determine side equations and for every integer Y in this interval get left and right integer points, then fill whole horizontal scanline of inner points.

For example, "left top" side of triangle has equation 2.2*y - x + 1.5 = 0 in y-range 3.14..17.3. The first integer Y is 4, substitution gives 10.3 - x = 0, so the leftmost integer x value is 11. Similar procedure for right edge gives the rightmost value (say p), so we output points (11,4), (12,4)...(p,4)

Arbitrary found article

subproblem - this is completely different problem. It is not needed for retrieving all integral points.
If you really need it - calculate signs of cross products of sides with vector to point (AB x AP, BC x BP, CA x CP)

MBo
  • 77,366
  • 5
  • 53
  • 86
  • Thanks for this valuable contribution. But the application is not in computer graphics but integer linear programming. Your approach may be workable but it's not very clear and I'm not convinced that it's efficient. You're doing some kind of transform of the coordinates, but seem to forget that it must preserve integral points. As for the subproblem, yeah this is one way of doing it. – Henrik4 May 24 '20 at 16:27
  • It is quite efficient - all graphics cards/engines use some kind of triangle rasterization to fill polygon pieces, millions triangles per second. What transform are you talking about? Most graphic routines work in integer coordinates - for example, look at Bresenham algorthm for line segments – MBo May 24 '20 at 16:35
  • But this is not a graphics routine and the points p,q,r are not integral. I'm working in the euclidean plane. – Henrik4 May 24 '20 at 17:55
  • It is not important. Line equation works even better :) for float values. – MBo May 24 '20 at 18:01