Как найти самый большой треугольник в выпуклой оболочке кроме поиска грубой силы
Это не учитывает свойства с параметрами и не учитывает частные методы доступа get / set, которые могут быть недоступны, а также не учитывает перечислимые элементы только для чтения, так что вот расширенное решение?
Я пытался конвертировать в C #, но обычные источники для этого не смогли этого сделать, и у меня нет времени конвертировать его самому.
''' <summary>
''' Import the properties that match by name in the source to the target.</summary>
''' <param name="target">Object to import the properties into.</param>
''' <param name="source">Object to import the properties from.</param>
''' <returns>
''' True, if the import can without exception; otherwise, False.</returns>
<System.Runtime.CompilerServices.Extension()>
Public Function Import(target As Object, source As Object) As Boolean
Dim targetProperties As IEnumerable(Of Tuple(Of Reflection.PropertyInfo, Reflection.MethodInfo)) =
(From aPropertyInfo In source.GetType().GetProperties(Reflection.BindingFlags.Public Or Reflection.BindingFlags.NonPublic Or Reflection.BindingFlags.Instance)
Let propertyAccessors = aPropertyInfo.GetAccessors(True)
Let propertyMethods = aPropertyInfo.PropertyType.GetMethods()
Let addMethod = (From aMethodInfo In propertyMethods
Where aMethodInfo.Name = "Add" AndAlso aMethodInfo.GetParameters().Length = 1
Select aMethodInfo).FirstOrDefault()
Where aPropertyInfo.CanRead AndAlso aPropertyInfo.GetIndexParameters().Length = 0 _
AndAlso (aPropertyInfo.CanWrite OrElse addMethod IsNot Nothing) _
AndAlso (From aMethodInfo In propertyAccessors
Where aMethodInfo.IsPrivate _
OrElse (aMethodInfo.Name.StartsWith("get_") OrElse aMethodInfo.Name.StartsWith("set_"))).FirstOrDefault() IsNot Nothing
Select New Tuple(Of Reflection.PropertyInfo, Reflection.MethodInfo)(aPropertyInfo, addMethod))
' No properties to import into.
If targetProperties.Count() = 0 Then Return True
Dim sourceProperties As IEnumerable(Of Tuple(Of Reflection.PropertyInfo, Reflection.MethodInfo)) =
(From aPropertyInfo In source.GetType().GetProperties(Reflection.BindingFlags.Public Or Reflection.BindingFlags.NonPublic Or Reflection.BindingFlags.Instance)
Let propertyAccessors = aPropertyInfo.GetAccessors(True)
Let propertyMethods = aPropertyInfo.PropertyType.GetMethods()
Let addMethod = (From aMethodInfo In propertyMethods
Where aMethodInfo.Name = "Add" AndAlso aMethodInfo.GetParameters().Length = 1
Select aMethodInfo).FirstOrDefault()
Where aPropertyInfo.CanRead AndAlso aPropertyInfo.GetIndexParameters().Length = 0 _
AndAlso (aPropertyInfo.CanWrite OrElse addMethod IsNot Nothing) _
AndAlso (From aMethodInfo In propertyAccessors
Where aMethodInfo.IsPrivate _
OrElse (aMethodInfo.Name.StartsWith("get_") OrElse aMethodInfo.Name.StartsWith("set_"))).FirstOrDefault() IsNot Nothing
Select New Tuple(Of Reflection.PropertyInfo, Reflection.MethodInfo)(aPropertyInfo, addMethod))
' No properties to import.
If sourceProperties.Count() = 0 Then Return True
Try
Dim currentPropertyInfo As Tuple(Of Reflection.PropertyInfo, Reflection.MethodInfo)
Dim matchingPropertyInfo As Tuple(Of Reflection.PropertyInfo, Reflection.MethodInfo)
' Copy the properties from the source to the target, that match by name.
For Each currentPropertyInfo In sourceProperties
matchingPropertyInfo = (From aPropertyInfo In targetProperties
Where aPropertyInfo.Item1.Name = currentPropertyInfo.Item1.Name).FirstOrDefault()
' If a property matches in the target, then copy the value from the source to the target.
If matchingPropertyInfo IsNot Nothing Then
If matchingPropertyInfo.Item1.CanWrite Then
matchingPropertyInfo.Item1.SetValue(target, matchingPropertyInfo.Item1.GetValue(source, Nothing), Nothing)
ElseIf matchingPropertyInfo.Item2 IsNot Nothing Then
Dim isEnumerable As IEnumerable = TryCast(currentPropertyInfo.Item1.GetValue(source, Nothing), IEnumerable)
If isEnumerable Is Nothing Then Continue For
' Invoke the Add method for each object in this property collection.
For Each currentObject As Object In isEnumerable
matchingPropertyInfo.Item2.Invoke(matchingPropertyInfo.Item1.GetValue(target, Nothing), New Object() {currentObject})
Next
End If
End If
Next
Catch ex As Exception
Return False
End Try
Return True
End Function
3 ответа
Yes, you can do significantly better than brute-force.
By brute-force I assume you mean checking all triples of points, and picking the one with maximum area. This runs in O(n3) time, but it turns out that it is possible to do it in not just O(n2) but in O(n) time!
[Update: A paper published in 2017 showed by example that the O(n) solution doesn't work for a specific class of polygons. See this answer for more details. But the O(n2) algorithm is still correct.]
By first sorting the points / computing the convex hull (in O(n log n) time) if necessary, we can assume we have the convex polygon/hull with the points cyclically sorted in the order they appear in the polygon. Call the points 1, 2, 3, … , n. Let (variable) points A, B, and C, start as 1, 2, and 3 respectively (in the cyclic order). We will move A, B, C until ABC is the maximum-area triangle. (The idea is similar to the rotating calipers method, as used when computing the diameter (farthest pair).)
With A and B fixed, advance C (e.g. initially, with A=1, B=2, C is advanced through C=3, C=4, …) as long as the area of the triangle increases, i.e., as long as Area(A,B,C) ≤ Area(A,B,C+1). This point C will be the one that maximizes Area(ABC) for those fixed A and B. (In other words, the function Area(ABC) is unimodal as a function of C.)
Next, advance B (without changing A and C) if that increases the area. If so, again advance C as above. Then advance B again if possible, etc. This will give the maximum area triangle with A as one of the vertices.
(The part up to here should be easy to prove, and simply doing this separately for each A would give an O(n2) algorithm.)
Now advance A again, if it improves the area, and so on.(The correctness of this part is more subtle: Dobkin and Snyder gave a proof in their paper, but a recent paper shows a counterexample. I have not understood it yet.)
Although this has three "nested" loops, note that B and C always advance "forward", and they advance at most 2n times in total (similarly A advances at most n times), so the whole thing runs in O(n) time.
Code fragment, in Python (translation to C should be straightforward):
# Assume points have been sorted already, as 0...(n-1)
A = 0; B = 1; C = 2
bA= A; bB= B; bC= C #The "best" triple of points
while True: #loop A
while True: #loop B
while area(A, B, C) <= area(A, B, (C+1)%n): #loop C
C = (C+1)%n
if area(A, B, C) <= area(A, (B+1)%n, C):
B = (B+1)%n
continue
else:
break
if area(A, B, C) > area(bA, bB, bC):
bA = A; bB = B; bC = C
A = (A+1)%n
if A==B: B = (B+1)%n
if B==C: C = (C+1)%n
if A==0: break
This algorithm is proved in Dobkin and Snyder, On a general method for maximizing and minimizing among certain geometric problems, FOCS 1979, and the code above is a direct translation of their ALGOL-60 code. Apologies for the while-if-break constructions; it ought to be possible to transform them into simpler while loops.
отвечая на ваш вопрос:
Описанная окружность треугольника не обязательно является минимальной ограничивающей окружностью многоугольника. Чтобы убедиться в этом, рассмотрим очень плоский равнобедренный треугольник, скажем, с вершинами в точках (0,0), (10,0) и (5,1). Минимальная ограничивающая окружность имеет центр (5,0) и радиус 5, но этот круг не касается вершины в точке (5,1), поэтому это не описанная окружность. (Описанная окружность имеет центр (5, -12) и радиус 13)
редактировать:
Выбор меньшего из описанной окружности или круга, содержащего противоположные точки диаметра многоугольника, также недостаточен, потому что он можно построить многоугольники, точки которых лежат вне описанной окружности максимального треугольника. Рассмотрим пятиугольник с вершинами в:
(-5, 0)
(-4, -1)
( 5, 0)
( 4, 1)
(-4, 1)
Максимальный треугольник имеет вершины в (-4, -1), (5, 0) и (-4, 1).
from http://www.wolframalpha.com/input/?i=triangle The area of the triangle = sqrt((a+b-c)(a-b+c)(-a+b+c)*(a+b+c)) / 4 If you use c connected to the end points of your convex polygon and if a and b would touch your convex polygon you could iterate around your polygon allowing a to grow and b to shrink until you find your maximum area. I would start mid point and try each direction for a larger area.