Деление плоскости точек в две равных [закрытые] половины

Учитывая 2 размерных плоскости, в которых существуют точки n. Я должен генерировать уравнение строки, которая делит плоскость, таким образом, что существуют точки n/2 на одной стороне и точки n/2 на другом.

32
задан M-- 10 September 2019 в 22:19
поделиться

8 ответов

Я предположил, что точки различны, иначе такой прямой может и не быть.

Если точки различны, то такая прямая всегда существует и ее можно найти с помощью детерминированного алгоритма с временем O(nlogn).

Предположим, что точек P1, P2, ..., P2n. Предположим, что все они не лежат на одной прямой. Если это так, то мы можем легко построить линию разбиения.

Сначала переведите точки так, чтобы все координаты (x и y) были положительными.

Теперь предположим, что у нас волшебным образом появилась точка Q на оси y, такая, что никакая прямая, образованная этими точками (т.е. любая бесконечная прямая Pi-Pj) не проходит через Q.

Теперь, поскольку Q не лежит внутри выпуклой оболочки точек, мы можем легко увидеть, что можем упорядочить точки по вращающейся линии, проходящей через Q. При некотором угле поворота половина точек будет лежать по одну сторону, а другая половина - по другую сторону этой вращающейся линии, или, другими словами, если рассматривать сортировку точек по наклону линии Pi-Q, то можно выбрать наклон между (медианной)-й и (медианной+1)-й точками. Этот выбор может быть выполнен за время O(n) любым алгоритмом выбора с линейным временем без необходимости сортировки точек.

Теперь выберем точку Q.

Предположим, что Q - это (0,b).

Предположим, что Q коллинеарна с P1 (x1,y1) и P2 (x2,y2).

Тогда имеем, что

(y1-b)/x1 = (y2-b)/x2 (заметим, что мы перевели точки так, что xi > 0).

Решение для b дает

b = (x1y2 - y1x2)/(x1-x2)

(Обратите внимание, если x1 = x2, то P1 и P2 не могут быть коллинеарны с точкой на оси Y).

Рассмотрим |b|.

|b| = |x1y2 - y1x2| / |x1 -x2|

Теперь пусть xmax будет x-координатой самой правой точки, а ymax - координатой самой верхней.

Также пусть D будет наименьшей ненулевой разницей x-координат между двумя точками (она существует, так как не все x одинаковы, так как не все точки коллинеарны).

Тогда получается, что |b| <= xmax*ymax/D.

Таким образом, выбираем точку Q (0,b) такой, что |b| > b_0 = xmax*ymax/D

D можно найти за время O(nlogn).

Величина b_0 может стать довольно большой, и нам, возможно, придется столкнуться с проблемами точности.

Конечно, лучший вариант - выбрать Q случайным образом! С вероятностью 1 вы найдете нужную точку, что сделает ожидаемое время работы O(n).

Если бы мы могли найти способ выбрать Q за время O(n) (найдя какой-нибудь другой критерий), то мы могли бы заставить этот алгоритм работать за время O(n).

26
ответ дан 27 November 2019 в 21:02
поделиться

Я предполагаю, что хороший способ - это сортировка/последовательность/упорядочение точек (например. например, слева направо), а затем выбрать линию, которая проходит через (или между) средними точками в последовательности.

1
ответ дан 27 November 2019 в 21:02
поделиться

Есть очевидные случаи, когда решение невозможно. Например. когда у вас три кучи очков. Одна точка в местоположении A, две точки в местоположении B и пять точек в местоположении C.

Если вы ожидаете приличного распределения, вы, вероятно, сможете получить хороший результат с помощью алгоритма Тлейтона. Чтобы выбрать начальный наклон линии, вы можете определить размер всего набора точек и выбрать угол наибольшей диагонали.

1
ответ дан 27 November 2019 в 21:02
поделиться
  1. Создайте произвольную линию в этой плоскости. Спроецируйте каждую точку на эту прямую, т.е. для каждой точки найдите ближайшую к ней точку на этой прямой.

  2. Расположите эти точки вдоль прямой в любом направлении и выберите такую точку на прямой, чтобы на ней было равное количество точек в любом направлении.

  3. Постройте прямую, перпендикулярную первой прямой, которая проходит через эту точку. По обе стороны от этой прямой будет половина исходных точек.

При выполнении этого действия следует избегать некоторых случаев. Самое главное, если все точки лежат на одной прямой, не выбирайте перпендикуляр, проходящий через нее. На самом деле, выберите саму прямую, чтобы не беспокоиться о проецировании точек. С точки зрения математики, векторные проекции будут очень полезны.

10
ответ дан 27 November 2019 в 21:02
поделиться

