# Get vertices of a terrain mesh affected by a brush or placement shape

I have the following mesh, it has very simple structure. You can think of it as a terrain from top-down view: each vertex (red and numbered) is a fixed distance away from its four neighbours in the horizontal xz plane (e.g 1 unit); only y (height) is different.

How could I get the vertices affected by a given overlaid shape?

By "Affected" I mean vertices that are inside or on the border of the shape, and any vertices that share a triangle with them.

Here I've drawn a pink rectangle on my mesh, and circled in green the vertices that should be considered "affected" by that shape.

I know:

• The constant distance between vertices
• The center of the mesh as a Vector3 (mesh is a square)
• The mesh's width/height (any corner could be calculated easily)

Some context, for what?

• Flatten terrain on when building a structure, road, etc
• Edit terrain with a brush (circle and other brushes)
• Vertex/texture painting, etc

This is actually a problem that GIS software can help you with. The easiest way to solve it is to just use the NetTopologySuite library instead of you implementing the algorithms that it uses. The best way to figure out how to use it is by looking at the tests.

I'm thinking it might look something like this.

var fact = new NetTopologySuite.Geometries.GeometryFactory();

var polygonSelect = fact.CreatePolygon(
new NetTopologySuite.Geometries.Coordinate[] {
new NetTopologySuite.Geometries.Coordinate(0, 0),
new NetTopologySuite.Geometries.Coordinate(0, 3),
new NetTopologySuite.Geometries.Coordinate(3, 3),
new NetTopologySuite.Geometries.Coordinate(3, 0)
});

var mpt = fact.CreateMultiPointFromCoords(
new NetTopologySuite.Geometries.Coordinate[] {
new NetTopologySuite.Geometries.Coordinate(1, 1),
new NetTopologySuite.Geometries.Coordinate(2, 2),
});

var pointCollectionSelected = mpt.Intersection(polygonSelect);