[Closed] Circle Collision

Welcome to scripting and to the forum!
Please use CODE tags when posting to make your code readable.

Had to do a similar thing long long time ago, although I picked the other approach; there were circles the new circles had to avoid colliding with, which as a side-effect allows you to continue running a script on a partially filled area (with or without changing the parameters). It was just one-off thing, no clever solutions to fill all the gaps nor any GUI, everything is set in the first two groups of locals.

(
    ---------------------------------------------------------------------------------
    -- Private Globals
    ---------------------------------------------------------------------------------

	-- nodes
	local boundary = $boundary_circle
	local centerPoint = boundary.pos
	local boundaryRadius = boundary.radius
	local innerBounds = selection as array -- existing circles inside the bounding circle
	clearSelection()

	-- node settings
	local max_nodes = 250 + innerBounds.count -- limit of newly created circles
	local max_size = 2750 -- maximum circle size
	local min_size = 700 -- initial inserted circle size
	local min_gap = 150
	local min_growth = 10
	local max_growth = 50
	local min_pos = boundary.min
	local max_pos = boundary.max

	-- 2D grid variables
 	local gridData = #()
 	local gridAddress = #()
 	local gridUnit = 2 * (max_size + min_gap)

	-- collections
	local list = #()
	list[max_nodes] = undefined
	local nodesCount = 0
	local liveNodes = #{}


    ---------------------------------------------------------------------------------
    -- Structs
    ---------------------------------------------------------------------------------

	-- existing circles, their size doesn't change
	struct staticNode
	(
		index,
		pos,
		radius,
		obj,
		alive = false,

		fn updateNode =	()
	)

	-- inserted circles
	struct circleNode
	(
		index,
		pos,
		radius = min_size,
		obj = circle pos:pos radius:radius wirecolor:yellow,
		alive = true,
		growth = random min_growth max_growth,

		fn updateNode =
		(
			if alive do
				alive = (radius = (obj.radius += growth)) < max_size AND
				((distance centerPoint pos) + min_gap + radius) < boundaryRadius
			liveNodes[index] = alive
		)
	)

    ---------------------------------------------------------------------------------
    -- Functions
    ---------------------------------------------------------------------------------

 	fn build2DGrid =
	(
		local start = [int(min_pos/gridUnit).x, int(min_pos/gridUnit).y]
		local end = [int(max_pos/gridUnit).x, int(max_pos/gridUnit).y]

		for x = start.x to end.x do
			for y = start.y to end.y do
			(
				append gridAddress (getHashValue [x,y])
				append gridData #()
			)
	)

 	fn get2DGridAddress pos =
 	(
 		pos /= gridUnit
 		[int(pos.x), int(pos.y)]
 	)
 	
 	fn getItemsNearPos pos tolerance:1 = 
	(
		local items = #()
		local posAddress = get2DGridAddress pos

		for x = posAddress.x - tolerance to posAddress.x + tolerance do
			for y = posAddress.y - tolerance to posAddress.y + tolerance do
				join items gridData[findItem gridAddress (getHashValue [x,y])]

		items
	)

	fn circlesCollide pos1 pos2 radius1 radius2 =
		distance pos1 pos2 < radius1 + radius2 + min_gap

	fn addNode pos =
	(
		if ((distance centerPoint pos) + min_gap + min_size) < boundaryRadius then
		(
			nodesCount += 1
			list[nodesCount] = circleNode index:nodesCount pos:pos
			true
		)
		else false
	)

	fn addPoints =
	(
		if addNode (random min_pos max_pos) do
		(
			local addedPoint = list[nodesCount]
			local pointPos = addedPoint.pos
			local gridPos = get2DGridAddress pointPos
			local neighbors = getItemsNearPos gridPos -- first get the neighbors

			-- only after that add the node so we don't test it against itself
			append gridData[findItem gridAddress (gridPos as string)] addedPoint

			for item in neighbors while addedPoint.alive
				where circlesCollide pointPos item.pos min_size item.radius do
				(
					delete addedPoint.obj
					list[nodesCount] = undefined
					liveNodes[nodesCount] = false
					nodesCount -= 1
				)
		)
	)

	fn killPoints =
		for i = 1 to nodesCount do
			for j = i+1 to nodesCount
				where (list[i].alive OR list[j].alive) AND
				circlesCollide list[i].pos list[j].pos list[i].radius (list[j].radius + min_gap) do
				(
				   list[i].alive = false
				   list[j].alive = false
				)

	fn updateList =
		for item in list
			where item != undefined do
				item.updateNode()

    ---------------------------------------------------------------------------------
    -- Main
    ---------------------------------------------------------------------------------

	build2DGrid()
	clearListener()

	for bound = 1 to innerBounds.count do
	(
		local obj = innerBounds[bound]
		local pos = obj.pos
		local radius = obj.radius

		local addedNode = staticNode index:bound pos:pos radius:radius obj:obj
		list[bound] = addedNode
		
		local extra_size = if radius > max_size then radius - max_size else 0
		local start = get2DGridAddress (pos - extra_size)
		local end = get2DGridAddress (pos + extra_size)

		for x = start.x to end.x do
			for y = start.y to end.y
				where (local gridIndex = findItem gridAddress ([x,y] as string)) > 0 do
					append gridData[gridIndex] addedNode

		nodesCount += 1
	)

	with undo off, redraw off
	(
		-- continue adding circles till we reach the limit
		while nodesCount < max_nodes AND NOT keyboard.ESCpressed do
		(
			addPoints()
			killPoints()
			updateList()

			windows.processPostedMessages()
			pushPrompt ("Remaining to add: " + (max_nodes - nodesCount) as string)
		)

		-- continue growing circles till all are dead
		while liveNodes.numberSet > 0 AND NOT keyboard.ESCpressed do
		(
			killPoints()
			updateList()

			windows.processPostedMessages()
			pushPrompt ("Remaining to grow: " + (liveNodes.numberSet) as string)
		)
	)
)

you have to understand that yours and Clovis’s algorithms are very slow. it might work for ~100 nodes, but not for ~1000. it’s much faster generate ‘non-intersected’ nodes, and find and delete ‘intersected’ after all. and more… the theory says that is faster to randomly generate nodes wherever than search for ‘non-intersected’ place for every new one.

spaw,
have you seen this my post? http://forums.cgsociety.org/showpost.php?p=7032076&postcount=23

Very fast and cool for a 2d and 3d case but im wondering if you need to specify the number of points as in the sphere question (i.e. a surface ) I have going or even points on a plane. Do you think there is a way to get just the number of points you want if you are using a uniform grid?

Thanks

-Michael