work out size of town

BR_Grid_minSettlement  = 10;				//you need this many buildings to be treated as a city
BR_Grid_settlementTreshold = 55;			//gap between houses to be considered as in the same city

BR_Grid_objBlacklistL1 = ["GHV"];
BR_Grid_objBlacklistL2 = ["CAL","GHV","WALL","BARR","POW"];
BR_Grid_houseObj = "House_F";
BR_Grid_ruinObj = "Ruins_F";

BRfn_convexHull =
{
	/*
	   Auhtor:
	    r?be

	   */

	private ["_points", "_spacing", "_minDistance", "_n"];

	_points = [];
	_spacing = 0;
	_minDistance = 0;

	if ((count _this) > 1) then
	{
	   _spacing = _this select 1;
	};

	if ((count _this) > 2) then
	{
	   _minDistance = _this select 2;
	};

	// empty list?
	if ((count (_this select 0)) == 0) exitWith
	{
	   []
	};

	private ["_extrapolate"];

	// 1 pos/object -> 4 positions
	_extrapolate =
	{
	   private ["_pos", "_dir", "_x", "_y", "_offset"];
	   _pos = _this select 0;
	   _dir = _this select 1;
	   _x = ((_this select 2) select 0) * 0.5;
	   _y = ((_this select 2) select 0) * 0.5;
	   _offset = _this select 3;

	   // apply offset
	   if (((_offset select 0) != 0) || ((_offset select 1) != 0)) then
	   {
	      _pos = [_pos, _offset, _dir] call BRfn_offsetPosition;
	   };

	   // return the four positions
	   [
	      ([_pos, [(_x * -1), _y], _dir] call BRfn_gridOffsetPosition),
	      ([_pos, [_x, _y], _dir] call BRfn_gridOffsetPosition),
	      ([_pos, [_x, (_y * -1)], _dir] call BRfn_gridOffsetPosition),
	      ([_pos, [(_x * -1), (_y * -1)], _dir] call BRfn_gridOffsetPosition)
	   ]
	};

	if ((typeName ((_this select 0) select 0)) == "OBJECT") then
	{
	   // objects & bounding box
	   private ["_box"];
	   {
	      _box = _x call BRfn_boundingBoxSize;
	      _points = _points + ([
	         (position _x),
	         (direction _x),
	         _box,
	         (boundingCenter _x)
	      ] call _extrapolate);
	   } forEach (_this select 0);
	}
	else
	{
		// positions as points (no extrapolation needed)
		_points = +(_this select 0);
	};

	_n = count _points;

	// no or too few points (to form a polygon)?
	if (_n < 3) exitWith
	{
	   []
	};

	private ["_theta", "_convexity"];

	// point1, point2 => scalar between 0 and 360
	//  returns NOT the angle made by p1 and p2 with
	//  the horizontal but which has the same order
	//  properties as the true angle (easier to compute)
	_theta = {
	   private ["_theta", "_dx", "_dy"];

	   _theta = 0;

	   _dx = ((_this select 1) select 0) - ((_this select 0) select 0);
	   _dy = ((_this select 1) select 1) - ((_this select 0) select 1);

	   if ((_dx == 0) && (_dy == 0)) then
	   {
	      _theta = 0;
	   } else {
	      _theta = _dy / ((abs _dx) + (abs _dy));
	   };

	   if (_dx < 0) then
	   {
	      _theta = 2 - _theta;
	   } else {
	      if (_dy < 0) then
	      {
	         _theta = 4 + _theta;
	      };
	   };

	   (_theta * 90)
	};


	// p0, p1, p2 => scalar, where
	//  _convexity < 0  == clockwise
	//  _convexity == 0 == collinear
	//  _convexity > 0  == counter-clockwise
	_convexity = {
	   (
	      (((_this select 1) select 0) - ((_this select 0) select 0)) *
	      (((_this select 2) select 1) - ((_this select 0) select 1)) -
	      (((_this select 1) select 1) - ((_this select 0) select 1)) *
	      (((_this select 2) select 0) - ((_this select 0) select 0))
	   )
	};

	/******************************************************
	 * graham scan
	 */

	// 1) finds the extremal or lowest (and left-most) point
	// and puts/swaps it to the front
	for "_i" from 1 to ((count _points) - 1) do
	{
	   if ((((_points select _i) select 1) < ((_points select 0) select 1)) ||
	       ((((_points select _i) select 1) == ((_points select 0) select 1)) &&
	        (((_points select _i) select 0) < ((_points select 0) select 0)))) then
	   {
	      [_points, 0, _i] call BRfn_arraySwap;
	   };
	};

	// 2) sort by theta
	_points = [_points, {
	   ([(_points select 0), _this] call _theta)
	}] call BRfn_arrayShellSort;


	// 3) graham scan
	private ["_convexHull", "_m"];
	_convexHull = [
	   (_points select 0),
	   (_points select 1)
	];

	_m = 2;
	for "_i" from 2 to _n do
	{
	   // backtracking, eliminating right turns and
	   // straight lines (collinear)
	   while {(([
	               (_points select _m),
	               (_points select (_m - 1)),
	               (_points select _i)
	            ] call _convexity) >= 0)} do
	   {
	      _convexHull call BIS_fnc_arrayPop;
	      _m = _m - 1;
	   };
	   //_convexHull = _convexHull + [(_points select _m)];
	   _convexHull set [(count _convexHull), (_points select _m)];
	   _m = _m + 1;
	   [_points, _m, _i] call BRfn_arraySwap;
	};



	// apply spacing
	if (_spacing != 0) then
	{
	   private ["_center"];
	   _center = _convexHull call BRfn_polygonCentroid;
	   [
	      _convexHull,
	      {
	         ([
	            _this,
	            _spacing,
	            ([_center, _this] call BIS_fnc_dirTo)
	         ] call BIS_fnc_relPos)
	      }
	   ] call BRfn_arrayMap;
	};


	private ["_relHullPos", "_reduceConvexHull"];

	// relative access to points on the convex hull
	// [_index, _shift] => _index
	_relHullPos = {
	   private ["_index", "_shift", "_n", "_pos"];
	   _index = _this select 0;
	   _shift = _this select 1;
	   _n = count _convexHull;

	   _pos = _index + _shift;

	   if (_pos < 0) exitWith
	   {
	      (_n + _pos)
	   };

	   if (_pos >= _n) exitWith
	   {
	      (_pos % _n)
	   };

	   _pos
	};

	// recursively reducing the convex hull by
	// merging two points into a new one
	_reduceConvexHull = {
	   private ["_n", "_i", "_j", "_d"];
	   _n = count _convexHull;

	   if (_n < 5) exitWith
	   {
	      true
	   };

	   for [{_i = 0}, {_i < _n}, {_i = _i + 1}] do
	   {
	      _j = [_i, 1] call _relHullPos;
	      _d = (_convexHull select _i) distance (_convexHull select _j);
	      if (_d < _minDistance) exitWith
	      {
	         private ["_newPoint", "_newHull", "_a1", "_a2", "_m", "_k"];
	         // merge point _i and _i + 1 into new point
	         _newPoint = [
	            (_convexHull select ([_i, -1] call _relHullPos)),
	            (_convexHull select _i),
	            (_convexHull select _j),
	            (_convexHull select ([_i, 2] call _relHullPos))
	         ] call BRfn_lineSegmentIntersection;

	         // alter convex hull
	         _newHull = [];
	         _a1 = _i min _j; // will be overwritten with the new point
	         _a2 = _i max _j; // will be dropped
	         _m = 0;

	         for [{_k = 0}, {_k < _n}, {_k = _k + 1}] do
	         {
	            if (_k != _a2) then
	            {
	               if (_k == _a1) then
	               {
	                  _newHull set [_m, _newPoint];
	               } else {
	                  _newHull set [_m, (_convexHull select _k)];
	               };
	               _m = _m + 1;
	            };
	         };

	         _convexHull = _newHull;

	         // run again until the convex hull coudn't be
	         // reduced any further...
	         [] call _reduceConvexHull;
	      };
	   };

	   true
	};

	// apply minDistance
	if (_minDistance != 0) then
	{
	   [] call _reduceConvexHull;
	};


	// close hull/polygon
	_convexHull = _convexHull + [(_convexHull select 0)];

	// return convex hull
	_convexHull
};
BRfn_getFarthest =
{
		/*
		function returns farthest element from a positions array to a given position

		Input:
		0: [array of positions] or [array of objects]
		1: position
		(2: max distance - optional)

		Return:
		[farthest element, index of farthest,distance]
	*/
	private ["_pos","_array","_dst","_idx","_elem","_ndst","_nArray"];
	_array = _this select 0;
	_pos = _this select 1;
	_maxDst = 1000000;
	if (count _this > 2) then {_maxDst = _this select 2};

	if (count _array == 0) exitWith {[]};

	_elem = _array select 0;
	_dst = 0;
	_idx = -1;
	{
		_ndst = _pos distance _x;
		if (_ndst > _dst && _ndst < _maxDst) then
		{
			_dst = _ndst;
			_idx = _forEachIndex;
			_elem = _x;
		};
	} foreach _array;

	[_elem, _idx,_dst]
};

