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

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); 

This answer assumes simple shapes as per OP's comment, as well as the terrain being broken up into smaller, manageable chunks (you should probably be doing this anyway).

First of all, treat the whole thing as 2D for the purpose of these calculations.

Then implement a common Shape or similar class (perhaps better an interface) that has a function that takes some points and returns a list of points the Shape contains. The exact struct/class of the points doesn't matter and probably depends on the framework/engine you're using if any.

Circles are straightforward, just check every point in your terrain chunk against the centre of the circle - anything with smaller distance than its radius is inside.

Rectangles are easy if aligned to the coordinate grid - but if you want arbitrary rotation, it is not hard. If you know your rectangle's centre and its rotation, you can rotate the rectangle and the points the opposite way, then use the axis aligned algoritm - any point that has its X coord more than rectangle's origin X and less than rectangle's origin X + width, same for its Y (Z) coord. In your case you are probably using X-Z as the "flat" directions and Y as the "ignored" height, so keep that in mind.

Any other stuff, probably the same, just rotate to axis align and calculate from that.

You'll probably be returning indices anyway, so not really needed to "unrotate" stuff after you're done with it as you're working on a copy of the vertex data anyway.

It might even be simpler to never touch the vertex data at all and use some "fixed" constant grid that you just copy and rotate to axis align, calculate indices and then dispose the copy at the end.

Your function then would look something like this in pseudocode:

for (x, y) generate point P for index x,y rotate by inverse of Shape's rotation if needed check if it's inside the inverse rotated Shape add to list of indices if true 

Once you have found the vertices that the Shape contains, you can also add any vertices that share a triangle with it by simply checking for each vertex as this is pretty fixed for such a grid.