Медиана медиана равномерно делит набор чисел способом, похожим на то, чего вы пытаетесь достичь, и она может быть вычислена за время O(n) с помощью алгоритма выбора (статья в Cormen et al. лучше, поэтому вы можете посмотреть там). Итак, найдите медиану ваших значений x Mx (или ваших значений y My, если хотите) и задайте x = Mx (или y = My), и эта линия будет выровнена по оси и разделит ваши точки поровну.

Если природа вашей задачи требует, чтобы не более одной точки лежало на прямой (если в вашем наборе нечетное число точек, то хотя бы одна из них будет лежать на прямой), и вы обнаружили, что именно это и произошло (или вы просто хотите защититься от такой возможности), поверните все точки на некоторый случайный угол θ и вычислите медиану повернутых точек. Затем поверните вычисленную вами медиану на -θ, и она равномерно разделит точки.

Вероятность случайного выбора θ так, что проблема проявится снова, очень мала при конечном числе точек, но если это произойдет, попробуйте снова с другим θ.

1
ответ дан 27 November 2019 в 21:02
поделиться

Не знаю, насколько это полезно. Я видел похожую проблему ...

Если у вас уже есть вектор направления (он же коэффициенты размеров вашей плоскости).

Затем вы можете найти две точки внутри этой плоскости, и, просто используя формулу средней точки, вы можете найти среднюю точку этой плоскости.

Затем, используя коэффициенты этой плоскости и средней точки, вы можете найти плоскость, которая находится на равном расстоянии от обеих точек, используя общее уравнение плоскости.

Строка тогда будет означать выражение одной переменной через другую так что вы найдете линию с равным расстоянием между обеими плоскостями.

Существуют разные способы сделать это, например, проекция с использованием уравнения расстояния от плоскости, но я считаю, что это сильно усложнит вашу математику.

0
ответ дан 27 November 2019 в 21:02
поделиться

Я взял идея от Moron и andand и продолжал формировать детерминированный алгоритм O (n).

Я также предположил, что точки разные и n четное (думал, что алгоритм может быть поменял так, чтобы неравномерное n с одной точкой на разделительной линии также поддерживаются).

Алгоритм пытается разделить точки вертикальной линией между ними. Это не удается, только если точки в середине имеют одинаковое значение x. В этом случае алгоритм определяет, сколько точек с одинаковым значением x должно быть слева и внизу, и соответственно поворачивает линию.

Попробую пояснить на примере. Предположим, у нас есть 16 точек на плоскости. Сначала нам нужно получить точку с 8-м по величине x-значением и точка с 9-м по величине x-значением.С помощью алгоритма выбора это возможно за O (n), как указано в другом ответе. Если значение x этих точек отличается, все готово. Мы создаем вертикальную линию между этими двумя точками и который разделяет точки на равные.

Проблема теперь возникает, если значения x равны. Итак, у нас есть 3 набора точек. То, что слева (x a ), посередине (x = x a ) и что в правой части (x> x a ). Теперь идея состоит в том, чтобы подсчитать очки слева и посчитайте, сколько очков от середины нужно туда, так, чтобы половина точек была на той стороне. Здесь мы можем игнорировать правую сторону потому что, если у нас есть половина точек на левой стороне, большая половина должна быть на правой стороне.

Предположим, у нас есть 3 точки (c = 3) слева, 6 посередине и 7 справа (алгоритм не знает счетчик со средней или правой стороны, потому что это не нужно, но мы также можем определить его за O (n)). Нам нужно 8-3 = 5 очков от середины, чтобы перейти на левую сторону. Очки, которые мы уже получили на первом этапе, теперь бесполезны, потому что они определяются только значением x и может быть любой из точек посередине.

Нам нужны 5 точек от середины с наименьшим значением y слева и точка с наивысшим значением y справа. Снова используя алгоритм выбора, мы получаем точку с 5-м по величине значением y. и точка с 6-м по величине значением y.Обе точки будут иметь значение x, равное x a , иначе мы бы не дошли до этого шага, потому что была бы вертикальная линия.

Теперь мы можем создать точку Q посередине этих двух точек. Это одна точка от полученной линии. Нужна еще одна точка, чтобы никакие точки с левой или правой стороны не разделялись. Чтобы получить эту точку, нам нужна точка с левой стороны, с наименьшим углом (b h ) между вертикальной линией в точке x a и линия, определяемая этой точкой и Q. Нам также понадобится эта точка с правой стороны (с углом a g ). Новая точка R находится между точкой с меньшим углом и точка на вертикальной прямой (если нижний угол находится слева на точку выше Q и если нижний угол находится справа, точка ниже Q).

Линия, определяемая Q и R, разделяет точки посередине. так, чтобы с обеих сторон было четное количество точек. Он не разделяет точки ни на левую, ни на правую сторону, потому что, если бы это было так, эта точка имела бы меньший угол и был бы выбран для вычисления R.

