[Solved] Finding coordinates from an outline

[xilef11]

Hello

 

I am creating a "block" that lifts terrain around it. The area to lift is defined by placing "marker" blocks in a connected shape that encloses the "lifter" block, on the same Y level. This has raised a few interesting questions:

 

1) Finding the outline:

This is the easy part, just search in any/all cardinal directions until a marker block is found (or a max distance is reached), then recursively find all connected marker blocks.

 

2) Making sure the outline is a closed shape around the lifter:

I would do this by making sure there is a marker block in all cardinal directions around the block, then checking that all marker blocks previously found have at least 2 other marker blocks connected to them. However, that looks like it could be slow.

 

3) Finding the area inside the outline

This is the part I don't know how to do, and also the more "general" problem: given a 2D grid with a known outline (and a "center" point), how to find the coordinates of all squares inside that outline?

 

Thoughts?

[JoseluGames]

I could answer the third, simply take the position of the marker with lower x and z coords, do a for loop until you arrive to the coords of the marker with the highest coords (If that's the question)

[xilef11]

I could answer the third, simply take the position of the marker with lower x and z coords, do a for loop until you arrive to the coords of the marker with the highest coords (If that's the question)

That would only work if the area was rectangular...

 

I would make a Shape class (or use an existing one from a library) with a "containsPoint" method. Then you can implement this method however is needed for every type of shape.

The problem is that I can't know what the shape will be... all we have is the coordinates of the blocks that form the outline (which are connected), as well as the coordinates of a block somewhere inside the shape

[xilef11]

that... is a surprisingly simple algorithm, considering all I could think of involved vector math (and wouldn't work).  always google first 

 

the only issue I see here is speed, since it looks like I'll have to iterate through all blocks within the "bounding rectangle" of the polygon, then check if it is on the inside, which involves iterating through all blocks on the outline (so at least width*height*perimeter checks). I have a similar concern with the check to make sure the border is actually closed. Not sure if something can be done about that though.

[xilef11]

I ended up using the first algorithm and ignoring the "closed edge" problem. I also make the checks more efficient by storing the edge as a Map<Xpos, Set<Zpos>>.

 

However, it seems that the area found is not correct (includes only the edge, but the edge that gets printed to the log is incomplete). I feel that I missed something obvious

Code on GitHub because reading code on the forums is painful

 

Edit: Yup, that was it: a few copy-paste derps in setting the NW and SE blocks.