एल्गोरिदम 2 डी अंक

Question

की दी गई सूची से सभी उत्तल चतुर्भुज को खोजने के लिए मुझे 2 डी अंकों की दी गई सूची से सभी उत्तल चतुर्भुज को खोजने के लिए एक प्रोग्राम बनाना है। मैंने वेक्टर क्रॉस उत्पाद के साथ कोशिश की है लेकिन यह एक सही समाधान प्रतीत नहीं होता है।

शायद इस समस्या के लिए कुछ प्रभावी एल्गोरिदम है लेकिन मुझे यह नहीं मिल रहा है।

इनपुट

 
Number of Points: 
6 

 
coordinates of points (x,y): 
0 0 
0 1 
1 0 
1 1 
2 0 
2 1 

आउटपुट

 
Number of convex quadrilaterals: 
9 

Answer 1

एक चतुर्भुज उत्तल है अगर इसकी विकर्णों एक दूसरे को काटना:

यह इनपुट और आउटपुट के साथ एक उदाहरण मामला है। इसके विपरीत, यदि दो रेखा खंड अलग-अलग होते हैं, तो उनके चार अंत बिंदु एक उत्तल चतुर्भुज बनाते हैं।

अंकों की हर जोड़ी आप एक रेखा खंड, और दो रेखा खंडों के बीच चौराहे के हर बिंदु देता है एक उत्तल चतुर्भुज से मेल खाती है।

आप या तो भोली एल्गोरिथ्म है कि वे सभी सेगमेंट जोड़े तुलना, या Bentley–Ottmann algorithm का उपयोग कर points of intersection पा सकते हैं। पूर्व ओ (एन) लेता है; और बाद ओ ((n + क्ष) लॉग ऑन n) (जहां क्ष उत्तल चतुर्भुज की संख्या है)। सबसे खराब स्थिति क्ष = Θ (n) में - एक चक्र पर n बिंदुओं पर विचार - तो बेंटले-Ottmann हमेशा तेजी से नहीं है।

import numpy as np 
from itertools import combinations 

def intersection(s1, s2): 
    """ 
    Return the intersection point of line segments `s1` and `s2`, or 
    None if they do not intersect. 
    """ 
    p, r = s1[0], s1[1] - s1[0] 
    q, s = s2[0], s2[1] - s2[0] 
    rxs = float(np.cross(r, s)) 
    if rxs == 0: return None 
    t = np.cross(q - p, s)/rxs 
    u = np.cross(q - p, r)/rxs 
    if 0 < t < 1 and 0 < u < 1: 
     return p + t * r 
    return None 

def convex_quadrilaterals(points): 
    """ 
    Generate the convex quadrilaterals among `points`. 
    """ 
    segments = combinations(points, 2) 
    for s1, s2 in combinations(segments, 2): 
     if intersection(s1, s2) != None: 
      yield s1, s2 

और एक उदाहरण रन:

यहाँ पायथन में भोली संस्करण है

>>> points = map(np.array, [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)]) 
>>> len(list(convex_quadrilaterals(points))) 
9