[RISOLTO] Racchiudere più punti di una dispersione in un qua

[bennes]

Salve a tutti, voglio sottoporvi un problema di natura più logica che programmativa.

Ho un'immagine nera, con una serie di punti bianchi di cui conosco le coordinate (una sottospecie di grafico). Questi punti si dispongono in maniera concentrata attorno ad un centro, e vanno via via diradandosi man mano che si allontanano.
Ora, il "centro" lo calcolo semplicemente facendo la media aritmetica prima sull'asse X e poi sull'Y delle coordinate dei punti, e fin qui ok.

Il problema sta nel momento in cui devo racchiudere la parte dell'immagine piu' densa di punti in un quadrato/rettangolo.
Mi spiego meglio: vorrei che il centro di cui ho parlato prima fosse il centro di un quadrato che contiene la maggior parte di punti, tralasciando quelli piu' lontani dal centro. In sostanza l'unico dato che mi manca è la lunghezza del lato del quadrato in questione.
Qualcuno sa come realizzare una cosa simile?

Se non mi sono spiegato chiedete, e scusate per il titolo, non avevo idea di cosa mettere
Grazie in anticipo!

[Alberto11]

nella misura in cui le leggi della matematica si riferiscono alla realtà non sono certe e
nella misura in cui sono certe non si riferiscono alla realtà

[Zoff]

Ma quanti punti devi racchiudere?
Parlando di maggiore densità immagino che tu abbia una % obbiettivo e tu voglia calcolare la dimesione del quadrato che racchiude quella %.
E' corretto?

Puoi escludere a priori la presenza di piu' "aree ad alta densità"?

[bennes]

Grazie per aver risposto! Hai capito bene, la quantità di punti è in percentuale, ed escludo anche più "aree ad alta densità". Il problema è che non so come trovare la lunghezza del lato

[Zoff]

Io partirei con calcolare il baricentro (che da come hai scritto mi sembra essere quello che tu chiami "centro").
In pseudo-codice

Codice: Seleziona tutto

var baricentro = { x:0, y:0};
for punto in punti
    baricentro.x += punto.x
    baricentro.y += punto.y
baricentro.x /= punti.length
baricentro.y /= punti.length

A questo punto partendo da un lato (chiamiamolo L) pari a quello che racchiuderebbe TUTTI i punti (ovvero il 100%) procedi a calcolare la dimensione che soddisfa la tua % in maniera dicotomica.

Se non fosse chiara la ricerca dicotomica, procedi guardando quanti punti stanno nel quadrato con lato L/2, se sono di piu' cerchi in L/4, se sono meno cerchi in L/(3/4) e così via aumentando o diminuendo sempre della metà.

Info sulla ricerca dicotomica classica: http://it.wikipedia.org/wiki/Ricerca_dicotomica

[Vincenzo1968]

Puoi rappresentare l'immagine con un array in cui i punti non bianchi hanno valori negativi e i punti bianchi hanno valori positivi.
A questo punto possiamo utilizzare l'algoritmo di Kadane per la ricerca di un sottoarray di somma massima.

Nell'esempio che segue abbiamo un array di dieci righe e dieci colonne.
I punti bianchi sono rappresentati col valore 1; i punti non bianchi col valore -1.
Il programma restituisce il sottoarray(può essere rettangolare o quadrato) con la maggiore concentrazione di punti bianchi.

KadaneSubCubic.c

Codice: Seleziona tutto

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>
#include <time.h>
#include <limits.h>

/*
gcc -Wall -Wextra -pedantic -O2 KadaneSubCubic3.c -o prova3
*/

int main()
{
	int i, j, k, l, m, n, z, x, x1, x2, y1, y2, s, t, S;
	int index;
	
	int column[11][11];
	int a[11][11];

	int my_array[100] =
	{
		-1, -1, -1, 1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, 1, 1, 1, -1, -1, -1, -1, -1, -1,
		-1, 1, 1, 1, 1, -1, -1, -1, -1, -1,
		-1, 1, 1, 1, 1, 1, 1, -1, -1, -1,
		-1, 1, 1, 1, 1, 1, 1, 1, -1, -1,
		-1, 1, -1, -1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 1, -1, -1, -1, -1, -1, -1,
		-1, -1, -1, 1, -1, -1, -1, 1, -1, -1
	};
	m = 10;
	n = 10;

	index = 0;
	for( i = 1; i <= m; i++ )
	{
		for( j = 1; j <= n; j++ )
		{
			a[i][j] = my_array[index++];
		}
	}

	x1 = 0; x2 = 0; y1 = 0; y2 = 0;
	S = INT_MIN;

	for(z = 1; z <= m; z++)
	{
		for(i = 1; i <= n; i++)
			column[z - 1][i] = 0;
		for(x = z; x <= m; x++)
		{
			t = 0; s = INT_MIN; k = 0; l = 0;
			j = 1;
			for(i = 1; i <= n; i++)
			{
				column[x][i] = column[x - 1][i] + a[x][i];
				t = t + column[x][i];
				if(t > s)
				{
					s = t; k = i; l = j;
				}
				if(t < 0)
				{
					t = 0;
					j = i + 1;
				}
			}
			if(s > S)
			{
				S = s; x1 = x; y1 = k; x2 = z; y2 = l;
			}
		}
	}
	
	printf("\n");
	printf("Riga 1    -> %d\n", x2 - 1);
	printf("Colonna 1 -> %d\n\n", y2 - 1);
	printf("Riga 2    -> %d\n", x1 - 1);
	printf("Colonna 2 -> %d\n\n", y1 - 1);
	/* printf("Somma     -> %d\n\n", S); */
		
	return EXIT_SUCCESS;
}

Output:

Codice: Seleziona tutto

[vincenzo]$ gcc -Wall -Wextra -pedantic -O2 KadaneSubCubic.c -o prova
[vincenzo]$ ./prova

Riga 1    -> 2
Colonna 1 -> 1

Riga 2    -> 5
Colonna 2 -> 4

Gli indici restituiti sono a base zero.
Quindi riga 1 -> 2 indica la terza riga; colonna 1 -> 1 indica la seconda colonna.

[bennes]

Ho applicato il metodo consigliato da Zoff perchè apparentemente più semplice, ma un grazie a tutti per i preziosi consigli!