Skip to content

A method to return a cut section of any polygon geometry

Ishan Joshi edited this page Jun 13, 2019 · 1 revision

Considering a polygon intersected by a line and we need to determine the part or the segment of the polygon that lies above it.

The algorithm works in two steps:

  • Determining the vertices (or points) that lie above the given line.
  • Adding those point to the list of the vertices of the new polygon segment.

How to determine whether a point lies above or below a line?

If we assume the equation of the line to be ax + by + c and the point to be checked be (x1, y1), then:

  • if (ax1 + by1 + c)/b = 0 implies that the point lies on the line.
  • if (ax1 + by1 + c)/b > 0 implies that the point lies above the line.
  • if (ax1 + by1 + c)/b < 0 implies that the point lies below the line.

Adding the points to the list of the vertices of the new polygon segment.

For a point which lies above the line has two cases:

  • Whether the previous point also lies above the line: If this is the case then it means we have to directly add that point to the new list.
  • Whether the previous point lies below the line: Here it means that the polygon edge (b/w the current and the previous point) is moving upwards and intersecting the line, hence in such a case we have to add the intersection point first and then add the current point to the list.

For a point which lies below the line has again two cases:

  • Whether the previous point also lies below the line: In such a case we will be ignoring the point and no action will be taken
  • Whether the previous point lies above the line: It means the polygon edge (b/w the current and the previous point) is moving downwards and intersecting the line, hence in such a case only the intersection point is included.

The implementation of this algorithm has been proposed in PR #17001

Clone this wiki locally
You can’t perform that action at this time.