BRfn_inString =
{
	/*
	   Author:
	    r?be

	   Description:
	    check's whether a given string is a substring of/in another
	    string.

	   Parameter(s):
	    _this select 0: needle (string)
	    _this select 1: haystack (string)

	   Returns:
	    boolean
	*/

	private ["_match", "_needle", "_haystack", "_n", "_h", "_index", "_i"];

	_match = false;

	_needle = toArray (_this select 0);
	_haystack = toArray (_this select 1);

	_n = count _needle;
	_h = count _haystack;

	if (_n > _h) exitWith {false};

	_index = 0;

	for "_i" from 0 to (_h - 1) do
	{
	   if ((_haystack select _i) == (_needle select _index))
	   then {_index = _index + 1}
	   else {_index = 0};

	   // needle found!
	   if (_index == (_n - 1)) exitWith {_match = true};
	};

	// return result
	_match
};

BR_Grid_GetSettlementHull =
{
	private ["_startPos","_queue","_houses","_isFailed","_t","_failed","_pullIn","_b","_nearby","_no","_startObj","_chull","_center","_area","_perimax"];
	_startPos = _this;
	_queue = [];
	_houses = [];

	//local fncs
	_isFailed =
	{
		private ["_failed","_t"];
		_t = typeOf _this;
		_failed = false;
		if ((getPosASL _this) select 2 < 0)  exitWith {true};
		if (getNumber(configFile>>"CfgVehicles">>_t>>"scope") != 1) exitWith {true};
		{
			if ( ([_x,toUpper _t] call BRfn_inString)) exitWith {_failed = true};
		} foreach BR_Grid_objBlacklistL1;
		_failed
	};

	_pullIn =
	{
		private ["_b","_nearby"];
		_b = _this;

		if (_b getVariable ["BR_Grid_sid",0] != 1) then
		{
			_b setVariable ["BR_Grid_sid",1];
			_houses set [count _houses,_b];
			//[str (getPos _b),getPos _b,0,"hd_dot","ColorWhite"] call BRfn_marker;
		};

		_nearby = (getPosATL _b) nearObjects [BR_Grid_houseObj, BR_Grid_settlementTreshold];
		_nearby = _nearby + ((getPosATL _b) nearObjects [BR_Grid_ruinObj, BR_Grid_settlementTreshold]);

		{
			if (_x getVariable ["BR_Grid_sid",0] == 0) then
			{
				if (_x call _isFailed)
				then {_x setVariable ["BR_Grid_sid",-1]}
				else {_queue set [count _queue,_x]};
			};
		} foreach _nearby;
	};

	//get a building
	_no = nearestObjects [[_startPos select 0, _startPos select 1, 0], [BR_Grid_houseObj,BR_Grid_ruinObj], BR_Grid_settlementTreshold];

	//start searching loop
	if (count _no > 0) then
	{
		_startObj =	_no select 0;
		_startObj call _pullIn;
		while {count _queue > 0} do
		{
			_startObj = _queue select (count _queue - 1);
			_queue resize (count _queue - 1);
			_startObj call _pullIn;
		};
	};

	//register
	_chull = [];
	if (count _houses > BR_Grid_minSettlement) then
	{
		_chull = [_houses,5] call BRfn_convexHull;
		//_center = _chull call BRfn_polygonCentroid;
		//_area = _chull call BRfn_polygonArea;
		//_perimax = ([_chull, _center] call BRfn_getFarthest) select 2;

	};

	//unreg
	{_x setVariable ["BR_Grid_sid",nil];} foreach _houses;

	_chull
};

