Diviser un plan de points en deux moitiés égales

Question

Étant donné un plan bidimensionnel dans lequel il y a n points. J'ai besoin de générer l'équation d'une ligne qui divise l'avion de telle sorte qu'il y ait n / 2 points d'un côté et n / 2 points de l'autre. (d'ailleurs, ce n'est pas un travail à domicile, j'essaie juste de résoudre le problème)

Answer 1

1. Créer une ligne arbitraire dans l'avion. Projet de chaque point sur la ligne une.k.un pour chaque point, obtenir le point le plus proche sur cette ligne-là.

2. L'ordre de ces points le long de la ligne dans les deux sens, et de choisir un point sur cette ligne tels qu'il existe un nombre égal de points sur la ligne, dans les deux sens.

3. Vous obtenez la ligne perpendiculaire à la première ligne qui passe par ce point. Cette ligne aura la moitié de l'original de points de chaque côté.

Il y a certains cas à éviter lors de cette opération. Plus important encore, si tous les points sont sur une seule ligne, ne choisissez pas une ligne perpendiculaire qui passe par elle. En fait, choisir la ligne elle-même, si vous n'avez pas à vous inquiéter au sujet de projeter les points. En ce qui concerne les mathématiques derrière cela, vecteur de projections sera très utile.

Answer 2

C'est une modification de la Division d'un avion de points en deux moitiés égales qui permet le cas avec chevauchement des points (dans ce cas, il va dire si oui ou non la réponse existe).

If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).

C'est - O(N) contrairement à d'autres solutions proposées.

En supposant une solution existe, la méthode ci-dessus va probablement mettre fin, même si je n'ai pas de preuve.

Essayez l'algorithme ci-dessus un peu de temps sauf si vous détectez cumul de points. Si vous détectez un nombre élevé de cumul de points, vous pouvez être mises à rude épreuve, mais il est terriblement inefficace force brute solution qui implique la vérification de tous les possibles angles:

For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.

Un angle critique est définie comme l'angle qui pourrait changer le résultat (imaginez la solution à une réponse précédente, à faire tourner l'ensemble des points jusqu'à ce qu'un ou plusieurs points de swaps position avec un ou plusieurs autres points, la traversée de la ligne de démarcation. Il y a seulement finitely nombre de ces pays, et je pense qu'ils sont limités par le nombre de points, alors vous êtes probablement à la recherche à quelque chose dans la gamme O(N^2)-O(N^2 log(N)) si vous avez cumul de points, pour une force brute approche.

Answer 3

Je suppose qu'un bon moyen est de trier / séquencer / ordonner les points (par exemple de gauche à droite), puis de choisir une ligne qui passe par (ou entre) le ou les points médians de la séquence.

Answer 4

Il y a des cas évidents où aucune solution n'est possible. Par exemple, lorsque vous avez trois tas de points. Un point à l'emplacement A, deux points à l'emplacement B et cinq points à l'emplacement C.

Si vous vous attendez à une distribution décente, vous pouvez probablement obtenir un bon résultat avec l'algorithme de tlayton. Pour sélectionner l'inclinaison de la ligne initiale, vous pouvez déterminer l'étendue de l'ensemble de points entier et choisir l'angle de la plus grande diagonale.