Определить алгоритм маршрута кругового (не точного круга)?

Question

Я получаю список путей из x, y координат из touchhevent. Как я могу обнаружить, что этот путь формирует круговой путь (не полный или точный круг)? Есть ли какой-либо алгоритм или способ обнаружить это?

Answer 1

Вот документ с кратким изложением различных методов подгонки кругов к данным: http://www.cs.bsu.edu/homepages/kerryj/kjones/circles.pdf

Answer 2

Я хотел бы сделать что-то вроде этого:

Пусть у меня есть точки полукруга:

val angles180 = (0 to 180 by 45).map(_/180.0 * Pi) 
val points = angles180.map { a => (math.cos(a), math.sin(a)) } 

я могу взять комбинации подмножеств с 3-х элементов:

val pointsList = points.combinations(3).toList 

И locate the center and radius of a circle given only three points on the circle, для каждого подмножества в pointsList:

val circles = for { 
    p <- pointsList 
} yield calculateCircle(p) 

Где:

case class Circle(x: Double, y: Double, r: Double) 

def calculateCircle(points: Seq[(Double, Double)]): Circle = { 
    val Seq((x1, y1), (x2, y2), (x3, y3)) = points 

    val mr = (y2 - y1)/(x2 - x1) 
    val mt = (y3 - y2)/(x3 - x2) 

    val x0 = (mr * mt * (y3 - y1) + mr * (x2 + x3) - mt * (x1 + x2))/(2 * (mr - mt)) 
    val y0 = -1.0/mr * (x0 - (x1 + x2)/2) + (y1 + y2)/2 

    val r = math.sqrt((x1 - x0) * (x1 - x0) + (y1 - y0) * (y1 - y0)) 

    Circle(x0, y0, r) 
} 

Вы должны проверить на наличие недопустимых кругов (возможно, точки коллинеарны и дают неверные результаты):

def isInvalid(circle: Circle) = 
    (circle.x.isNaN || circle.y.isNaN || circle.r.isNaN) 

val validCircles = circles.filterNot(isInvalid) 

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

Один из способов сделать это, чтобы увидеть, попадают ли их данные в интервал (m - x . s, m + x . s), где m - среднее значение, а s - стандартное отклонение. Для x == 2.58 99% данных лежат внутри интервала. Вы можете проверить, лежат ли каждый из данных кругов внутри, а если нет, это не круг. Помните, мы делаем это за x и y положениями центра круга и радиусом r, и это хорошо только, если все три хороши.

def looksLikeACircle(circles: Seq[Circle]) = { 
    val resultsLists = circles.map { c => List(c.x, c.y, c.r) }.transpose 

    val cis = resultsLists.map(interval99) 

    val good = resultsLists.zip(cis).map { case (values, ci) => withinInterval(values, ci) } 
    val allGood = good.reduceLeft { (acc, v) => acc && v } 

    allGood 
} 


val allGood = looksLikeACircle(validCircles) 

Где:

def mean(values: Seq[Double]) = values.sum/values.size 

def standardDeviation(values: Seq[Double]) = { 
    val m = mean(values) 

    math.sqrt(values.map { v => (v - m) * (v - m) }.sum/(values.size - 1)) 
} 

def interval99(values: Seq[Double]) = { 
    val m = mean(values) 
    val d = (2.58 * standardDeviation(values)) 

    (m - d, m + d) 
} 

def withinInterval(values: Seq[Double], ci: (Double, Double)) = 
    values.forall { v => ci._1 <= v && v <= ci._2 } 

Ну, это выглядит как точки сделать круг, но, возможно, это просто математика. Учитывая достаточно большой радиус, истинный круг может отображаться как прямая линия в окне. Возникает вопрос: мог ли пользователь сделать круг с этими точками в окне?

Вы можете проверить, если средний круг находится внутри границы окна:

case class Window(x: Double, y: Double, w: Double, h: Double) 

def calculateMeanCircle(circles: Seq[Circle]) = { 
    val resultsLists = circles.map { c => List(c.x, c.y, c.r) }.transpose 

    val Seq(xm, ym, rm) = resultsLists.map(mean) 

    Circle(xm, ym, rm) 
} 

def isCircleFit(circle: Circle, window: Window) = { 
    def isWithinBounds(value: Double, bounds: (Double, Double)) = { 
    bounds._1 <= value && value <= bounds._2 
    } 

    val (xMin, xMax) = (circle.x - circle.r, circle.x + circle.r) 
    val (yMin, yMax) = (circle.y - circle.r, circle.y + circle.r) 

    val horizontalBounds = (window.x, window.x + window.w) 
    val verticalBounds = (window.y, window.y + window.h) 

    val isInside = 
    isWithinBounds(xMin, horizontalBounds) && isWithinBounds(xMax, horizontalBounds) && 
    isWithinBounds(yMin, verticalBounds) && isWithinBounds(yMax, verticalBounds) 

    isInside 
} 

val meanCircle = calculateMeanCircle(validCircles) 

Наконец, для points в начале этого длинного поста (надеюсь, что вы все еще здесь) и window:

val window = Window(0, 0, 600, 800) 

println("Looks like a circle? " + allGood) 
println(meanCircle) 
println(window) 
println("Is mean circle fit? " + isCircleFit(meanCircle, window)) 

получаем:

Looks like a circle? true 
Circle(-8.088567489053774E-18,4.4408920985006264E-17,1.0) 
Window(0.0,0.0,600.0,800.0) 
Is mean circle fit? false 

W ell только один квадрант может быть нарисован этими точками внутри этого окна, поэтому не подходит.

Что делать, если:

val points5 = angles180.map { a => (window.w/2 + math.cos(a), window.h/2 + math.sin(a)) } 

Это лучше сейчас (в центре окна):

Looks like a circle? true 
Circle(300.0,400.0,1.0000000000000144) 
Window(0.0,0.0,600.0,800.0) 
Is mean circle fit? true 

Как насчет этих точек, почти образуют окружность с центром в (0, 0) и радиус r == 1:

val points = Seq(
    (1.0, 0.0), 
    (0.0, 1.1), 
    (-0.9, 0.0), 
    (-0.1, -1.0) 
) 

Ну, это выглядеть как один, но он не подходит снова, конечно (но вы видите точку):

Looks like a circle? true 
Circle(0.05805243445692886,0.07674497786857344,1.0288200278337032) 
Window(0.0,0.0,600.0,800.0) 
Is mean circle fit? false 

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

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