Fill Irregilar Area?

[Faestus]

I need to fill an irregular area with stuff.

I need the area between multiple points to be filled with objects.

Is there a system or spell that can help me do this?

 

[Zwiebelchen]

Split your areas up into triangles, then use this:

function IsPointInTriangle takes real x1, real y1, real x2, real y2, real x3, real y3, real x, real y returns boolean
     local boolean b = (x2 - x) * (y3 - y2) - (x3 - x2) * (y2 - y) >= .0
     return ((x1 - x) * (y2 - y1) - (x2 - x1) * (y1 - y) >= .0) == b and b == ((x3 - x) * (y1 - y3) - (x1 - x3) * (y3 - y) >= .0)
endfunction

Without any further information about what you want to do, there's not much we can do.

 

[Faestus]

I want the red and the green farms gone, assuming that all farms are the same unit type, given only the coordinates of the red farms.

 

[Dr Super Good]

I want the red and the green farms gone, assuming that all farms are the same unit type, given only the coordinates of the red farms.

As mentioned you need to model the entire area as triangles composing only of vertices produced from the points (the red farms). You can then test if a farm is inside each of the triangles to get if it should be removed. The triangle grid will look very similar to the pathing mesh used by SC2 if you were to visualise it. Some complex tree system might allow you to discern which triangle a farm is in in logn time (n is number of triangles), which is pretty efficient given the complexity of the problem.

Another approach if you are only dealing with enclosed spaces (not the above) would be to model everything as tiles and then perform a fill brush operation on the area to generate a region (not rect, region (look at JASS)) consisting of all the area you want to check if something is in.

 

[Faestus]

Another approach if you are only dealing with enclosed spaces (not the above) would be to model everything as tiles and then perform a fill brush operation on the area to generate a region (not rect, region (look at JASS)) consisting of all the area you want to check if something is in.

A fill brush operation?

Please explain.

 

[Dr Super Good]

Well you keep testing neighbouring cells until you hit one with a red farm in which case you stop searching that direction and process the other directions.

 

[Faestus]

Well you keep testing neighbouring cells until you hit one with a red farm in which case you stop searching that direction and process the other directions.

Wouldn't that overload the engine?

(Given that it executes all these actions in one turn)

 

[Dr Super Good]

No as you just run it in multiple threads in a chain. Would it cause frame drop? Maybe but then again fill operations usually do. For small areas it should be fine though since there are not that many cells to fill.

The fastest is still some form of area test with area made up of triangles from the points. The structure would need to be tiered so that you avoid O(n) based point in triangle tests. I do not know of such a structure off my head.

 

[Faestus]

Yeah that does the job.

Anyway thanks!

 

[stan0033]

Err... use collision size, pathing type...?