[Closed] Find visual center of contour/polygon

here it is as a 2010 max file

shape.max (184 KB)

Oh, yes. Now it works as expected.

ptsArr = for k = 1 to numKnots myPolygon 1 collect 
		(
			kPos = getKnotPoint myPolygon 1 k
			[kPos.x, kPos.y,0]
		)
		append ptsArr ptsArr[1]
polygon = #(ptsArr)

By the way, if I use precison=0.1 and the while loop is stopped when the currCell.data.z - bestCell.data.x > precision is true for the first time, the result is almost the same as when the while loop is not stopped(this is valid for all the polygons I tested). With precision=1 the situation is not the same and the while loop must not be stopped.

I have a question about this while loop.

qsort cells cellSorter
			while cells.count != 0 do
			(
				-- pick the most promising cell from the queue
				
				currCell = cells[cells.count]
				cells.count = cells.count - 1

				-- update the best cell if we found a better one
				if (currCell.data.x > bestCell.data.x) do
				(
					bestCell = currCell
					if (debug) do format "found best % after % probes... precision:%\n" currCell.data.x numProbes precision
				)

				-- do not drill down further if there's no chance of a better solution
				if (currCell.data.z - bestCell.data.x > precision) do
				(
					-- split the cell into four cells
					h = currCell.data.y/2.0
					append cells (makeCell [currCell.center.x - h, currCell.center.y - h, 0] h polygon)
					append cells (makeCell [currCell.center.x + h, currCell.center.y - h, 0] h polygon)
					append cells (makeCell [currCell.center.x - h, currCell.center.y + h, 0] h polygon)
					append cells (makeCell [currCell.center.x + h, currCell.center.y + h, 0] h polygon)
					numProbes += 4
					
					qsort cells cellSorter  -- !!! only here.
				)
			)

I still wonder why the while loop must not be stopped when (currCell.data.z - bestCell.data.x < precision) is true.
Sorting the cells always forces the while loop to check the most promising cell first. Lets say that after 10 iterations we have the first 3 cells with the same maxDistance, for example 5.3.
The while loop will pick the first cell(of these 3 cells) and when its find that the (currCell.data.z - bestCell.data.x < precision) is true, why we have to check the next cells and to divide the first cell to 4 new cells?

If we divide the first cell to 4 new cells, the maxDistance of each of these 4 new cells has to be less than the maxDistance of the first cell.

If the while loop is not stopped and it picks the second cell(from these 3 cells), it will compare the same values as in previous iteration(it has the same maxDistance as previous cell) and again the (currCell.data.z - bestCell.data.x < precision) will be true. The same will happen with the other 1 cells: (currCell.data.z - bestCell.data.x < precision) will be true.
These 3 cells are the best candidates and they have the same maxDistance. The maxDistance of each one of all other cells is less than the maxDistance of the first best candidate.
In this situation we will have 3 points which will be the centers of the 3 largest inscribed circle in the polygon, and these 3 circles will have the same radius. So, which one of these 3 points will be used as a final result does not matter.

I have tested several polygons and the numProbes: are the same when the while loop is not stopped and when it is stopped the first time when the (currCell.data.z - bestCell.data.x < precision) is true, and the bestCell is always the same. Maybe with proper polygon there will be significant difference between stopped and non stopped while loop.

=======

@Klvnk can you test your c++ version with this shape: https://drive.google.com/file/d/1KfKzjcnb7d-RskR6pQqT54LVELEHqk_m/view?usp=sharing

With precision set to 0.1 the js ported code(with almost all improvements from the Denis’ last version of the script) I have this result:
numProbes: 16750
best distance: 162.478
precision:0.1 time:56803 heap:80946052L

With the last code from Denis:
num probes: 16750
best distance: 162.478
precision:0.1 time:443424 heap:262513116L

With precison = 1.0
JS version:
numProbes: 2422
best distance: 162.478
precision:1 time:1535 heap:11663264L

Denis version:
num probes: 2422
best distance: 162.478
precision:1 time:8332 heap:1278508L

no probs i get this…

shape001.jpg1276×790 20.9 KB

a slight deviation I have my xml format for handling max shapes if you’re interested…
xmlshape.ms (6.6 KB)
it’s an importer/exporter I never particularly liked any other of the “factory” options in max.

takes about 0.8 secs to do it 10,000 times @ 0.1 prec on that shape, i removed the debug code though

Why do you need so high precision? It doesn’t make sense to be lower than a half of the length to the closest edge… I guess.

image.png544×706 20.1 KB

Here is my example.
All shapes have different position, rotation, mirror, scale… but the algorithm finds exactly the same relative point. The precision is the half of maximum distance of “the most promising cell”

BTW. It takes ~1-2 msec per shape using MXS version

Do you redefine the precision every time when the cells are sorted, or you set the precision after the first sort(outside of the while loop)?

I set it once after getting all cells…

Try another one.
we do:
h = cellSize/2.0
change it to:
h = cellSize/8.0
for example, and set precision to something very high like FLT_MAX

I have the same result but much faster

The time is 0, the result is the same.