BRfn_polygonCentroid =
{
	/*
		Although Ruebe's algorithm below is far more precise, but it just doesn't work with small polys.
		Switched to a lot simplier method, which doesn't give you the actual centroid, but always gives you something like it.
	*/
	private ["_positions","_minx","_maxx","_miny","_maxy","_tx", "_ty"];
	_positions = _this;

	_minx = 100000;
	_miny = 100000;
	_maxx = 0;
	_maxy = 0;
	{
		_tx = _x select 0;
		_ty = _x select 1;

		if (_tx > _maxx) then {_maxx = _tx};
		if (_tx < _minx) then {_minx = _tx};
		if (_ty > _maxy) then {_maxy = _ty};
		if (_ty < _miny) then {_miny = _ty};
	} foreach _positions;

	[_minx + ((_maxx - _minx) / 2),_miny + ((_maxy - _miny) / 2),0]
};



//----------------------------------------------------------------------------------------------------
//
//
//
//----------------------------------------------------------------------------------------------------


BR_makeCityArray =
{
	_allCities = nearestLocations [getPos player, ["NameCityCapital","NameCity", "NameVillage"], 100000];

	BR_cityarray = [];
	{
		startLoadingScreen[str _foreachIndex];
		_set = (getPos _x) call BR_Grid_GetSettlementHull;
		_fset = [];
		if (count _set > 0) then
		{
			_center = _set call BRfn_polygonCentroid;
			_perimax = ([_set, _center] call BRfn_getFarthest) select 2;
			_fset = [_set,_center,_perimax];
		};
		BR_cityarray set [count BR_cityarray, _fset];
		endloadingscreen;
	} foreach _allCities;

	copyToClipboard str BR_cityarray;

	BR_cityarray
};