С точки зрения математика, который должен хорошо работать в O (n). Для компьютерных программ довольно легко найти футляр. где точность становится проблемой. Пример с 4 точками будет A (0, 100000000), B (0, 100000001), C (0, 0), D (0,0000001, 0). В этом примере Q будет (0, 100000000,5) и R (0,00000005, 0). Что дает B и C с левой стороны и A и D с правой стороны. Но возможно, что A и B оба находятся на разделительной линии, из-за ошибок округления.А может только один из них. Таким образом, он относится к входным значениям, если этот алгоритм соответствует требованиям.

  1. получают две точки P a (x a , y a ) и P b (x b , y b )
    которые являются медианами на основе значений x > O (n)
  2. if x a ! = X b , вы можете остановиться здесь
    поскольку параллельная линия по оси Y между этими двумя точками является результатом > O (1)
  3. получить все точки, в которых значение x равно x a > O (n)
  4. count точки со значением x меньше x a как c > O (n)
  5. получают самую низкую точку P c на основе значений y из точек из 3. > O (n)
  6. получить наибольшую точку P d на основе значений y из точек из 3. > O (n)
  7. получить (n / 2-c) наибольшая точка P e на основе значений y из точек из 3. > O (n)
  8. также получить следующую наибольшую точку P f на основе значений y из точек из 3.> O (n)
  9. создать новую точку Q (x a , (y e + y f ) / 2) между P e и P f > O (1)
  10. для всех точек P i вычислить
    угол a i между P c , Q и P i и
    угол b i между P d , Q и P i > O (n)
  11. получить точку P g с наименьший угол a g g > 0 ° и g <180 °) > O (n)
  12. получить точка P h с наименьшим углом b h (с b h > 0 ° и b h <180 °) > O (n)
  13. , если нет P g или P h (все точки имеют одинаковое значение x)
    создать новую точку R (x a +1, 0) где угодно, но с другим значением x, чем x a
    , иначе, если a g меньше, чем b h
    создать новую точку R ((x c + x g ) / 2, (y c + y g ) / 2) между P c и P g
    else
    создать новую точку R ((x d + x h ) / 2, (y d + y h ) / 2) между P d и P h > O (1)
  14. линия, определяемая Q и R, делит точки > O (1)
0
ответ дан 27 November 2019 в 21:02
поделиться

В дополнение к ответу М: метод генерации Q (которая не так далека) за O(n log n).

Для начала пусть Q будет любой точкой на оси y, т.е. Q = (0,b) - хорошими вариантами могут быть (0,0) или (0, (ymax-ymin)/2).

Теперь проверьте, существуют ли две точки (x1, y1), (x2, y2), коллинеарные с Q. Прямая между любой точкой и Q имеет вид y = mx + b; поскольку b постоянно, это означает, что две точки коллинеарны с Q, если их наклоны m равны. Итак, определите наклоны mi для всех точек и проверьте, нет ли дубликатов: (аморитизировано O(n) с помощью хэш-таблицы)

Если все m различны, мы закончили; мы нашли Q, и алгоритм M, приведенный выше, генерирует линию за O(n) шагов.
Если две точки коллинеарны с Q, переместим Q вверх на небольшое количество ε, Qnew = (0, b + ε), и покажем, что Qnew не будет коллинеарна с двумя другими точками.

Критерий для ε, полученный ниже, таков:

ε < mminΔ*xmin

Для начала наши m выглядят следующим образом:

mi = yi/xi - b/xi

Найдем минимальную разность между любыми двумя distinct mi и назовем ее mminΔ (O(n log n) например, сортируя и сравнивая разности между mi и i+1 для всех i)

Если мы подтянем b на ε, то новое уравнение для m станет:

mi,new = yi/xi - b/xi - ε/xi
       = mi,old - ε/xi

Поскольку ε > 0 и xi > 0, все m уменьшаются, причем все уменьшаются на максимум ε/xmin. Таким образом, если

ε/xmin < mminΔ, ie.
ε < mminΔ*xmin

верно, то два mi, которые ранее были неравными, гарантированно останутся неравными.


Осталось показать, что если m1,old = m2,old, то m1,new =/= m2,new. Поскольку оба mi уменьшились на величину ε/xi, то это эквивалентно доказательству x1 =/= x2. Если они были равны, то:

y1 = m1,oldx1 + b = m2,oldx2 + b = y2

Противоречит нашему предположению, что все точки различны. Таким образом, m1, new =/= m2, new, и никакие две точки не коллинеарны с Q.

0
ответ дан 27 November 2019 в 21:02
поделиться
Другие вопросы по тегам:

Похожие вопросы: